Algorithms for the single machine total weighted completion time scheduling problem with release times and sequence-dependent setups

作者：Chou Fuh Der^*; Wang Hui Mei; Chang Tzu Yun

来源：International Journal of Advanced Manufacturing Technology, 2009, 43(7-8): 810-821.

DOI：10.1007/s00170-008-1762-4

• Sequence-dependent setup time
• Total weighted completion time
• Scheduling
• Algorithm
• Heuristic

This paper considers the problem of scheduling n jobs on a single machine to minimize the total weighted completion time in the presence of sequence-dependent setup times and release times. To the best of our knowledge, little research has been devoted to this scheduling problem. Therefore, we developed two exact algorithms, including a constraint programming model and a branch-and-bound method for small problems. The obtained optimal solutions can be used as a benchmark for evaluating the performance of heuristics. With the complexity in mind, two heuristics, including a best index dispatch ( BID) and a modified weighted shortest processing time (MWSPT) based on non-delay concepts are also proposed for large problems. The time complexities of the two proposed heuristics are O(n(4)) and O(n(3)), respectively. The computational results showed that the branch-and-bound method could solve most instances with 40 jobs under the time limit of 7,200 s. The BID heuristic is superior to the MWSPT in solution quality, although both can efficiently and effectively obtain near-optimal solutions for large instances.

• 出版日期2009-8