Optimization Online


New solution approaches to the general single machine earliness-tardiness problem

Hoksung Yau (yau***at***cae.wisc.edu)
Yunpeng Pan (yunpeng.pan***at***gmail.com)
Leyuan Shi (Leyuan***at***engr.wisc.edu)

Abstract: This paper addresses the general single-machine earliness-tardiness problem with distinct release dates, due dates, and unit costs. The aim of this research is to obtain an exact nonpreemptive solution in which machine idle time is allowed. In a hybrid approach, we formulate and then solve the problem using dynamic programming (DP) while incorporating techniques from branch-and-bound (BB). This approach (DP-BB) has been proven to be effective in solving certain types of scheduling problems. We further propose a new adaptation of the approach to a general problem with a nonregular objective function. To address some shortcomings of DP-BB, we also apply a branch-and-bound approach in which partial dynamic programming dominance (BB-PDP) is exploited. Computational experiments were conducted with randomly generated test instances in order to evaluate the effectiveness of the two approaches. The results clearly showed that our new approaches can solve all the instances with up to 40 jobs and most of the instances with 50 jobs, which outperforms those frequently used approaches in scheduling research.

Keywords: single-machine, earliness-tardiness, branch-and-bound, dynamic

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

Category 2: Applications -- OR and Management Sciences (Production and Logistics )

Category 3: Other Topics (Dynamic Programming )

Citation: Forthcoming in IEEE Trans. on Automation Science and Engineering

Download: [PDF]

Entry Submitted: 03/07/2006
Entry Accepted: 03/07/2006
Entry Last Modified: 01/06/2007

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