Complexity of shop-scheduling problems with fixed number of jobs: a survey.

*(English)*Zbl 1180.90115Summary: The paper surveys the complexity results for job shop, flow shop, open shop and mixed shop scheduling problems when the number \(n\) of jobs is fixed while the number \(r\) of operations per job is not restricted. In such cases, the asymptotical complexity of scheduling algorithms depends on the number \(m\) of machines for a flow shop and an open shop problem, and on the numbers \(m\) and \(r\) for a job shop problem. It is shown that almost all shop-scheduling problems with two jobs can be solved in polynomial time for any regular criterion, while those with three jobs are NP-hard. The only exceptions are the two-job, \(m\)-machine mixed shop problem without operation preemptions (which is NP-hard for any non-trivial regular criterion) and the \(n\)-job, \(m\)-machine open shop problem with allowed operation preemptions (which is polynomially solvable for minimizing makespan).

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

90C60 | Abstract computational complexity for mathematical programming problems |

PDF
BibTeX
XML
Cite

\textit{P. Brucker} et al., Math. Methods Oper. Res. 65, No. 3, 461--481 (2007; Zbl 1180.90115)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Akers SB (1956) A graphical approach to production scheduling problems. Oper Res 4:244–245 |

[2] | Akers SB, Friedman J (1956) A non-numerical approach to production scheduling problems. Oper Res 3:429–442 |

[3] | Aho AV, Hopcroft JE, Ullman JD (1974) The design and analysis of computer algorithms. Addison-Wesley, Reading |

[4] | Brucker P (1988) An efficient algorithm for the job-shop problem with two jobs. Computing 40:353–359 · Zbl 0654.90036 |

[5] | Brucker P (1994) A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs. Oper Res Spekt 16:5–7 · Zbl 0807.90061 |

[6] | Brucker P, Jurisch B, Meyer W (1989) Geometric methods for solving the job-shop scheduling problem. Preprint Heft 127, Fachbereich Mathematik/Informatik, Universität Osnabrück |

[7] | Brucker P, Kravchenko SA, Sotskov YuN (1994) On the complexity of two machine job-shop scheduling with regular objective functions. Oper Res Spect 16:5–7 · Zbl 0807.90061 |

[8] | Brucker P, Kravchenko SA, Sotskov YuN (1999) Preemptive job-shop scheduling problems with a fixed number of jobs. Math Methods Oper Res 49:41–76 · Zbl 0948.90064 |

[9] | Brucker P, Schlie R (1990) Job-shop scheduling with multipurpose machines. Computing, 45:369–375 · Zbl 0813.90058 |

[10] | Gonzalez T, Sahni A (1976) Open shop scheduling to minimize finish time. J Associat Comput Mach 23:665–679 · Zbl 0343.68031 |

[11] | Hardgrave WH, Nemhauser GL (1963) A geometric model and graphical algorithm for a sequencing problem. Oper Res 11:889–900 · Zbl 0124.36302 |

[12] | Johnson SM (1954) Optimal two- and three-stage production schedules with setup times included. Naval Res Logist Quart 1:61–68 · Zbl 1349.90359 |

[13] | Kravchenko SA, Sotskov YuN (1996) Optimal makespan schedule for three jobs on two machines. Math Methods Oper Res 43:233–238 · Zbl 0848.90069 |

[14] | Masuda T, Ishii H, Nishida T (1985) The mixed shop scheduling problem. Discr Appl Math 11:175–186 · Zbl 0579.90053 |

[15] | Servach VV (1983) On the Akers–Friedman problem. Upravljajemye Syst Novosibirsk 23:70–81 (in Russian) · Zbl 0546.90043 |

[16] | Shakhlevich NV, Strusevich VA (1990) Scheduling two jobs in a multi-machine open shop to minimize an arbitrary regular penalty function. Report 9125/A, Erasmus University Rotterdam, The Netherlands |

[17] | Shakhlevich NV, Sotskov YuN (1994) Scheduling two jobs with fixed and nonfixed routines. Computing 52:17–30 · Zbl 0808.90084 |

[18] | Shakhlevich NV, Sotskov YuN, Werner F (1999) Shop-scheduling problems with fixed and non-fixed machine orders of jobs. Ann Oper Res 92:281–304 · Zbl 0958.90038 |

[19] | Shakhlevich NV, Sotskov YuN, Werner F (2000) Complexity of mixed shop scheduling problems: A survey. Euro J Oper Res 120:343–351 · Zbl 0949.90047 |

[20] | Sotskov YuN (1985) Optimal scheduling of two jobs with a regular criterion. Institute of Engineering Cybernetics of the Academy of Sciences of BSSR, Minsk, pp. 86–95 (in Russian) |

[21] | Sotskov YuN (1989) Complexity of scheduling with fixed number of jobs. Dokl Akad Nauk BSSR. 33:488–491 (in Russian) · Zbl 0671.90036 |

[22] | Sotskov YuN (1990) Complexity of optimal scheduling of three jobs Kibernetika N 5:74–78 (in Russian) |

[23] | Sotskov YuN (1991) The complexity of shop-scheduling problems with two or three jobs. Euro J Oper Res 53:326–336 · Zbl 0742.90046 |

[24] | Sotskov YuN, Shakhlevich NV (1990) NP-hardness of optimal scheduling three jobs. Vestsi Akad Navuk BSSR Ser Fiz-Mat Navuk 4:96–101 (in Russian) · Zbl 0703.90049 |

[25] | Sotskov YuN, Shakhlevich NV (1995) NP-hardness of shop-scheduling problems with three jobs. Discr Appl Mathe 59:237–266 · Zbl 0837.90072 |

[26] | Strusevich VA (1986) On the possibility of constructing optimal makespan schedules for multi-stage systems with nonfixed routes. Vestsi Akad Navuk BSSR Ser Fiz-Mat Navuk 6:43–48 (in Russian) · Zbl 0611.90061 |

[27] | Szwarc W (1960) Solution of the Akers-Friedman scheduling problem. Oper Res 8:782–788 · Zbl 0100.15102 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.