| Autor: |
Son, Trang Hong, Van Lang, Tran, Huynh-Tuong, Nguyen, Soukhal, Ameur |
| Zdroj: |
Journal of Ambient Intelligence & Humanized Computing; Jan2021, Vol. 12 Issue 1, p1179-1196, 18p |
| Abstrakt: |
This paper studies a single machine scheduling problem which machine-availability constraint is imposed. The jobs are splittable into sub-jobs and the size of each sub-job has a common lower bound. The objective aims to find an optimal scheduling solution that minimizes the maximum completion time for the whole set jobs. The scheduling problem was proved to be strongly NP-hard by a reduction from 3-Partition problem. In this paper, a general mixed-integer linear mathematical model is constructed based on some structurally optimal properties in the literature. Besides that we propose some effective heuristics concerned about assignment strategy such as assignment heuristic, heuristic based on shortest/longest processing time rules, heuristic based on max flow resolution, matching and assignment approach. In order to improve solution quality, we also propose to apply a combination between these proposed heuristics and metaheuristics such as tabu search and genetic algorithm. In addition, in the hope of achieving the better solutions in acceptable time, we introduce another approach called exact for subset-jobs matheuristic which is combined between mathematical programming and heuristic derived from single-attribute priority rule. Experimental results show the performance of proposed approximating approaches in comparing between them and the exact method based on the MILP model which is implemented by CPLEX solver. Among proposed effective algorithms, the matheuristic showed the superiority in terms of solution quality and execution time. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
Full text from SpringerLink