Minimizing makespan of Personal Scheduling problem in available time-windows with split-min and setup-time constraints



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.


splitting-job; available time-window; setup-time; assignment approach; SPT/LPT rule; tabu search algorithm

Full Text:



M.T. Almeida and M. Centeno. A composite heuristic for the single machine early/tardy job scheduling problem. Computers & Operations Research, 25(7-8):625-635, 1998.

Peter Brucker. Scheduling Algorithms - Fifth Edition. Springer, 2007.

B. Fleischmann and H. Meyr. The general lotsizing and scheduling problem. OR Spektrum, 19(1):11-21, 1997.

S. Raut, S. Swami, and J.N.D. Gupta. Scheduling a capacitated single machine with time deteriorating job values. International Journal of Production Economics, 114:769-780, 2008.

S. Gawiejnowicz and A. Kononov. Complexity and approximability of scheduling resumable proportionally deteriorating jobs. European Journal of Operational Research, 200:305-308, 2010.

D.Q. Tran, N. Huynh Tuong, G.L. Hoang Ngoc, T.L. Mai, T.L. Tran, Q.T. Mai, and T.T. Quan. A personal scheduling system using genetic algorithm and simple natural language processing for usability. In Multi-disciplinary International Workshop on Artificial Intelligence (MIWAI’2010),

Mahasarakham, Thailand, 2010.

S. Hartmann and D. Briskorn. A survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 207:1-14, 2010.

Jixiang Yang. Complexity analysis of new task allocation problem using network flow method on multicore clusters. Mathematical Problems in Engineering, Hindawi Publishing Corporation, 2014:1-7, 2014.

S. Zaman and D. Grosu. Combinatorial auction-based allocation of virtual machine instances in clouds. Journal of Parallel and Distributed Computing, 73(4):495-508, 2013.

R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5:287-326,

V.H. Nguyen, N. Huynh Tuong, H.P. Nguyen, and T.H. Nguyen. Single-machine scheduling with splitable jobs and availability constraints. REV Journal on Electronics and Communications, 3(1-2):21-27, 2013.

V.H. Nguyen, N. Huynh Tuong, V.H. Tran, and N. Thoai. An milp-based makespan minimization model for single-machine scheduling problem with splitable jobs and availability constraints. In International Conference on Computing, Management and Telecommunications (ComManTel), pages 397-400, Ho Chi Minh, Vietnam, 2013.

DOI: Display counter: Abstract : 183 views. PDF : 122 views.

Journal of Computer Science and Cybernetics ISSN: 1813-9663

Published by Vietnam Academy of Science and Technology