Dual constrained single machine sequencing to minimize total weighted completion time

Yunpeng Pan (yunpeng.pangmail.com)
Leyuan Shi (leyuanengr.wisc.edu)

Abstract: 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(nlogn)-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.

Keywords: scheduling, isotonic regression, timetabling, branch-and-bound, weighted completion time

Category 1: Applications -- OR and Management Sciences (Scheduling )

Citation: IEEE Trans. on Automation Science and Engineering, Vol. 2, n. 4, pp. 344-357, 2005

Download:

Entry Submitted: 03/30/2005
Entry Accepted: 03/30/2005
Entry Last Modified: 08/10/2006

Modify/Update this entry