The one-machine sequencing problem

✍ Scribed by Jacques Carlier

• Book ID: 104339139
• Publisher: Elsevier Science
• Year: 1982
• Tongue: English
• Weight: 267 KB
• Volume: 11
• Category: Article
• ISSN: 0377-2217
• DOI: 10.1016/s0377-2217(82)80007-6

✦ Synopsis

Let M I and M~ be non-bonleneck macbi~les and M, ¢1 bonleneek machine proeessin~ only one job ;11 ~ dine, Suppose thai n jnbs have to be processed on M I. M: and M11in thai order) and lob i has to spend a time ~1, on M~, d, on M: and q~ on M3; we Wahl to minimize the nlakuspan.

This problem is important since its rew,~lution provides a bound on tile makespan of complicated systems such as job shops. It is NP-hard in the strong sense, However. etficienl branch and bound metb~s exi,~l lind we describe one of them, Our bound for the tree-search is very ch~s¢ to the bound used by Florian et al., but the principle of branching is quite different. At every node. we construct by an O(n log n) algorithm a Schrage schedule; then we define a critical job c, a critical set J and consider two subsets of schedules; the ~chedute,~ when ,, precedes every job of J and the scltedule~ when t ~ follows every job of J. We give Ihe results of this method and prove that the difference belween the optimum and the Schrase schedule is less than d,.