Optimization Online


Approximate resolution of a resource-constrained scheduling problem

Renaud Sirdey (renauds***at***nortel.com)
Jacques Carlier (carlier***at***hds.utc.fr)
Dritan Nace (dnace***at***hds.utc.fr)

Abstract: This paper is devoted to the approximate resolution of a strongly NP-hard resource-constrained scheduling problem which arises in relation to the operability of certain high availability real time distributed systems. We present an algorithm based on the simulated annealing metaheuristic and, building on previous research on exact resolution methods, extensive computational results demonstrating its practical ability to produce acceptable solutions, in a precisely defined sense. Additionally, our experiments are in remarkable agreement with certain theoretical properties of our simulated annealing scheme. The paper is concluded by a short discussion on further research.

Keywords: combinatorial optimization, scheduling, simulated annealing, distributed systems.

Category 1: Combinatorial Optimization (Meta Heuristics )

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

Category 3: Applications -- OR and Management Sciences (Telecommunications )

Citation: Report n PB/BSC/INF/016550, Nortel GSM Access R&D, january 2006. To appear in the Journal of Heuristics.

Download: [Postscript]

Entry Submitted: 04/10/2006
Entry Accepted: 04/10/2006
Entry Last Modified: 04/03/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