Energy-Efficient Single Machine Total Weighted Tardiness Problem with Sequence-Dependent Setup Times

Abstract

Most of the problems defined in the scheduling literature do not yet take into account the energy consumption of manufacturing processes as in most of the variants with tardiness objectives. This study handles scheduling of jobs with due dates and sequence-dependent setup times (SMWTSD) while minimizing total weighted tardiness and total energy consumed in machine operations. The trade-off between total energy consumption (TEC) and total weighted tardiness is examined in a single machine environment where different jobs can be operated at varying speed levels. A bi-objective mixed integer linear programming model is formulated including this speed-scaling plan. Moreover an efficient multi-objective block insertion heuristic (BIH) and a multi-objective iterated greedy (IG) algorithm are proposed for this NP-hard problem. The performances of the proposed BIH and IG algorithms are compared with each other. The preliminary computational results on a benchmark suite consisting of instances with 60 jobs reveal that the proposed BIH algorithm is very promising in terms of providing good Pareto frontier approximations for the problem.