Dual constrained single machine sequencing to minimize total weighted completion time

作者：Pan YP^*; Shi LY

来源：IEEE Transactions on Automation Science and Engineering, 2005, 2(4): 344-357.

DOI：10.1109/TASE.2005.853474

• branch and bound
• isotonic regression
• scheduling
• timetabling
• weighted completion time (WCT)

We study a single-machine sequencing problem with both release dates and deadlines to minimize the total weighted completion time. We propose a branch-and-bound, algorithm for this problem. The algorithm exploits an effective lower bound and a dynamic programming dominance technique. As a byproduct of the lower bound, we have developed a new algorithm for the generalized isotonic regression problem; the algorithm can also be used as an O (n log n) -time timetabling routine in earliness-tardiness scheduling. Extensive computational experiments indicate that the proposed branch-and-bound algorithm competes favorably with a dynamic programming procedure.

• 出版日期2005-10