Bi-objective optimization of single-machine batch scheduling under time-of-use electricity prices

¹ School of Management, Northwestern Polytechnical University, Xi’an, P.R. China.
² Laboratoire IBISC, University of Evry-Val d’Essonne, Evry, France.
feng.chu@ibisc.univ-evry.fr
³ School of Transportation Engineering, Hefei University of Technology, Hefei, P.R. China.
⁴ Laboratoire Genie Industriel, CentraleSupélec, Université Paris-Saclay, Grande Voie des Vignes, 92290 Chatenay-Malabry, France.

Received: 20 May 2015
Accepted: 2 December 2015

Abstract

Time-of-use (TOU) electricity pricing has been a common practice to enhance the peak load regulation capability of power grid. Meanwhile, it provides a good opportunity for industries to reduce energy costs, especially for energy-intensive ones, where batch scheduling is often involved. Majority of batch scheduling problems have been proved to be NP-hard, even for most single-machine environments. Optimizing batch scheduling under TOU policy in these industries will be of great significance. Single-machine batch scheduling is an important basis for more complicated shop scheduling problems. This paper investigates a bi-objective single-machine batch scheduling problem under TOU policy: the first objective is to minimize the makespan and the second is to minimize the total electricity costs. The considered problem is first formulated as a bi-objective mix-integer linear programming (MILP) model and is demonstrated to be NP-hard. Subsequently, the MILP is simplified by analyzing properties and search space for a Pareto optimal solution is greatly reduced. Then, an exact ε-constraint method is adapted to obtain its Pareto front, which is accelerated due to these properties. Finally, a preferable solution is recommended for decision makers via a fuzzy-logic-based approach. Computational results on randomly generated instances show the effectiveness of the proposed approach.