Exponential neighborhood search for a parallel machine scheduling problem

Y.A. Rios Solis (yasmin.rioslip6.fr)
F. Sourd (francis.sourdlip6.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 to appear in Computers & Operations Research. Available online

Download: [PDF]

Entry Submitted: 05/23/2006
Entry Accepted: 05/23/2006
Entry Last Modified: 09/18/2007

Modify/Update this entry