Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization
| Autor: | Arthur Kramer, Manuel Iori, Philippe Lacomme |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), DOREAU, Bastien |
| Rok vydání: | 2021 |
| Předmět: |
Parallel machines
Mathematical optimization Information Systems and Management [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO] General Computer Science Family setup times Mathematical formulations Scheduling Weighted completion time Computer science Computation 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research Industrial and Manufacturing Engineering Scheduling (computing) 0502 economics and business 050210 logistics & transportation 021103 operations research Heuristic 05 social sciences [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Modeling and Simulation Minification Completion time |
| Zdroj: | EURO/ALIO International Conference 2018 on Applied Combinatorial Optimization EURO/ALIO International Conference 2018 on Applied Combinatorial Optimization, 2018, Bologna, Italy HAL |
| ISSN: | 0377-2217 |
| Popis: | This paper addresses the parallel machine scheduling problem with family dependent setup times and total weighted completion time minimization. In this problem, when two jobs j and k are scheduled consecutively on the same machine, a setup time is performed between the finishing time of j and the starting time of k if and only if j and k belong to different families. The problem is strongly NP -hard and is commonly addressed in the literature by heuristic approaches and by branch-and-bound algorithms. Achieving proven optimal solution is a challenging task even for small size instances. Our contribution is to introduce five novel mixed integer linear programs based on concepts derived from one-commodity, arc-flow and set covering formulations. Numerical experiments on more than 13000 benchmark instances show that one of the arc-flow models and the set covering model are quite efficient, as they provide on average better solutions than state-of-the-art approaches, with shorter computation times, and solve to proven optimality a large number of open instances from the literature. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect