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

Cheng, Junheng; Chu, Feng; Chu, Chengbin; Xia, Weili

RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 4-5, pp. 715-732.

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 $\epsilon$-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.

Classification : 90B35, 90B50, 90C11
Mots clés : Batch scheduling, TOU pricing policy, bi-objective optimization, makespan, electricity cost

A. Pacific, Energy Research Centre APERC. Chapter 6: Apec energy demand and supply outlook, 5th edition. Asia-Pacific Economic Cooperation (2013) 70.

J.-F. Bérubé, M. Gendreau and J.-Y. Potvin, An exact-constraint method for bi-objective combinatorial optimization problems: Application to the traveling salesman problem with profits. Eur. J. Oper. Res. 194 (2009) 39–50. | DOI | MR | Zbl

Junheng Cheng, Feng Chu, Weili Xia, Jianxun Ding and Xiang Ling. Bi-objective optimization for single-machine batch scheduling considering energy cost. In 2014 International Conference on Control, Decision and Information Technologies (CoDIT). IEEE (2014) 236–241.

I. Das and J.E. Dennis, A closer look at drawbacks of minimizing weighted sums of objectives for pareto set generation in multicriteria optimization problems. Struct. Optim. 14 (1997) 63–69. | DOI

M.P. Lee, L. Medearis, P. Sporborg, M. Tita, D. Wight, A. Wilkerson, F. Kreger, V. Richardson, W. Gifford, C. Elsner, D. Kathan and R. Aldina, Assessment of demand response and advanced metering: Staff report 2012. Federal Energy Regulatory Commission, Washington (2012).

M. Esmaili, H.A. Shayanfar and N. Amjady, Multi-objective congestion management incorporating voltage and transient stabilities. Energy 34 (2009) 1401–1412. | DOI

K. Fang, N.A. Uhan, F. Zhao and J.W. Sutherland, Scheduling on a single machine under time-of-use electricity tariffs. Ann. Oper. Res. 238 (2016) 199–227. | DOI | MR | Zbl

R.L. Graham, E.L. Lawler, J.K. Lenstra and A.R. Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5 (1979) 287–326. | DOI | MR | Zbl

H. Hadera and L. Harjunkoski, Continuous-time batch scheduling approach for optimizing electricity consumption cost. In vol. 32 of 23rd European Symposium on Computer Aided Process Engineering. Elsevier (2013) 403.

Y.Y. Haimes, L.S. Lasdon and D.A. Wismer, On a bicriterion formulation of the problems of integrated system identification and system optimization. IEEE Trans. Syst. Man Cybernet. (1971) 296–297. | MR | Zbl

Cheng He, Xiumei Wang, Yixun Lin and Yundong Mu, An improved algorithm for a bicriteria batching scheduling problem. RAIRO: OR 47 (2013) 1–8. | DOI | Numdam | MR | Zbl

Yoshiro Ikura and M. Gimple, Efficient scheduling algorithms for a single batch processing machine. Oper. Res. Lett. 5 (1986) 61–65. | DOI | MR | Zbl

C.-Y. Lee, R. Uzsoy and L.A. Martin-Vega, Efficient algorithms for scheduling semiconductor burn-in operations. Oper. Res. 40 (1992) 764–775. | DOI | MR | Zbl

M. Leitner, I. Ljubić and M. Sinnl, Solving the bi-objective prize-collecting steiner tree problem with the $\epsilon$-constraint method. Electron. Notes Discrete Math. 41 (2013) 181–188. | DOI

H. Luo, B. Du, G.Q. Huang, Huaping Chen and Xiaolin Li, Hybrid flow shop scheduling considering machine electricity consumption cost. Int. J. Prod. Econ. 146 (2013) 423–439. | DOI

G. Mavrotas, Effective implementation of the $\epsilon$-constraint method in multi-objective mathematical programming problems. Appl. Math. Comput. 213 (2009) 455–465. | DOI | MR | Zbl

