Duality-based algorithms for scheduling on unrelated parallel machines

S.L. van de Velde

Research output: Contribution to journalArticleAcademicpeer-review

132 Downloads (Pure)


We consider the following parallel machine scheduling problem. Each of n independent jobs has to be scheduled on one of m unrelated parallel machines. The processing of job J[sub l] on machine Mi requires an uninterrupted period of positive length p[sub lj]. The objective is to find an assignment of jobs to machines so as to minimize the maximum Job completion time. The objective of this paper is to design practical algorithms for this NP-hard problem. We present an optimization algorithm and an approximation algorithm that are both based on surrogate relaxation and duality. The optimization algorithm solves quite large problems within reasonable time limits. The approximation algorithm is based upon a novel concept for iterative local search, in which the search direction is guided by surrogate multipliers.
Original languageEnglish
Pages (from-to)192-205
JournalORSA journal on computing
Issue number2
Publication statusPublished - 1993

Fingerprint Dive into the research topics of 'Duality-based algorithms for scheduling on unrelated parallel machines'. Together they form a unique fingerprint.

  • Cite this