International Transactions in Operational Research

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

Early View


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.

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.