Scheduling n jobs on a single machine regarding total earliness and tardiness is characterized via the Graham notations as 1 || sum_j (E_j + T_j). Let me review a bit history of this problem,
First, Garey, M. R., Tarjan, R. E., & Wilfong, G. T. (1998) proved that the problem is NP-hard in the ordinary sense by a reduction from 2-Partition.
Secnod, Wan, L., & Yuan, J. (2013) proved that the problem is NP-hard in the strong sense by a reduction from 3-Partition.
Third, I, again, reduced 2-Partition to the problem by a simpler proof strategy. I also developed a working pseudo-polynomial algorithm.
So, my question is how come it is possible to find a pseudo-polynomial algorithm for a problem that is already proven NP-hard in the strong sense.
Dear Mohammad Namakshenas,
I suggest you to see links and attached file on topic.
https://www.amazon.in/Handbook-Scheduling-Applications-International-Information-ebook/dp/B07FP8NXHS
https://www.amazon.com/Scheduling-Theory-Single-Stage-Mathematics-Applications/dp/0792328531
https://www.amazon.ca/Scheduling-Theory-Multi-Stage-V-Tanaev/dp/9401045216
https://www.springer.com/gp/book/9783658284145
https://www.springer.com/gp/book/9783319487489
Best regards
Thanks for the sources provided Mohamed-Mourad Lafifi .
However, this is a bit profound question in the scheduling theory; I believe that those sources would not help.
Thank you for your valuable comments Michael Short .
1) For your first question, I had previously discussed the issue with Micheal Pinedo and the following is the feedback from him:
***Quote***
If it is Jinjiang Yuan who proved strongly NP-Hardness, then it is most likely
true. Jinjiang Yuan is by far the strongest Chinese scheduling researcher and
I do not think he ever has made a mistake. If this proof of his is wrong, then it is
the first time I have heard he has made an error.
***Unquote***
I myself checked the details of the proof with one of the esteemed computer science professors at Sharif University. I've checked the proof in numerous ways. They have done a pseudo-polynomial reduction from 3-partition to 1 || sum_j (E_j + T_j), in which all inputs are preserved in polynomial bounds during this transformation. It is noteworthy to refer to their claim in their published paper:
***Quote***
Above construction can be done in a pseudo-polynomial time, which is polynomial under the unary encode.
***Unquote***
2) About your second question, there are two great papers for problem 1|p_j=p|sum_j (E_j + T_j) , considering equal processing times:
_____________________________________________________________________
Garey, M.R., Tarjan, R.E., Wilfong, G.T.: One-processor scheduling with symmetric earliness and tardiness penalties. Mathematics of Operations Research 13(2), 330–348 (1988)
Szwarc, W., Mukhopadhyay, S.K.: Optimal timing schedules in earliness-tardiness single machine sequencing. Naval Research Logistics (NRL) 42(7), 1109–1114 (1995)
--------------------------------------------------------------------------------------------------------------
In our developed algorithm, we have made use of the job-clustering technique and some sub-modular properties of 1 || sum_j (E_j + T_j). The complexity of the algorithm is the polynomial function of sum_j (p_j) or some of processing times.
Michael Short. Our algorithm is definitely a deterministic scheme and finds the optimal schedule and the optimal objective in the worst-case running time of a polynomially bounded function w.r.t. the sum of processing times and the number of jobs.
By the job clustering, I mean a technique of clustering jobs in which no shift can be applied to the schedule of a cluster of jobs that can improve the objective. i.e., a semi-active schedule.
Dear Mohammad Namakshenas ,
I think you must either prove that the strong NP-completeness result is not correct (which is possible) or show that your algorithm is indeed correct. My experience with the sum of tardiness suggests that any added element would easily make the problem strongly NP-hard although the classical single machine case is NP-hard in the ordinary sense. Therefore, if I know nothing about the problem, my first impression would be that the single machine with sum of tardiness and earliness is NP-hard in the strong sense. This is contradictory with what you suggest (which is super interesting): so, I am very curious to see your algorithm.
Best,
Morteza
Dear Morteza Davari ,
I attacked the proof in several aspects without any success Maybe I'm missing something.
You can find the brief concept of the algorithm here: http://www.optimization-online.org/DB_HTML/2019/07/7280.html .
However, the concept of algorithm for 1||sum(Tj+Ej) is a bit complicated. We are working on complexity status to publish the original results. It runs a pseudo-polynomial times (as sequence) of a polynomial oracle (as schedule).
- Badges
- Science topic
- Similar topics
- Automotive Engineering
- Machines