Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0953.90029
Lancia, Giuseppe
Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the makespan. (English)
[J] Eur. J. Oper. Res. 120, No.2, 277-288 (2000). ISSN 0377-2217

Summary: This paper deals with the problem of assigning a set of $n$ jobs, with release dates and tails, to either one of two unrelated parallel machines and scheduling each machine so that the makespan is minimized. This problem will be denoted by $R2|r_i,q_i|C_{\max}$. The model generalizes the problem on one machine $1|r_i,q_i|C_{\max}$, for which a very efficient algorithm exists. In this paper we describe a branch and bound procedure for solving the two machine problem which is partly based on Carlier's algorithm for the $1|r_i,q_i|C_{\max}$. An $O(n\log n)$ heuristic procedure for generating feasible solutions is given. Computational results are reported.

MSC 2000:: *90B35 Scheduling theory
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
68M20 Performance evaluation of computer systems, etc.

Keywords: scheduling theory; branch and bound; parallel machines; makespan

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]