Near-optimal solutions of large-scale Single Machine Scheduling Problems

Pasquale Avella (avellaunisannio.it)
Maurizio Boccia (bocciacrmpa.unisa.it)
Bernardo D'Auria (dauriadiima.unisa.it)

Abstract: We present a lagrangean heuristic based on the time-indexed formulation of the Single Machine Scheduling Problem with Release Dates. We observe that lagrangian relaxation of job constraints leads to a Weighted Stable Set problem on an Interval Graph. The problem is polynomially solvable by a dynamic programming algorithm. Computational experience is reported on instances up to 400 jobs and maximum processing time 50.

Keywords: Single Machine Scheduling, Lagrangian relaxation, Interval Graphs

Category 1: Applications -- OR and Management Sciences (Production and Logistics )

Category 2: Combinatorial Optimization

Citation: Technical Report DIIMA - Università di Salerno, May 2002

Download:

Entry Submitted: 05/15/2002
Entry Accepted: 05/15/2002
Entry Last Modified: 09/08/2007

Modify/Update this entry