Optimization Online


New hybrid optimization algorithms for machine scheduling problems

Yunpeng Pan (yunpeng.pan***at***gmail.com)
Leyuan Shi (leyuan***at***engr.wisc.edu)

Abstract: Dynamic programming, branch-and-bound, and constraint programming are the standard solution principles for finding optimal solutions to machine scheduling problems. We propose a new hybrid optimization framework that integrates all three methodologies. The hybrid framework leads to powerful solution procedures. We demonstrate our approach through the optimal solution of the single-machine total weighted completion time scheduling problem subject to release dates, which is known to be strongly NP-hard. Extensive computational experiments indicate that new hybrid algorithms use orders of magnitude less storage than dynamic programming, and yet can still reap the full benefit of the dynamic programming property inherent to the problem. We are able to solve to optimality all 1,900 instances with up to 200 jobs. This more than doubles the size of problems that can be solved optimally by the previous best algorithm running on the latest computing hardware.

Keywords: dynamic programming, branch-and-bound, constraint programming

Category 1: Other Topics (Dynamic Programming )

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

Citation: IEEE Trans. on Automation Science and Engineering. Accepted.

Download: [PDF]

Entry Submitted: 03/29/2005
Entry Accepted: 03/30/2005
Entry Last Modified: 12/03/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