Novel Hybrid Algorithms for a Single Machine Scheduling Problem With an Overtime Constraint

In this paper, a single machine scheduling problem with an overtime constraint is studied. The objective is to minimise the total penalty cost defined as the sum of tardy, early, and overtime costs. Three novel hybrid algorithms that hybridise a new heuristic with genetic algorithm, tabu search, and simulated annealing, referred to as GAH, TSH, and SAH, are proposed to solve the problem. In each iteration of the proposed hybrid algorithms, a given metaheuristic is used to determine a sequence of jobs, whereas a new heuristic is used to minimise the total penalty cost of the sequence using a backward-forward scheduling technique and a penalty cost trade-off process. Exhaustive experiments are conducted to evaluate the effectiveness of the proposed hybrid algorithms. For medium-scale and large-scale problems, TSH with its best common parameter setting referred to as TSH2, clearly outperforms the exact algorithm, whereas both algorithms can obtain the optimal solution for small-scale problems. In addition, the computational time of TSH2 is in an acceptable range for the planner.