Makespan minimization subject to flowtime optimality on identical parallel machines |
| |
| Affiliation: | 1. Leiden University Medical Center, Department of Surgery, Albinusdreef 2, Postbus 9600, 2300 RC Leiden, the Netherlands;2. Leiden University Medical Center, Department of Medical Oncology, Albinusdreef 2, Postbus 9600, 2300 RC Leiden, the Netherlands;3. Belgian Cancer Registry, Koningsstraat 215 bus 7, 1210 Brussels, Belgium;4. Oslo University Hospital, Department of Oncology, PO 4953 Nydalen, 0424 Oslo, Norway;5. Stavanger University Hospital, Stavanger, Department of Gastrointestinal Surgery, Postboks 8100, 4068 Stavanger, Norway;6. University of Bergen, Department of Clinical Medicine, Jonas Lies veg 87, N-5021 Bergen, Norway;7. Karolinska Institutet, Department of Molecular Medicine and Surgery, Solnavägen 1, 171 77 Stockholm, Sweden;8. Umeå University, The Biobank Research Unit, 901 87 Umeå, Sweden;9. Reinier de Graaf Hospital, Department of Surgery, Reinier de Graafweg 5, Postbus 5011, 2600 GA Delft, the Netherlands |
| |
| Abstract: | We consider the identical parallel machine problem with makespan minimization subject to minimum total flowtime. First, we develop an optimal algorithm to the identical parallel machine problem with the objective of minimizing makespan. To improve the computational efficiency, two implementation techniques, the lower bound calculation and the job replacement rule, are applied. Based on the algorithm, an optimal algorithm, using new lower bounds, to the considered problem is developed. The result of this study can also be used to solve the bicriteria problem of minimizing the weighted sum of makespan and mean flowtime. Computational experiments are conducted up to six machines and 1000 jobs. Although the proposed algorithm has an exponential time complexity, the computational results show that it is efficient to find the optimal solution. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
