Optimal solutions for unrelated parallel machines scheduling problems using convex quadratic reformulations

M.-C. Plateau (mc.plateaucnam.fr)
Y.A. Rios-Solis (yasmin.rioslip6.fr)

Abstract: We consider the unrelated parallel machines scheduling problem where jobs have earliness and tardiness penalties and a common due date. We formulate this problem and some of its variants as 0-1 programs with quadratic objective function subject to linear constraints. The main contribution of this paper is to use and develop different convex reformulations to solve exactly the quadratic programs. We show that this new link between quadratic programming and scheduling can be theoretically and practically interesting.

Keywords: Scheduling, Common due date, Quadratic programming

Category 1: Applications -- OR and Management Sciences

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

Category 3: Nonlinear Optimization (Quadratic Programming )

Citation: Submitted article. M.-C. Plateau CEDRIC -CNAM 292 rue Saint Martin, 75003 Paris, France Y.A. Rios-Solis LIP6 - University Pierre et Marie Curie 4 Place Jussieu, 75252 Paris Cedex 05, France

Download: [PDF]

Entry Submitted: 09/19/2007
Entry Accepted: 09/19/2007
Entry Last Modified: 01/23/2008

Modify/Update this entry