Neighborhood search for solving personal scheduling problem in available time windows with split-min and deadline constraints

Son Hong Trang, Lang Van Tran, Nguyen Tuong Huynh


The scheduling of individual jobs with certain constraints so that efficiency is a matter of concern. Jobs have deadlines to complete, can be broken down but not too small, and will be scheduled into some available time windows. The goal of the problem is to find a solution so that all jobs are completed as soon as possible. This problem is proved to be a strongly $NP$-hard problem. The implementation of the proposed MILP model using a CPLEX solver was also conducted to determine the optimal solution for the small-size dataset. For large-size dataset, heuristic algorithms are recommended such as First Come First Served (FCFS), Earliest Deadline (EDL), and neighborhood search including  Stochastic Hill Climbing (SHC), Random Restart Hill Climbing (RRHC), Simulated Annealing (SA) to determine a good solution in an acceptable time. Experimental results will present in detail the performance among the groups of exact, heuristic, and neighborhood search methods.

Full Text:



R. Graham, E. Lawler, J. Lenstra, and A. R. Kan, "Optimization and approximation in deterministic sequencing and scheduling: a survey", Annals of Discrete Mathematics, vol. 5, pp. 287–326, 1979.

V. Nguyen, N. H. Tuong, H. Nguyen, and T. Nguyen, "Single-machine scheduling with splitable jobs and availability constraints", REV Journal on Electronics and Communications, vol. 3, no. 1-2, pp. 21–27, 2013.

V. Nguyen, N. H. Tuong, V. Tran, and N. Thoai, "An milp-based makespan minimization model for single-machine scheduling problem with splitable jobs and availability constraints", in International Confer- ence on Computing, Management and Telecommunications (ComMan- Tel), Ho Chi Minh, Vietnam, 2013, pp. 397–400.

F. Sourd, "Dynasearch for the earliness-tardiness scheduling problem with release dates and setup constraints", Operations Research Letters, vol. 34, no. 5, pp. 591–598, 2006.

Q. C. Ta, J.-C. Billaut, and J.-L. Bouquard, "Heuristic algorithms to minimize the total tardiness in a flow shop production and outbound distribution scheduling problem", in 2015 International Conference on Industrial Engineering and Systems Management (IESM), Seville, Spain, 21-23 Oct. 2015.

J. Pearl, Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Longman Publishing Co., Inc., 1984.

S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, 3rd ed. Prentice Hall Press, 2009, ch. Beyond Classical Search.

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by simulated annealing", Science, vol. 220, no. 4598, pp. 671–680, 1983.

A. M. A. Hariri and C. N. Potts, "Single machine scheduling with deadlines to minimize the weighted number of tardy jobs", Management Science, vol. 40, no. 12, pp. 1712–1719, 1994.

P. Baptiste, F. Della Croce, A. Grosso, and V. T’Kindt, "Sequencing a single machine with due dates and deadlines: An ilp-based approach to solve very large instances", Journal of Scheduling, vol. 13, no. 1, pp. 39–47, 2010.

I. L. O. Geneva, "Working time in the twenty-first century", International Labour Organization, 2011.

P. Laarhoven, Theoretical and Computational Aspects of Simulated Annealing. Erasmus Universiteit Rotterdam, 1988.


Copyright (c) 2022 REV Journal on Electronics and Communications

ISSN: 1859-378X

Copyright © 2011-2024
Radio and Electronics Association of Vietnam
All rights reserved