Bi-criteria formulation for green scheduling with unrelated parallel machines with sequence-dependent setup times.

Abstract

Given the important role of machine scheduling in manufacturing industry, we discuss power consumption in sequencing jobs in a scheduling problem, assuming variable speed operation in machines. The problem involves defining the allocation of jobs to machines, the order of processing jobs and the speed of processing each job in each machine. This problem can be viewed as a type of green scheduling problem, dealing with sustainable use of energy consumption and environmental effects. We propose a mixed integer linear programming (MILP) model for the unrelated parallel machine‐scheduling problem with sequence‐dependent setup times, with independent and non‐preemptible jobs, minimizing the makespan and the total consumption of electricity. Furthermore, we employ a novel math‐heuristic algorithm, named multi‐objective smart pool search matheuristic (or simply smart pool), for finding solutions near the Pareto front, in a restricted computational budget. As a case study, a new set of instances is created for the problem. Those instances are solved using the classical ε‐constrained method and the smart pool method. The obtained sets of non‐dominated solutions indicate the conflict between both objectives, highlighting the relevance of the suggested approach to industry. From the obtained results, it was verified that the smart pool achieved good convergence towards the true Pareto front, as indicated by the hyper‐volume metric, presenting lower average time for finding solutions on the Pareto front. In small to medium size instances, the smart pool search method can achieve very good approximations of the Pareto front with less computational effort than traditional methods.