Preemption in single machine earliness/tardiness scheduling

Bülbül, Kerem and Kaminsky, Philip and Yano, Candace (2007) Preemption in single machine earliness/tardiness scheduling. Journal of scheduling, 10 (4-5). pp. 271-292. ISSN 1094-6136 (Print) 1099-1425 (Online)

This is the latest version of this item.

[img]PDF - Registered users only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://dx.doi.org/10.1007/s10951-007-0028-6


We consider a single machine earliness/tardiness scheduling problem with general weights, ready times and due dates. Our solution approach is based on a time-indexed preemptive relaxation of the problem. For the objective function of this relaxation, we characterize cost coe±cients that are the best among those with a piecewise linear structure with two segments. From the solution to the relaxation with these best objective function coe±cients, we generate feasible solutions for the original non-preemptive problem. We report extensive computational results demonstrating the speed and effectiveness of this approach.

Item Type:Article
Uncontrolled Keywords:single-machine scheduling; earliness; tardiness; preemption; transportation problem
Subjects:T Technology > T Technology (General)
ID Code:5383
Deposited By:Kerem Bülbül
Deposited On:09 Oct 2007 23:51
Last Modified:25 May 2011 14:04

Available Versions of this Item

Repository Staff Only: item control page