A hybrid heuristic solution based on simulated annealing algorithm for energy efficient single machine scheduling problem with sequence dependent setup times

Abstract

Increased carbon dioxide emissions and energy consumption increase interest in energy efficient scheduling problems. In this study, speed scaling method is discussed in order to provide energy saving in multiobjective energy efficient single machine scheduling problem. In the literature with the speed scaling method, the energy consumption rate increases when the machine is operated at high speed, but the job is completed in a shorter time. When the machine is operate at low speed, the energy consumption rate decreases but the completion time of the jobs are prolonged. In the study, the objective functions are minimization of the total amount of energy consuption and the number of tardy jobs. The problem is defined by the scheduling problem in a manufacturing firm that produces plastic parts. Jobs have a sequence dependent setup times, and the setup time of a job depends on the job completed before it. A mathematical model is proposed for the problem. The epsilon-constraint method is used for the solution of the problem. All Pareto efficient solutions for small size problems are obtained by using the proposed heuristic method. However, as a result of the problem not being solved in polynomial time, a multi-objective heuristic algorithm is proposed for solving large-scale problems. The success of the proposed algorithm is shown by comparing with Non- dominated Sorting Genetic Algorithm II.