Optimization Online


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

Pasquale Avella (avella***at***unisannio.it)
Maurizio Boccia (boccia***at***crmpa.unisa.it)
Bernardo D'Auria (dauria***at***diima.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


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

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