Problem F2@?C"m"a"x with forbidden jobs in the first or last position is easy [An article from: European Journal of Operational Research]

This digital document is a journal article from European Journal of Operational Research, published by Elsevier in 2007. The article is delivered in HTML format and is available in your Amazon.com Media Library immediately after purchase. You can view it with any web browser.

Description:
Saadani et al. [N.E.H. Saadani, P. Baptiste, M. Moalla, The simple F2@?C"m"a"x with forbidden tasks in first or last position: A problem more complex that it seems, European Journal of Operational Research 161 (2005) 21-31] studied the classical n-job flow shop scheduling problem F2@?C"m"a"x 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 [S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly 1 (1954) 61-68] permutation. The problem was solved in O(n^2) 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(nlogn) time, the problem in Saadani et al. (2005) can be solved in O(nlogn) time as well.