Optimization Online


Exponential neighborhood search for a parallel machine scheduling problem

Y.A. Rios Solis (yasmin.rios***at***lip6.fr)
F. Sourd (francis.sourd***at***lip6.fr)

Abstract: We consider the parallel machine scheduling problem where jobs have different earliness-tardiness penalties and a restrictive common due date. This problem is NP-hard in the strong sense. In this paper we define an exponential size neighborhood for this problem and prove that finding the local minimum in it is an NP-hard problem. The main contribution of this paper is to propose a pseudo-polynomial algorithm that finds the best solution of the exponential neighborhood. Additionally, we present some computational results.

Keywords: Parallel machine scheduling; Earliness-tardiness penalties; Large neighborhood search; Dynamic programming

Category 1: Applications -- OR and Management Sciences

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

Citation: Final version in Computers & Operations Research, Available online


Entry Submitted: 05/23/2006
Entry Accepted: 05/23/2006
Entry Last Modified: 05/28/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