Solving the Unrelated Parallel Machine Scheduling Problem with Setups Using Late Acceptance Hill Climbing - Université de technologie de Troyes Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

Solving the Unrelated Parallel Machine Scheduling Problem with Setups Using Late Acceptance Hill Climbing

Résumé

We propose a Late Acceptance Hill-Climbing (LAHC) approach to solve the unrelated parallel machine scheduling problem with sequence and machine-dependent setup times. LAHC is an iterative list-based single-parameter metaheuristic that exploits information from one iteration to another to decide whether the new candidate solution is accepted. A dynamic job insertion heuristic is used to generate initial solutions. Three local search operators (job swap between different machines, job swap within the same machine and job insertion from one machine to another) are used to improve solutions. A Variable Neighborhood Descent (VND) method is proposed to improve the candidate solution and accelerate the convergence of the LAHC. To the best of our knowledge, this is the first application of LAHC to parallel machine scheduling problems. We evaluate and compare the proposed algorithm against the best methods from the literature. Having a single parameter which makes it simpler than all existing approaches, the proposed method outperforms existing methods on most of the tested benchmark instances.
Fichier non déposé

Dates et versions

hal-02502174 , version 1 (09-03-2020)

Identifiants

Citer

Mourad Terzi, Taha Arbaoui, Farouk Yalaoui, Karima Benatchba. Solving the Unrelated Parallel Machine Scheduling Problem with Setups Using Late Acceptance Hill Climbing. 12th Asian Conference on Intelligent Information and Database Systems, ACIIDS 2020, Mar 2020, Phuket, Thailand. pp.249-258, ⟨10.1007/978-3-030-41964-6_22⟩. ⟨hal-02502174⟩

Collections

CNRS UTT LOSI
76 Consultations
3 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More