Advanced Search

Query:

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

Format:

Display: entries per page entries

Zbl 1009.90047
Gharbi, Anis; Haouari, Mohamed
Minimizing makespan on parallel machines subject to release dates and delivery times. (English)
[J] J. Sched. 5, No.4, 329-355 (2002). ISSN 1094-6136; ISSN 1099-1425/e

Summary: We consider the problem of minimizing the makespan on identical parallel machines subject to release dates and delivery times. The objective of this paper is to develop exact branch-and-bound algorithms to solve this strongly NP-hard problem. A preprocessing algorithm is devised to speed up the convergence of the proposed algorithms, and a new tight bounding scheme is introduced. The search tree is also reduced using a polynomial selection algorithm. Extensive computational experiments show that instances with up to 300 jobs can be solved exactly in a moderate CPU time.

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

Keywords: scheduling; identical parallel machines; makespan; release dates; delivery times; branch-and-bound

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]