Branch-and-bound algorithms for minimizing total earliness and tardiness in a two-machine permutation flow shop with unforced idle allowed

• Type: Article in International Scientific Journal
• Date: 2019

Authors

Schaller, J (Author) Other; Jorge M S Valente (Author) FEP

Journal

Title: Computers and Operations Research

Vol. 109

Pages: 1-11

ISSN: 0305-0548

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 13 Citations

Scopus - 16 Citations

Other information

Authenticus ID: P-00Q-GGZ

DOI: 10.1016/j.cor.2019.04.017

Abstract (EN): The two-machine permutation flow shop scheduling problem with the objective of minimizing total earliness and tardiness is addressed. Unforced idle time can be used to complete jobs closer to their due dates. It is shown that unforced idle time only needs to be considered on the second machine. This result is then used to extend a lower bound and dominance conditions for the single-machine problem to the two-machine permutation flow shop problem. Two branch-and-bound algorithms are developed for the problem utilizing the lower bound and dominance conditions. The algorithms are tested using instances that represent a wide variety of conditions.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 11