Optimization Online


Fast Neighborhood Search For The Single Machine Earliness-Tardiness Scheduling Problem

Safia Kedad-Sidhoum(safia.kedad-sidhoum***at***lip6.fr)
Francis Sourd(francis.sourd***at***lip6.fr)

Abstract: This paper addresses the one machine scheduling problem in which $n$ jobs have distinct due dates with earliness and tardiness costs. Fast neighborhoods are proposed for the problem. They are based on a block representation of the schedule and can be computed in $O(n^2)$. A timing operator is presented as well as swap and extract-and-reinsert neighborhoods. They are used in an iterated local search framework. Two types of perturbations are developed based respectively on random swaps and earliness and tardiness costs. Computational results show that very good solutions for instances with significantly more than 100 jobs can be derived in a few seconds.

Keywords: Machine scheduling, earliness-tardiness, neighborhood, iterated local search

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


Download: [PDF]

Entry Submitted: 06/23/2008
Entry Accepted: 06/23/2008
Entry Last Modified: 06/23/2008

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