Problem F2‖Cmax with forbidden jobs in the first or last position is easy

Problem F2‖Cmax with forbidden jobs in the first or last position is easy

0.00 Avg rating0 Votes
Article ID: iaor20084393
Country: Netherlands
Volume: 177
Issue: 2
Start Page Number: 1310
End Page Number: 1311
Publication Date: Mar 2007
Journal: European Journal of Operational Research
Authors: ,
Keywords: computational analysis
Abstract:

Saadani et al. studied the classical n-job flow shop scheduling problem F2‖Cmax with an additional constraint that some jobs cannot be placed in the first or last position. There exists an optimal job sequence for this problem, in which at most one job in the first or last position is deferred from its position in Johnson's permutation. The problem was solved in O(n2) time by enumerating all candidate job sequences. We suggest a simple O(n) algorithm for this problem provided that Johnson's permutation is given. Since Johnson's permutation can be obtained in O(n log n) time, the problem in Saadani et al. can be solved in O(n log n) time as well.

Reviews

Required fields are marked *. Your email address will not be published.