Proportionate flow shop with controllable processing times

✍ Scribed by T. C. Edwin Cheng; Natalia Shakhlevich

• Publisher: Springer US
• Year: 1999
• Tongue: English
• Weight: 122 KB
• Volume: 2
• Category: Article
• ISSN: 1094-6136
• DOI: 10.1002/(sici)1099-1425(199911/12)2:6<253::aid-jos30>3.0.co;2-r

✦ Synopsis

This paper considers a special class of ow-shop problems, known as the proportionate ow shop. In such a shop, each job ows through the machines in the same order and has equal processing times on the machines. The processing times of di erent jobs may be di erent. It is assumed that all operations of a job may be compressed by the same amount which will incur an additional cost. The objective is to minimize the makespan of the schedule together with a compression cost function which is non-decreasing with respect to the amount of compression. For a bicriterion problem of minimizing the makespan and a linear cost function, an O(n log n) algorithm is developed to construct the Pareto optimal set. For a single criterion problem, an O(n 2 ) algorithm is developed to minimize the sum of the makespan and compression cost.