C.A. Méndez, J. Cerdá, I.E. Grossmann, I. Harjunkoski and M. Fahl, State-of-the-art review of optimization methods for short-term scheduling of batch processes. Comput. Chem. Eng. 30 (2006) 913–946. | DOI

J.-Y. Moon, K. Shin and J. Park, Optimization of production scheduling with time-dependent and machine-dependent electricity cost for industrial energy efficiency. Int. J. Adv. Manufact. Technol. 68 (2013) 523–535. | DOI

A.K. Ojha and R.R. Ota, Multi-objective geometric programming problem with Karush-Kuhn-Tucker condition using $\epsilon$-constraint method. RAIRO: OR 48 (2014) 429–453. | DOI | Numdam | MR | Zbl

C.N. Potts and M.Y. Kovalyov, Scheduling with batching: a review. Eur. J. Oper. Res. 120 (2000) 228–249. | DOI | MR | Zbl

P. Reiter and W.J. Gutjahr, Exact hybrid algorithms for solving a bi-objective vehicle routing problem. Central Eur. J. Oper. Res. 20 (2012) 19–43. | DOI | MR | Zbl

F. Shrouf, J. Ordieres-Meré, A. García-Sánchez and M. Ortega-Mier, Optimizing the production scheduling of a single machine to minimize total energy consumption costs. J. Clean. Prod. 67 (2014) 197–207. | DOI

C.S. Sung and Y. Choung, Minimizing makespan on a single burn-in oven in semiconductor manufacturing. Eur. J. Oper. Res. 120 (2000) 559–574. | DOI | Zbl

Lixin Tang, Jiyin Liu, Aiying Rong, and Zihou Yang. A review of planning and scheduling systems and methods for integrated steel production. Eur. J. Oper Res. 133 (2001) 1–20. | DOI | Zbl

V. T’Kindt and J.-C. Billaut, Multicriteria scheduling problems: a survey. RAIRO: OR 35 (2001) 143–163. | DOI | Numdam | MR | Zbl

R. Uzsoy, C.-Y. Lee and L.A. Martin-Vega, A review of production planning and scheduling models in the semiconductor industry part i: system characteristics, performance evaluation and production planning. IIE Trans. 24 (1992) 47–60. | DOI

R. Uzsoy, C.-Y. Lee and L.A. Martin-Vega, A review of production planning and scheduling models in the semiconductor industry part ii: shop-floor control. IIE Trans. 26 (1994) 44–55. | DOI

D.J. Van De Rzee, A. Van Harten and P.C. Schuur, Dynamic job assignment heuristics for multi-server batch operations-a cost based approach. Int. J. Prod. Res. 35 (1997) 3063–3094. | DOI | Zbl

Y. Wang and L. Li, Time-of-use based electricity demand response for sustainable manufacturing systems. Energy 63 (2013) 233–244. | DOI

P. Wu, A. Che, F. Chu and M. Zhou, An improved exact $\epsilon$-constraint and cut-and-solve combined method for biobjective robust lane reservation. IEEE Trans. Intell. Transp. Syst. 16 (2015) 1479–1492. | DOI

R. Xu, H. Chen and X. Li, Makespan minimization on single batch-processing machine via ant colony optimization. Comput. Oper. Res. 39 (2012) 582–593. | DOI | MR | Zbl

R. Xu, H. Chen and X. Li, A bi-objective scheduling problem on batch machines via a pareto-based ant colony system. Int. J. Prod. Econ. 145 (2013) 371–386. | DOI

H. Zhang, F. Zhao, K. Fang and J.W. Sutherland, Energy-conscious flow shop scheduling under time-of-use electricity tariffs. CIRP Ann. Manufact. Technol. 63 (2014) 37–40. | DOI

Z. Zhou, F. Chu, A. Che and M. Zhou, $\epsilon$-constraint and fuzzy logic-based optimization of hazardous material transportation via lane reservation. IEEE Trans. Intell. Transp. Syst. 14 (2013) 847–857. | DOI