Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time - Mines Saint-Étienne Accéder directement au contenu
Article Dans Une Revue Computers and Operations Research Année : 2020

Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time

Résumé

This paper addresses the problem of scheduling a set of jobs that are released over the time on a set of identical parallel machines, aiming at the minimization of the total weighted completion time. This problem, referred to as P vertical bar r(j)vertical bar Sigma WjCj, is of great importance in practice, because it models a variety of real-life applications. Despite its importance, the P vertical bar r(j)vertical bar Sigma WjCj has not received much attention in the recent literature. In this work, we fill this gap by proposing mixed integer linear programs and a tailored branch-and-price algorithm. Our branch-and-price relies on the decomposition of an arc-flow formulation and on the use of efficient exact and heuristic methods for solving the pricing subproblem. Computational experiments carried out on a set of randomly generated instances prove that the proposed methods can solve to the proven optimality instances with up to 200 jobs and 10 machines, and provide very low gaps for larger instances

Dates et versions

emse-02747648 , version 1 (03-06-2020)

Identifiants

Citer

Arthur Kramer, Mauro Dell'Amico, Dominique Feillet, Manuel Iori. Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time. Computers and Operations Research, 2020, 123, pp.105018. ⟨10.1016/j.cor.2020.105018⟩. ⟨emse-02747648⟩
75 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More