CHEMICAL ENGINEERING TRANSACTIONS VOL. 81, 2020 A publication of The Italian Association of Chemical Engineering Online at www.cetjournal.it Guest Editors: Petar S. Varbanov, Qiuwang Wang, Min Zeng, Panos Seferlis, Ting Ma, Jiří J. Klemeš Copyright © 2020, AIDIC Servizi S.r.l. ISBN 978-88-95608-79-2; ISSN 2283-9216 Novel Approaches for Energy-Efficient Flexible Job-Shop Scheduling Problems Nikolaos Rakovitisa, Dan Lia, Nan Zhanga, Jie Lia,*, Liping Zhangb, Xin Xiaoc aCentre for Process Integration, Departement of Chemical Engineering and Analytical Science, The University of Manchester, M13 9PL, United Kingdom bDepartment of Industrial Engineering, Wuhan University of Science and Technology, Wuhan, Hubei, 430081 P. R. China cInstitute of Process Engineering, Chinese Academy of Sciences, P. R. China 100190 jie.li-2@manchester.ac.uk In this work, two novel mixed-integer linear programming models for energy efficient scheduling of flexible job- shops with simultaneous consideration of machine switching off-on strategy are developed. While the first model is based on the unit-specific event-based approach, the other one uses the sequence-based approach. The computational results demonstrate that the proposed models, especially the unit-specific event-based model, are more robust and efficient than the existing models. To solve industrial-scale problems efficiently, a hybrid algorithm is developed through the combination of the existing eGEP algorithm and mathematical programming approach. The hybrid algorithm leads to up to 15 % more energy savings in comparison to the eGEP algorithm. 1. Introduction Flexible job-shop scheduling problems have received significant attention due to their wide relation with many process industries (Chaudhry and Khan, 2015). Many approaches have been developed for such optimal scheduling to minimize operating cost or makespan without consideration of energy consumptions (Chaudhry and Khan, 2015). As reported, up to 65 % of total energy is consumed when machines are idle (Nguyen et al. 2019). The optimal schedule generated can lead to unnecessarily high energy consumption due to large machine idle periods and inefficient use of machine switching off-on strategy (Zhang et al., 2017). Several approaches have been proposed for energy-efficient scheduling of flexible job-shop problems with simultaneous implementation of the machine switch off-on strategy (Meng et al., 2019). These approaches include the development of Mixed-Integer Linear Programming (MILP) models (Meng et al., 2019) and an efficient gene expression programming-based algorithm (eGEP) (Zhang et al., 2017). Although the MILP models can solve small-scale problems to optimality, they lead to intractable model size and require excessive computational time. They often fail to obtain a feasible solution for large-scale problems. The eGEP generates efficient dispatching rules for solving large-scale problems. However, it often generates solutions with higher energy consumption than the MILP models. No robust and efficient approach has been developed for the industrial-scale energy-efficient scheduling problem. In this work, two novel efficient MILP models are developed using the unit-specific event-based (Rakovitis et al., 2019) and sequence-based (Méndez and Cerdá, 2000) modelling approaches. These two models lead to smaller model size with tighter MILP relaxation and less computational time than the existing models. To solve large-scale problems efficiently, a hybrid algorithm through combination of the mathematical programming approach and the eGEP is proposed. It is shown that the hybrid algorithm always generates better solutions with up to 15 % additional energy savings than the eGEP. The hybrid algorithm is also superior to the proposed unit-specific event-based model for large-scale problems. 2. Problem description Figure 1 illustrates a typical flexible job-shop facility. In total 𝐾 (𝑘 = 1, 2, … , 𝐾) jobs with 𝐿 (𝑙 = 1, 2, … , 𝐿) operations should be processed in 𝐽 (𝑗 = 1, 2, … , 𝐽) machines. Each job 𝑘 contains 𝐋𝑘 operations. An operation 𝑙 in a job 𝑘 can only start after all preceding operations in the same job finish. Each operation must be processed DOI: 10.3303/CET2081138 Paper Received: 30/04/2020; Revised: 06/06/2020; Accepted: 11/06/2020 Please cite this article as: Rakovitis N., Li D., Zhang N., Li J., Zhang L., Xiao X., 2020, Novel Approaches for Energy-Efficient Flexible Job-Shop Scheduling Problems, Chemical Engineering Transactions, 81, 823-828 DOI:10.3303/CET2081138 823 exactly once in the horizon. A machine can be in operation, standby, or switch off-on mode. The energy consumption curve in a machine is depicted in Figure 2. Energy required is classified into direct energy, indirect energy, standby energy and switch off-on energy. While direct energy is consumed when a machine processes an operation, indirect energy is consumed for an operation in the facility but not directly from a machine. Standby energy is required when a machine remains on standby. Switch off-on energy is consumed when a machine is switched off and on. Given the necessary data including jobs, available machines, processing times, unit cutting power, unit unload power, switch off-on energy consumption and scheduling horizon, the scheduling problem is to determine optimal allocation, sequence and timings of operations, as well as optimal mode of each machine at a time. The objective is to minimize total energy consumption. All machines are switched off in the beginning. Figure 1: A typical flexible job-shop facility Figure 2: The energy consumption curve for a machine 3. Unit-specific event-based formulation (M1) The process is represented by the state-task network (Kondili et al., 1993) where task 𝑖 denotes an operation and state 𝑠 denotes the relation between two tasks. A binary variable 𝑤𝑖,𝑗,𝑛,𝑛 is used to denote if task 𝑖 is processed on 𝑗 from 𝑛 to 𝑛. A parameter ∆𝑛 is the number of event points that a task is allowed to span over. 3.1. Allocation constraints At a time, machine 𝑗 can process at most one task and all tasks must be processed exactly once in the horizon. A consuming task 𝑖 can start at event point 𝑛 only if its related production task 𝑖 ends at 𝑛 or a previous 𝑛 < 𝑛. , , , 1 i i j n n j n n n n n n n n w      −     + =   J ∀𝑗, 𝑛 (1) , , , 1 i i j n n j n n n n n w     + =  J ∀𝑖 (2) , , , , , , i i j n n i j n n j n n n n n n n n n n w w           −     +     J ∀𝑠 ∈ 𝑆𝐼𝑁 , 𝑖 ∈ 𝐈𝑠 𝑃 , 𝑗, 𝑖 ∈ (𝐈𝑗 ∪ 𝐈𝑠 𝐶 ), 𝑛 (3) where 𝐈𝑗 contains tasks processed in 𝑗. 𝐈𝑆 P contains tasks that “produce” 𝑠. 𝐈𝑆 C includes tasks that “consume” 𝑠. The number of tasks processed on machine 𝑗 must be within the minimum (𝑁𝑗 min) and maximum (𝑁𝑗 max) limits. min max , , , j j i j n n j i n n n n n N w N    +    I ∀𝑗 (4a,b) 3.2. Duration constraints The end time of unit 𝑗 at 𝑛 (𝑇𝑗,𝑛 𝑓 ) must equal the start time (𝑇𝑗,𝑛 𝑠 ) plus the duration (𝛼𝑖,𝑗) of the task processed. f s , , , , , , j j n j n i j i j n n i n n n n T T w     + = +   Ι ∀𝑗, 𝑛 (5) E n e rg y T0 On Off On Off Time Job 1 Job 2 E n e rg y T0 On Off Time Job 1 Job 2 Standby Time 824 3.3 Standby energy constraints A binary variable 𝑥𝑗,𝑛 denotes if 𝑗 is on standby at 𝑛. The standby energy consumption (𝐸𝑆𝑗,𝑛) equals the idle time multiplying the unload power (𝑃𝑈𝑗), which should not exceed the switch off-on energy consumption (𝐸𝑂𝑗). , ,j n j j n ES EO x  ∀𝑗, 𝑛 (6) ( )s f, , , 1j n j n j n jES T T PU− −  ∀𝑗, 𝑛 > 1 (7) ( ) ( )s f, , , 1 , ,max( ) 1j n j n j n j i j j j n i ES T T PU PU x −  −  −   − ∀𝑗, 𝑛 > 1 (8) 3.4. Sequencing constraints A machine 𝑗 at event point (𝑛 + 1) must start after it finishes at 𝑛. A machine 𝑗 at 𝑛, processing a “production” (“consumption”) task of state s must finish (start) before (after) the time that state s is available at 𝑛 (𝑇𝑠,𝑛). s f , 1 ,j n j n T T +  ∀𝑗, 𝑛 < 𝑁 (9) ( ) f , , , , , (1 ) P j S s n j n i j n n n n n ni T T M w  −     −  −   I I s∊SIN, j, , 0 j s i i    I , n (10) ( ) s , , , , , (1 ) C j S s n j n i j n n n n n ni T T M w    +   +  −   I I s∊SIN, j, ( ) , , 0 P R j S s i j i i          I I I , n (11) The time that state 𝑠 is available at event point 𝑛 is before the time that is available at event point (𝑛 + 1). , , 1+  s n s n T T ∀𝑠 ∈ 𝑆𝐼𝑁 , 𝑛 (12) 3.5. Makespan calculation Makespan (denoted as MS) is the earliest time, that all tasks have already been processed. f ,j n T MS ∀𝑗, 𝑛 = 𝑁 (13) ,s n T MS ∀𝑠 ∈ 𝑆𝐼𝑁 , 𝑛 = 𝑁 (14) 3.6. Objective The objective is to minimize the total energy consumption. The first and second term calculates direct energy, indirect energy, while the third term calculates standby energy and the switch off/on energy consumptions. ( ), , , , , , , 1 1 j i j n n i j i j j n j j n j i n n n n n j n TEC w PC MS ES EO x     +   =   +  + +  −     I (15) 4. Sequence-based mathematical formulation (M2) A binary variable 𝑥𝑘,𝑙,𝑘,𝑙,𝑗 denotes if an operation 𝑙 in job 𝑘 immediately precedes 𝑙 in job k on 𝑗 . Binary variables 𝑤𝑘,𝑙,𝑗 denotes if 𝑙 in job 𝑘 is processed in 𝑗 and 𝑋𝐹𝑘,𝑙,𝑗 denote if 𝑙 in job 𝑘 is first processed in 𝑗. 4.1. Allocation constraints An operation is processed first or immediately preceded in 𝑗. KLJk,l,j contains operations of job 𝑘 processed in 𝑗. ( )( ), , , , , , , , , , ,k l j k l k l j k l j k l j k l k k k k l l x XF w            =   + =  KLJ j, k, l ∊ KLJk,l,j (16) Constraint (17) ensures that an operation 𝑙 that is not processed in 𝑗 should not precede any operation in 𝑗. At most one operation can be processed first in 𝑗 indicated in constraint (18). Constraint (19) ensures that an operation is processed exactly once. Constraints (20) impose min/max limits on the number of operations in 𝑗. 825 ( )( ), , , , , ', , , ,k l j k l k l j k l j k l k k k k l l x w           =     KLJ j, k, l ∊ KLJk,l,j (17) , , , , 1 k l j k l j k l XF    KLJ ∀𝑗 (18) , , , 1 k l k l j j w  = J k, l ∊ Lk (19) , , min max , , k l j j k l j j k l N w N     KLJ ∀𝑗 (20a,b) A machine that does not process is in either the standby mode (yk,l,j = 1) or the switch on-off mode (zk,l,j = 1). , , , , , ,k l j k l j k l j y z w+ = j, k, l∊KLJk,l,j (21) 4.2. Sequencing constraints An operation 𝑙 (𝑙 = 𝑙 + 1) should start after operation 𝑙 in the same job finishes (constraint 22). Constraints 23- 24 indicate if operation 𝑙 immediately precedes 𝑙 in 𝑗, the start time of 𝑙 should equal the finish time of 𝑙 plus the idle time (𝐶𝑇𝑘,𝑙,𝑗) . ( ) , , , , , , , k l k l k l k l j k l j j T T w   +  J k,l,l∊ Lk, l = l + 1 (22) ( ) ( ), , , , , , , , , , , , , , ', 1 k l k l k l k l k l k l j k l j k l j k l k l j j j T T w CT H x             +  + − −       J J J  (k, k, l, l) KL (23) ( ) ( ), ,, , , , , , , , , , , , , ', , , 1 1 k l k lk l k l k l k l k l j k l j k l j k l k l j k l j j jj T T w CT H x H y               +  + + − + −           J JJ J  (k, k, l, l) KL (24) where set KL is defined as: KL = {(𝑘, 𝑙, 𝑘′ , 𝑙′)|𝑙 ∊ L𝑘 , 𝑙 ∊ L𝑘, 𝑘 ≠ 𝑘 or (𝑘 = 𝑘 and 𝑙 ≠ 𝑙)}. 4.3. Standby energy calculation , , , , k l k l k l j j j ES CT PU  =  J k, l ∊ Lk (25) , , , , min( , ) j k l j k l j j EO CT H y PU   j, k, l∊KLJk,l,j (26) 4.4. Tightening constraints ( ) , , , , , , , , k l k l k l j k l j k l j j T w CT MS  +  +  J k, l ∊ Lk, l = L (27) ( ) , , , , , , , , k l j k l j k l j k l j k l w CT MS   +   KLJ ∀𝑗 (28) 4.5. Objective ( ) , , , , , , , , , , , , , [ ] k l j k k l j k l j k l j k l j k l j k l j j k l k l j k l z w PC MS ES EO z      =   +  + +       KLJ L KLJ (29) 4.6. Bounds An operation 𝑙 in a job 𝑖 should always start after the minimum time required for all previous operations. ( ) min, , , , , , ,mink l k l j k l j k l j j l l T B      +  k, l, l ∊ Lk (30) 826 5. Hybrid algorithm The eGEP from Zhang et al. (2017) generates dispatching rules that are used to obtain schedules. However, the schedules may not be energy efficient. The main reason is that the dispatching rules can only effectively determine the operation allocation and sequence. A heuristic “assign as early as possible” is used to determine the timings of operations on machines, which can result in high standby and switch off-on energy. A better solution can be obtained using an efficient mathematical model to determine the optimal timings. Based on this, a hybrid algorithm through combination of the eGEP algorithm and the proposed sequence-based model is developed in which the eGEP algorithm first generates efficient dispatching rules to determine the allocation and sequence of operations. The proposed sequence-based model M2 then determines the best operation timings and best trade-off between indirect energy consumption and switching off-on energy consumption. Table 1: Computational results for Examples 1-10 Example Model Event points CPU time (s) RMILP (h) MILP (h) Discrete Variables Continuous Variables Constraints Gap (%) Ex1 ZTWW 3 0.19 7.33 63.03 30 45 218 - MZSR 3a 0.06 63.03 63.03 21 23 68 - M1 3 0.02 63.03 63.03 19 28 68 - M2 - 0.06 63.03 63.03 16 30 57 - Ex2 ZTWW 3 0.19 24.58 220.74 63 84 596 - MZSR 4a 0.05 214.74 220.74 37 35 114 - M1 3 0.02 220.74 220.74 30 44 123 - M2 - 0.05 220.74 220.74 30 46 94 - Ex3 ZTWW 3 0.20 20.00 166.23 42 57 292 - MZSR 4a 0.05 159.23 166.23 46 36 133 - M1 3 0.02 166.23 166.23 28 31 76 - M2 - 0.11 166.23 166.23 40 46 103 - Ex4 ZTWW 5 2.9 19.79 219.46 150 183 1,946 - MZSR 7a 0.19 212.97 219.46 90 56 244 - M1 5 0.11 218.97 219.46 77 80 274 - M2 - 0.14 218.97 219.46 91 72 195 - Ex5 ZTWW 6 2.8 25.70 274.94 180 219 2,660 - MZSR 6a 0.30 260.94 274.94 84 56 232 - M1 6 0.05 274.94 274.94 93 95 315 - M2 - 0.05 274.94 274.94 82 72 183 - Ex6 MZSR 15a 3,600 1,455.95 1,715.22 853 277 2,032 22.6 M1 11 3,600 1,542.15 1,830.43 710 612 2,405 5.5 M2 - 3,600 1,710.62 1,792.04 943 342 1,739 4.5 Ex7 M1 20 3,600 2,606.72 2,637.50 1,815 1,507 6,016 0.3 M2 - 3,600 2,606.72 2,736.30 1,816 496 3,366 4.7 Ex8 M1 21 3,600 3,002.11 3,035.98 2,494 2,002 8,207 0.4 Ex9 M1 12 3,600 2,512.49 3,648.90 1,466 1,452 5,585 31.1 M2 - 3,600 2,590.43 3,150.59 1,555 654 3,129 26.2 Ex10 M1 17 3,600 3,885.07 6,704.23 2,934 2,652 11,439 42.1 Ex11 M1 21 3,600 5,598.36 9,603.38 4,946 4,422 17,809 41.5 a Maximum number of positions of all machines. 6. Computational results 15 examples from Zhang et al. (2017) are solved to illustrate the capability of the proposed models and hybrid algorithm. While Examples 1-5 are small-scale, Examples 6-11 and 12-15 are medium-scale and large-scale. All examples are solved using CPLEX 12/GAMS 24.6.1. on a desktop computer with Intel® Core™ i5-2500 3.3 GHz and 8 GB RAM running Windows 7. The maximum computational time is one hour. The results are given in Table 1. Model M1 is able to generate optimal solutions for Examples 1-5 and best feasible solutions for Examples 6-11. It fails for Examples 12-15. Model M2 can also generate optimal solutions for Examples 1-5 and feasible solutions for Examples 6-7 and 9 only. The performance of models M1 and M2 is also compared with the existing models (Zhang et al., 2017; Meng et al., 2019) denoted as ZTWW and MZSR, as shown in Table 1. From Table 1, both ZTWW and MZSR can generate optimal solutions for Examples 1-5. However, ZTWW cannot generate a feasible solution for Examples 827 6-15, whilst MZSR is only able to generate a feasible solution for Example 6. Models M1 and M2 lead to tighter LP relaxation and smaller model size for most examples than ZTWW and MZSR. As a result, M1 and M2 require less computational time to obtain the same or better solutions than ZTWW and MZSR. The Model M1 is more robust than M2 since it can generate solutions for more examples. Table 2: Comparative results for Examples 6-15 using different approaches M1 eGEP Hybrid Algorithm Examples TEC (kW) TEC (kW) TEC (kW) Examples Ex6 1,830.43 1,975.75 1,943.83 Ex6 Ex7 2,637.50 3,046.21 2,890.21 Ex7 Ex8 3,035.98 3,700.86 3,468.03 Ex8 Ex9 3,648.90 4,082.95 3,715.50 Ex9 Ex10 6,704.23 6,640.15 5,671.46 Ex10 Ex11 9,603.38 7,173.32 6,662.99 Ex11 Ex12 - 10,108.14 9,098.46 Ex12 Ex13 - 10,939.20 9,726.36 Ex13 Ex14 - 10,339.46 9,112.79 Ex14 Ex15 - 10,751.25 9,459.67 Ex15 The hybrid algorithm is also used to solve Examples 6-15. The comparative results of the hybrid algorithm, model M1 and the eGEP algorithm are provided in Table 2. It seems that model M1 can generate better feasible solutions for medium-scale examples 6-9 compared to the eGEP and hybrid algorithms. However, when the problem size increases, model M1 generates worse solutions or fails in comparison to the eGEP and hybrid algorithms (see Examples 10-15). The hybrid algorithm always generates better solutions than the eGEP algorithm due to the reduction of machine idle time. A maximum improvement by 15 % can be achieved. 7. Conclusions In this work, two novel mathematical models for energy-efficient scheduling of flexible job-shops were developed. A hybrid algorithm combining the eGEP with the mathematical programming model was proposed to solve large-scale problems efficiently. The computational results demonstrate that the proposed unit-specific event-based model is the most robust and efficient compared to the existing models. The hybrid algorithm always generated better solutions with up to 15 % more energy savings in comparison to the eGEP algorithm. It is also shown that the hybrid algorithm is superior to the proposed unit-specific event-based model for industrial-scale problems. In the future, the hybrid algorithm will be refined further to improve the solution quality. Acknowledgements NR would like to acknowledge financial support from the postgraduate award by The University of Manchester. LZ appreciates financial support from the National Natural Science Foundation of China (51875420). References Chaudhry I.A., Khan A.A., 2015. A research survey: review of flexible job shop scheduling techniques. International Transctions in Operations Research, 23, 551-591. Kondili E., Pantelides C. C., Sargent R. W. H., 1993 A general algorithm for short-term scheduling of batch operations-I MILP formulation. Computers and Chemical Engineering, 17(2), 211-227 Méndez C.A., Cerdá J., 2000. Optimal scheduling of a resource-constrained multiproduct batch plant supplying intermediates to nearby end-product facilities. Computers and Chemical Engineering, 24(2-7), 369-376 Meng L., Zhang C., Shao X., Ren Y., 2019. MILP models for energy-aware flexible job shop scheduling problem. Journal of Cleaner Production, 210, 710-723. Rakovitis N., Zhang N., Li J., Zhang L., 2019. A new approach for scheduling of multipurpose batch processes with unlimited intermediate storage policy. Frontiers of Chemical Science and Engineering, 13, 784-802 Nguyen T.A.K., Tran Le N.H., Henri P., Museau M., 2019. Evaluating energy efficiency of production machine. Applied Mechanics & Materials, 889, 580-587. Zhang L., Tang Q., Wu Z., Wang F., 2017. Mathematical modelling and evolutionary generation of rule sets for energy-efficient flexible job shops. Energy, 138, 210-227. 828