Scheduling with controllable processing times and compression costs using population-based heuristics

This paper considers the single machine scheduling problem of jobs with controllable processing times and compression costs and the objective to minimise the total weighted job completion time plus the cost of compression. The problem is known to be intractable, and therefore it was decided to be tackled by population-based heuristics namely differential evolution (DE), particle swarm optimisation (PSO), genetic algorithms (GAs), and evolution strategies (ES). Population-based heuristics have found wide application in most areas of production research including scheduling theory. It is therefore surprising that this problem has not yet received any attention from the corresponding heuristic algorithms community. This work aims at contributing to fill this gap. An appropriate problem representation scheme is developed together with a multi-objective procedure to quantify the trade-off between the total weighted job completion time and the cost of compression. The four heuristics are evaluated and compared over a large set of test instances ranging from five to 200 jobs. The experiments showed that a differential evolution algorithm is superior (with regard to the quality of the solutions obtained) and faster (with regard to the speed of convergence) to the other approaches.