Resolution for bounded-splitting jobs scheduling problem on a single machine in available time-windows

• Published in: Journal of ambient intelligence and humanized computing 2021-01, Vol.12 (1), p.1179-1196
• Main Authors: Son, Trang Hong, Van Lang, Tran, Huynh-Tuong, Nguyen, Soukhal, Ameur
• Format: Article
• Language: English
• Subjects: Artificial Intelligence; Availability; Completion time; Computational Intelligence; Computer Science; Engineering; Genetic algorithms; Heuristic; Heuristic methods; Integer programming; Job shops; Linear programming; Lower bounds; Mathematical models; Mathematical programming; Mixed integer; Operations Research; Original Research; Preventive maintenance; Production planning; Robotics and Automation; Scheduling; Tabu search; User Interfaces and Human Computer Interaction; Windows (intervals)
• ISSN: 1868-5137; 1868-5145
• DOI: 10.1007/s12652-020-02162-0

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.