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

What is it about?

Saadani et al. (European Journal of Operational Research 161, 2005, 21–31) 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(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(n log n) time, the problem in Saadani et al. (2005) can be solved in O(n log n) time as well.

Featured Image