A hybrid simulated annealing approach for single machine scheduling problems with non-regular penalty functions

An algorithm is presented for single machine scheduling problems which have V-shaped optimal schedules. The algorithm is a hybrid of a greedy approach, followed by a simulated annealing search of the V-shaped sequence solution space. A number of non-regular objective functions, both with and without a common due date, are considered. In all test problems, the algorithm gives better solutions than the heuristics previously presented in the literature.