The associated decision problem is: Input: the processing times $T_i >0, T_i in mathbb{N}$ of $N$ jobs, an integer $Kgeq 2N$Question: can we process all the jobs in time $leq K$ using the above “bottleneck” model ?
Has this problem a name?
What is its complexity? (is it in $sf{P}$ or is it $sf{NP}$-complete?)
UPDATE 29 March:
As correctly noticed by M.Cafaro in his answer, the problem is similar to the Unconstrained Minimum Finish Time Problem (UMFT) (see Chapter 17 of Handbook of Scheduling Algorithms) which is $sf{NP}$-hard (proved in W. Kern and W. Nawijn, “Scheduling multi-operation jobs with time lags on a single machine”, University of Twente, 1993). As I can see, there are some differences because in my model:
- the pre/post processing time is constant (1 unit of time)
- as soon as the job is completed it must immediately be post-processed (the UMFT model allows delays)
I didn’t found the Kern & Nawijn proof online, so I still don’t know if the above restrictions change the difficulty of the problem. Finally you can think the whole process like a single cook robot with a big oven; the robot can prepare different types of foods one at a time (all require the same time of preparation), put them in the oven, and as soon as they are cooked it must remove them from the oven and add some cold ingredients … the “cook robot problem” 🙂
Asked By : Vor
Answered By : Peter Shor
Theorem 24. The problem of minimizing the makespan on a single machine with two unit time operations per job with arbitrary intermediate delays is strongly NP-hard.
The exact model studied here is that job $i$ consists of two operations that take unit time separated by some delay time $T_i$. The problem is strongly NP-complete both when the exact value of the delay $T_i$ is specified for each job, and when some minimum delay time is specified for each job.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10869
