Optimization Online


Preemptive scheduling with position costs

Francis Sourd (Francis.Sourd***at***lip6.fr)

Abstract: This paper is devoted to basic scheduling problems in which the scheduling cost of a job is not a function of its completion time. Instead, the cost is derived from the integration of a cost function over the time intervals on which the job is processed. This criterion is specially meaningful when job preemption is allowed. Polynomial algorithms are presented to solve some special cases including a one-machine problem with a common due date and a two-machine problem with linear nondecreasing cost functions.

Keywords: Scheduling algorithm, preemption, primal-dual algorithm, dynamic programming.

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

Citation: Algorithmic Operations Research 1(2)


Entry Submitted: 04/29/2005
Entry Accepted: 04/29/2005
Entry Last Modified: 07/04/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