Minimizing the total weighted completion time in a two-machine proportionate flow shop with different machine speeds

Abstract

In this paper, we consider the problem of minimizing the total weighted completion time in an n-job, two-machine proportionate flow shop, where job processing times are inversely proportional to machine speeds. We show that the problem is NP-complete. We provide a tight lower bound to an optimal objective value and show that the worst-case performance ratio of the weighted shortest processing time rule is less than 2. We propose heuristic procedures to find an approximate solution for the problem. A computational study on randomly generated test problems is conducted to investigate the performance of the proposed heuristics.

Keywords:

• Proportionate flow shop
• NP-complete
• Machine speed
• Worst-case performance ratio
• Weighted shortest processing time

Acknowledgement

This work was supported by the Soongsil University Research Fund.