A polynomial algorithm for lot-size scheduling of two type tasks

✍ Scribed by Mikhail Y. Kovalyov; Marcus Pattloch; Günter Schmidt

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 94 KB
• Volume: 83
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(01)00331-3

✦ Synopsis

We study the problem of scheduling unit time tasks of two types on m parallel identical machines. For each type, given numbers of tasks are required to be completed by the specified deadlines. These tasks leave the system at the deadlines. The in-process inventory capacities are given. The objective is to construct a schedule that minimizes the number of changeovers occurring between the tasks of different types. This problem arises, for instance, in the production of gear-boxes on transfer lines and in the tobacco industry. Pattloch and Schmidt [Discrete Appl. Math. 65 (1996) 409-419] give an O(mH ) algorithm to solve this problem where H is the latest deadline. We present here a modification of that algorithm with O(K min{K, m}) time complexity where K is the number of deadlines.