A 5-parameter complexity classification of the two-stage flow shop scheduling problem with job dependent storage requirements

The paper is concerned with the two-machine scheduling problem where each job is to be processed on the first-stage machine and after that on the second-stage machine. In order to be processed, each job requires storage space that it seizes at the start of its processing on the first-stage machine and releases only at the completion of processing on the second-stage machine. The storage space is limited and its consumption varies from job to job. The goal is to minimise the time needed for the completion of all jobs. All instances of the considered scheduling problem are classified by means of five parameters. This leads to the sixty four families of instances. For each family, the paper establishes its computational complexity and, in the case of polynomial-time solvability, presents a polynomial-time algorithm, constructing an optimal schedule.

Automated summary

The paper explores the two-machine scheduling problem where each job is processed on a first-stage machine before moving to a second-stage machine. Jobs require storage space and the goal is to minimize completion time. Instances are classified through five parameters, resulting in 64 families, with computational complexity and polynomial-time solvability established for each family.