Minimizing makespan of Personal Scheduling problem in available time-windows with split-min and setup-time constraints
Author affiliations
DOI:
https://doi.org/10.15625/1813-9663/34/2/12667Keywords:
splitting-job, available time-window, setup-time, assignment approach, SPT/LPT rule, tabu search algorithmAbstract
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.
Metrics
References
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.
Downloads
Published
How to Cite
Issue
Section
License
1. We hereby assign copyright of our article (the Work) in all forms of media, whether now known or hereafter developed, to the Journal of Computer Science and Cybernetics. We understand that the Journal of Computer Science and Cybernetics will act on my/our behalf to publish, reproduce, distribute and transmit the Work.2. This assignment of copyright to the Journal of Computer Science and Cybernetics is done so on the understanding that permission from the Journal of Computer Science and Cybernetics is not required for me/us to reproduce, republish or distribute copies of the Work in whole or in part. We will ensure that all such copies carry a notice of copyright ownership and reference to the original journal publication.
3. We warrant that the Work is our results and has not been published before in its current or a substantially similar form and is not under consideration for another publication, does not contain any unlawful statements and does not infringe any existing copyright.
4. We also warrant that We have obtained the necessary permission from the copyright holder/s to reproduce in the article any materials including tables, diagrams or photographs not owned by me/us.
