The two‐machine permutation flow shop with state‐dependent processing times

E. Wagneur and C. Sriskandarajah

Naval Research Logistics (NRL), 1993, vol. 40, issue 5, 697-717

Abstract: If the processing time of each job in a flow shop also depends on the time spent prior to processing, then the choice of a sequence influences processing times. This nonstandard scheduling problem is studied here for the minimum makespan schedule in a flow shop with two machines. The problem is NP‐hard in the strong sense and already contains the main features of the general case [10]. Restricting to the case of permutation schedules, we first determine the optimal release times of the jobs for a given sequence. Permutation schedules are evaluated for this optimal policy, and the scheduling problem is solved using branch‐and‐bound techniques. We also show the surprising result that the optimal schedule may not be a permutation schedule. Numerical results on randomly generated data are provided for permutation schedules. Our numerical results confirm our preliminary study [10] that fairly good approximate solutions can efficiently be obtained in the case of limited computing time using the heuristics due to Gilmore and Gomory [7]. © 1993 John Wiley & Sons, Inc.

Date: 1993
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199308)40:53.0.CO;2-V

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:40:y:1993:i:5:p:697-717

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().