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

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

  Google Scholar 

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

  Google Scholar 

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

  MATH  Google Scholar 

• Brucker P (1988) An efficient algorithm for the job-shop problem with two jobs. Computing 40:353–359

  Article  MATH  MathSciNet  Google Scholar 

• 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

  Article  MATH  MathSciNet  Google Scholar 

• 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

• 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

  Article  MATH  Google Scholar 

• 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

  MATH  MathSciNet  Google Scholar 

• Brucker P, Schlie R (1990) Job-shop scheduling with multipurpose machines. Computing, 45:369–375

  Article  MATH  MathSciNet  Google Scholar 

• Gonzalez T, Sahni A (1976) Open shop scheduling to minimize finish time. J Associat Comput Mach 23:665–679

  MATH  MathSciNet  Google Scholar 

• Hardgrave WH, Nemhauser GL (1963) A geometric model and graphical algorithm for a sequencing problem. Oper Res 11:889–900

  MATH  Google Scholar 

• Johnson SM (1954) Optimal two- and three-stage production schedules with setup times included. Naval Res Logist Quart 1:61–68

  Article  Google Scholar 

• Kravchenko SA, Sotskov YuN (1996) Optimal makespan schedule for three jobs on two machines. Math Methods Oper Res 43:233–238

  Article  MATH  MathSciNet  Google Scholar 

• Masuda T, Ishii H, Nishida T (1985) The mixed shop scheduling problem. Discr Appl Math 11:175–186

  Article  MATH  MathSciNet  Google Scholar 

• Servach VV (1983) On the Akers–Friedman problem. Upravljajemye Syst Novosibirsk 23:70–81 (in Russian)

  Google Scholar 

• 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

• Shakhlevich NV, Sotskov YuN (1994) Scheduling two jobs with fixed and nonfixed routines. Computing 52:17–30

  Article  MATH  MathSciNet  Google Scholar 

• 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

  Article  MATH  MathSciNet  Google Scholar 

• Shakhlevich NV, Sotskov YuN, Werner F (2000) Complexity of mixed shop scheduling problems: A survey. Euro J Oper Res 120:343–351

  Article  MATH  MathSciNet  Google Scholar 

• 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)

• Sotskov YuN (1989) Complexity of scheduling with fixed number of jobs. Dokl Akad Nauk BSSR. 33:488–491 (in Russian)

  MATH  MathSciNet  Google Scholar 

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

• Sotskov YuN (1991) The complexity of shop-scheduling problems with two or three jobs. Euro J Oper Res 53:326–336

  Article  MATH  Google Scholar 

• 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)

  MathSciNet  Google Scholar 

• Sotskov YuN, Shakhlevich NV (1995) NP-hardness of shop-scheduling problems with three jobs. Discr Appl Mathe 59:237–266

  Article  MATH  MathSciNet  Google Scholar 

• 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)

  MathSciNet  Google Scholar 

• Szwarc W (1960) Solution of the Akers-Friedman scheduling problem. Oper Res 8:782–788

  Article  MATH  Google Scholar 

Download references