Open AccessMinimizing makespan of Personal Scheduling problem in available time-windows with split-min and setup-time constraints
Author(s) -
Sơn Hồng Trang,
Nguyen Ngoc Tri Huynh,
Lăng Văn Trần
Publication year - 2018
Publication title -
journal of computer science and cybernetics (vietnam academy of science and technology)/journal of computer science and cybernetics
Language(s) - English
Resource type - Journals
eISSN - 2815-5939
pISSN - 1813-9663
DOI - 10.15625/1813-9663/34/2/12667
Subject(s) - job shop scheduling , heuristics , mathematical optimization , tabu search , computer science , scheduling (production processes) , schedule , nurse scheduling problem , reduction (mathematics) , upper and lower bounds , mathematics , flow shop scheduling , mathematical analysis , geometry , operating system
This paper deals with personal scheduling problem in available time-windows with split-min and setup-time constraints. The jobs are splitable into sub-jobs and a common lower bound on the size of each sub-job is imposed. The objective function aims to find a feasible schedule that minimizes the maximum completion time of all jobs. The proposed scheduling problem was proved to be strongly NP-hard by a reduction to 3-SAT problem in the preliminary results. We propose in this paper an exact method based on MILP model to find optimal solution, some heuristics to find feasible solution and a meta-heuristic based on tabu search algorithm to find good solution. The computational results show the performance of proposed exact method, some heuristics and tabu search algorithm.