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

Abstract

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.