The application of search heuristics to the single machine early/tardy scheduling problem

Abstract

Just-In-Time manufacturing aims to reduce waste within an organisation, by focusing on completing orders at the time requested by customers. Failure to complete orders at the time specified causes the organisation to incur additional costs. The Just-In-Time environment has introduced complexities for scheduling which have been modelled by the Single Machine, Early/Tardy Machine Scheduling problem. Research to date has concentrated on models with assumptions such as the use of a single due date for all jobs or restrictions on early/tardy penalties. This research uses a generalised model which makes no such assumptions. The use of three popular ‘intelligent’ search techniques: Simulated Annealing, Genetic Algorithms and Tabu Search are investigated as possible solution techniques. The properties of the common due date, early/tardy scheduling problem enable schedules to be defined from early/tardy job specifications - which state whether individual jobs are scheduled earlier or later than requested. Search techniques can then be applied using an early/tardy job specification solution space rather than the sequence of jobs solution space. Experiments found that the former was more efficient. The properties of the common due date problem are generalised for the distinct due date problem so that a distinct due date schedule can also be defined from early/tardy job specifications, however, this is only possible with the use of a heuristic. By incorporating an early/tardy heuristic into a search, the early/tardy job specification solution space can be used in a search technique. Two early/tardy heuristics are developed, one being a construction based heuristics, the other based on a principle of conflict resolution. Both of these heuristics, unlike any other heuristic for this problem, determine the sequence and timing of each job simultaneously. Experiments demonstrated that the early/tardy heuristics could find good quality solutions, however, search techniques based on the standard sequence of jobs solution space found better solutions. On larger sized problems, searches based on the early/tardy heuristic made large initial gains but little subsequent progress. Hybrid techniques which used both the heuristic solution space and the sequence of jobs solution space were found to produce the best results. Of the search techniques, Tabu Search was found to consistently produce better results than Simulated Annealing and Genetic Algorithms. Experiments also found that a Tabu Search with an early/tardy heuristic-based diversification strategy was the least sensitive to the starting point used by the search. A final experiment found that if an error in the earliness and tardiness penalties is within the range of -25% and 20%, there is unlikely to be a significant difference in the solution quality.