Skip to Main content Skip to Navigation
Journal articles

Parallel machine scheduling to minimize total tardiness

Abstract : This paper addresses, using an exact method, the identical parallel machine scheduling problem to minimize total tardiness. In this problem, a set of jobs has to be scheduled, without preemption, on identical parallel machines. Each machine is able to treat only one job at a time. In order to prune the search tree, dominance properties are proved and lower and upper bounding schemes are proposed. A branch and bound (BAB) algorithm is developed taking into account these theoretical properties, lower and upper bounds. This BAB algorithm has been tested on a large set of randomly generated medium-sized problems. Computational results demonstrate the effectiveness of our approach over existing methods in the literature.
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02501003
Contributor : Daniel Gavrysiak <>
Submitted on : Friday, March 6, 2020 - 2:39:46 PM
Last modification on : Saturday, March 7, 2020 - 1:36:38 AM

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Farouk Yalaoui, Chengbin Chu. Parallel machine scheduling to minimize total tardiness. International Journal of Production Economics, Elsevier, 2002, 76 (3), pp.265-279. ⟨10.1016/S0925-5273(01)00175-X⟩. ⟨hal-02501003⟩

Share

Metrics

Record views

41