Skip to Main content Skip to Navigation
Conference papers

Branch and Bound and Dynamic Programming to Minimize the Total Completion Times on a Single Machine with Availability Constraints

Imed Kacem 1 Cherif Sadfi 1 Abdelkader El Kamel 2
1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels
ICD - Institut Charles Delaunay
2 LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Abstract : In this paper we consider the single machine scheduling problem with availability constraints in order to minimize the total completion times of jobs. We propose two exact approaches to solve the problem: a dynamic programming and a branch and bound method. The study of these approaches is carried out in this article and a concluding analysis based on several experimental results allows us to select the most suitable method according to the studied instance.
Keywords : Single machine scheduling Dynamic scheduling Heuristic algorithms Parallel machines Time factors Scheduling algorithm H infinity control Scheduling single machine availability constraint branch and bound dynamic programming
Document type :
Conference papers
Complete list of metadatas
https://hal-utt.archives-ouvertes.fr/hal-02491598
Contributor : Daniel Gavrysiak <>
Submitted on : Wednesday, February 26, 2020 - 11:32:35 AM
Last modification on : Tuesday, November 24, 2020 - 2:18:23 PM

Identifiers

Collections

LAGIS | ROSAS | UTT | CNRS

Citation

Imed Kacem, Cherif Sadfi, Abdelkader El Kamel. Branch and Bound and Dynamic Programming to Minimize the Total Completion Times on a Single Machine with Availability Constraints. 2005 IEEE International Conference on Systems, Man and Cybernetics, Oct 2005, Waikoloa, United States. pp.1657-1662, ⟨10.1109/ICSMC.2005.1571386⟩. ⟨hal-02491598⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

44