11
$\begingroup$

Given $n$ jobs $J_1,J_2,...,J_n$, each job requires $T_i > 0, T_i \in N$ time to complete.

Each job must be pre-processed and post-processed by a single machine M that can handle only 1 job at a time and both phases require 1 unit of time. After being pre-processed, job $J_i$ is sent to a machine with unlimited power (that can handle in parallel an unlimited number of jobs) and it will be ready in time $T_i$, then it must be sent (immediately) to machine M again for post-processing.

enter image description here

The associated decision problem is:

Input: the processing times $T_i >0, T_i \in \mathbb{N}$ of $N$ jobs, an integer $K\geq 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" :-)

Improve this question
$\endgroup$
11
  • $\begingroup$ Nice. I have a feeling that the bottleneck should simplify things. $\endgroup$
    – Raphael
    Commented Mar 28, 2013 at 12:01
  • $\begingroup$ The constraint $k \geq 2 n$ is always verified, since pre and post-processing costs are both 1 unit of time and you have $n$ jobs. Are you sure the constraint is correct ? $\endgroup$
    – Massimo Cafaro
    Commented Mar 28, 2013 at 12:03
  • $\begingroup$ Sorry, I was not clear about what I meant in the previous comment. Is $k$ explicitly given in input as a "deadline" or are you asking for an algorithm to minimize $k$ ? $\endgroup$
    – Massimo Cafaro
    Commented Mar 28, 2013 at 12:11
  • $\begingroup$ @MassimoCafaro: $k$ is given as input (to make the optimization problem a decision problem). As you noticed, I wrote $k \geq 2n$ because if $k < 2n$ the answer is trivially NO. But perhaps it is confusing and I should delete it. $\endgroup$
    – Vor
    Commented Mar 28, 2013 at 12:58
  • 1
    $\begingroup$ Your question is proven NP-complete in "Minimizing Makespan in a Two-Machine Flow Shop with Delays and Unit-Time Operations is NP-Hard" by W. Yu, H. Hoogeveen, and J.K. Lenstra (2004), who also say that Kern and Nawijn did not solve it. I quote: "The complexity status of the special case with unit processing time tasks has been open for both minimum and exact delays. The complexity status of the one with minimum delays is posed as an open question by Kern and Nawijn (1991)." $\endgroup$
    – Peter Shor
    Commented Jun 18, 2013 at 0:08

2 Answers 2

Reset to default
5
$\begingroup$

The question is proven NP-hard in "Minimizing Makespan in a Two-Machine Flow Shop with Delays and Unit-Time Operations is NP-Hard" by W. Yu, H. Hoogeveen, and J.K. Lenstra (2004). This is proven in section 9 of the paper:

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.

Improve this answer
$\endgroup$
5
$\begingroup$

This looks like the so called master-slave scheduling model introduced by Sahni. In particular, your problem falls under the Single-Master Master-Slave Systems. You can distinguish several cases:

  1. If you do not add any additional constraint on the order of job execution (as in your case), the problem is called unconstrained minimum finish time problem (UMFT) and has been shown to be NP-hard;

  2. Same Pre- and Postprocessing Orders: it is possible to design an $O(n \log n)$ algorithm to construct an order preserving minimum finish time (OPMFT) schedule;

Therefore, in case 1 your problem is $NP$-hard, while it is in $P$ in case 2.

Additional related problems are:

  1. Reverse Order Postprocessing: For any given preprocessing permutation, $σ$ , it is possible to construct a reverse-order schedule, referred to as canonical reverse order schedule (CROS). Given a preprocessing permutation $σ$ , the corresponding CROS is unique. It is easy to establish that every minimum finish-time reverse order (ROMFT) schedule is a CROS.

  2. no-wait-in-process constraint:

a) [MFTNW] Minimize finish time subject to the no-wait-in-process constraint; b) [OP-MFTNW] This is the order-preserving version of MFTNW. That is, minimize finish time subject to the no-wait-in-process and order-preserving constraints; c) [RO-MFTNW] Minimize finish time subject to the no-wait-in-process and reverse-order constraints.

Problems $a$ and $b$ are NP-hard, while $c$ admits a polynomial time solution.

Additional details in Handbook of Scheduling, chapter 17.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thanks, it is similar (I don't have the book but I found this paper ). I'll read it carefully later, Just a question after reading its introduction, it seems that it uses $n$ slaves (after preprocessing), but in my model there are an unlimited number of slaves; is it correct?. I'll read the proof of NP-hardness of UMFT and see if it uses the hypothesis that the number of slaves is limited. $\endgroup$
    – Vor
    Commented Mar 28, 2013 at 13:56
  • $\begingroup$ Sahni showed that you can always use exactly $n$ slaves: "The available processors are divided into two categories: master and slave. If $n$ denotes the number of jobs, then no schedule can use more than $n$ slaves. Hence, we may assume that there are exactly $n$ slaves." So your problem is easily translated to this setting: you simply discard and do not use the additional slaves available in the machine with unlimited slaves. $\endgroup$
    – Massimo Cafaro
    Commented Mar 28, 2013 at 14:06
  • 2
    $\begingroup$ It looks to me like the NP-hardness proof of Sahni critically uses the fact that the pre-processing times and post-processing times can be arbitrary. The OP's problem has all these times equal to 1. Does the proof work in this case? $\endgroup$
    – Peter Shor
    Commented Mar 28, 2013 at 14:16
  • $\begingroup$ Vor, the paper you refer to is just an extract with many missing parts from chapter 17 of the book. However, the missing part will prevent you from correctly understanding (missing notation etc). $\endgroup$
    – Massimo Cafaro
    Commented Mar 28, 2013 at 14:17
  • $\begingroup$ Peter, I am not sure and I need to check the proof; if it just requires pre- an post-processing times > 0 it should include the OP's problem when considering the unconstrained minimum finish time problem. By the same reasoning, this should lead instead to the $O(n \log n)$ polynomial time algorithm for the order preserving minimum finish time problem. $\endgroup$
    – Massimo Cafaro
    Commented Mar 28, 2013 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.