Flow shop with job–dependent buffer requirements—a polynomial–time algorithm and efficient heuristics

Publication Type:
Conference Proceeding
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2019, 11548 LNCS pp. 342 - 357
Issue Date:
Filename Description Size
2019_Book_MathematicalOptimizationTheory.pdfPublished version21.38 MB
Adobe PDF
Full metadata record
© Springer Nature Switzerland AG 2019. The paper is concerned with the two-machine flow shop, where each job needs storage space (a buffer requirement) during the entire time of its processing. The buffer requirement is determined by the duration of job’s first operation. The goal is to minimise the time needed for the completion of all jobs. This scheduling problem is NP-hard in the strong sense even for very restricted cases such as the case with a given order of jobs processing on one of the machines. The paper contributes to the efforts of establishing the borderline between the NP-hard and polynomial-time solvable cases by proving that there exists a polynomial-time algorithm which constructs an optimal schedule if the duration of each operation does not exceed one-fifth of the buffer capacity. The presented polynomial-time algorithm is used as a basis for a heuristic for the general case. This heuristic is complemented by a Lagrangian relaxation based heuristic and a bin-packing based constructive heuristic. The heuristics are tested by computational experiments.
Please use this identifier to cite or link to this item: