Optimization Online


Dual constrained single machine sequencing to minimize total weighted completion time

Yunpeng Pan (yunpeng.pan***at***gmail.com)
Leyuan Shi (leyuan***at***engr.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


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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society