# Energy-Aware Flexible Job Shop Scheduling Using Mixed Integer Programming and Constraint Programming

Authors: Andy Ham; Myoung-Ju Park; Kyung Min Kim
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Compromising productivity in exchange for energy saving does not appeal to highly capitalized manufacturing industries. However, we might be able to maintain the same productivity while significantly reducing energy consumption. This paper addresses a flexible job shop scheduling problem with a shutdown (on/off) strategy aiming to minimize makespan and total energy consumption. First, an alternative mixed integer linear programming model is proposed. Second, a novel constraint programming is proposed. Third, practical operational scenarios are compared. Finally, we provide benchmarking instances, CPLEX codes, and genetic algorithm codes, in order to promote related research, thus expediting the adoption of energy-efficient scheduling in manufacturing facilities. The computational study demonstrates that (1) the proposed models significantly outperform other benchmark models and (2) we can maintain maximum productivity while significantly reducing energy consumption by 14.85% (w/o shutdown) and 15.23% (w/shutdown) on average.


---

## Body

## 1. Introduction

Energy consumption is a very important issue for our society in terms of both environment and economy. U.S. Energy Information Administration [1] recently reported international energy outlook 2019 with projections to 2050. In the report, the world energy consumption is expected to increase by approximately 50%, accounting for more than half of the non-OECD Asian countries, including China and India. Industrial sectors, such as manufacturing, agriculture, and construction, are the largest consumer among end users, and their energy consumption will increase by more than 30% from 2018 to 2050. The share of energy consumed by energy-intensive manufacturing holds steady at 50% from 2018 to 2050. These predictions and phenomena were analyzed in several studies [2–4].Manufacturing has enormous potential for energy saving because 80% of the energy consumed by machines occurs in the idle state [5]. For this reason, several methods to increase energy efficiency in manufacturing have been attempted. The common method is to optimize a production schedule by considering green metrics along with traditional performance indicators. This approach called energy-aware scheduling or energy-efficient scheduling has the advantage of achieving significant performance at no extra cost [6].In this paper, we deal with energy-efficient scheduling in the flexible job shop scheduling problem (FJSP). Mouzon et al. [5] observed that if an idle period is long enough, the energy could be saved by using shutdown (on/off) strategy to turn the machine off and on. Che et al. [7] first developed a mixed integer linear programming (MILP) model for a single machine scheduling with a shutdown strategy, and the model was effectively validated with CPLEX solver. Subsequently, the shutdown strategy was applied to various production systems, and the first MILP model for FJSP with a shutdown strategy was proposed by Zhang et al. [8]. However, the proposed model was complex and computationally inefficient, so Meng et al. [9] improved it. However, both studies used only one type of MILP formulations for FJSP. This paper proposes the most efficient MILP formulation.The contributions of this paper are threefold. First, we propose an alternative MILP model for FJSP with a shutdown strategy. Second, we devise a constraint programming (CP). Third, the experimental study demonstrates that we can reduce energy consumption by 14.85% (w/o shutdown) and 15.23% (w/shutdown) on average, while not compromising productivity. In addition, we provide benchmarking instances, CPLEX MIP and CP source codes, and GA code, in order to promote related-research, thus expediting the adoption of energy-efficient scheduling in manufacturing facilities.The remainder of the paper is organized as follows: Section2 shows the literature review of FJSP, energy-efficient scheduling, and constraint programming. In Section 3, the problem description and solution methods are described. In Section 4, we compare the performance of proposed models and existing model through computational experiments. Finally, the conclusion and some directions for future research are given in Section 5.


## 2. Literature Review

### 2.1. Flexible Job Shop Scheduling Problem

The FJSP has been extensively studied over the past 30 years. A variety of techniques from exact methods to heuristics have been used in this research. Exact methods include branch-and-bound algorithm, MILP, and Lagrangian relaxation method among others, while heuristics include ant colony optimization, artificial bee colony, artificial immune system, evolutionary algorithms, greedy randomized adaptive search procedure, neighborhood search, particle swarm optimization, simulated annealing, Tabu search, hybrid techniques, and so on. See Chaudhry and Khan [10] for the survey about FJSP. We focus on the MILP method.MILP models for FJSP are classified into four different types by the main binary decision variable. The first is the machine-position formulation (MPF) that determines the position of the machine, where each operation is processed [8, 9, 11, 12]. The second is the general precedence formulation (GPF) that determines whether one operation precedes the other operation on the same machine [13, 14]. Note that one operation is not necessarily positioned immediately before the other operation. The third is the immediate precedence formulation (IPF) that determines whether one operation immediately precedes the other operation on the same machine [15]. The fourth is the time indexed formulation (TIF) that determines the time of the machine when each operation is started [16]. Demir and Kürşat Isleyen [17] classified mathematical models by this criterion and compared the computational results of MILP models.


### 2.2. Energy-Efficient Scheduling

The studies for energy-efficient scheduling are classified into four groups based on saving methods. The first is to reduce unnecessary idle time. This is a model that extends the existing model to save energy by reducing unnecessary idle time. The second is to shut down the idle machines. Turning off machines during the idle can save energy when idle time is long enough. The decision when to shut down a machine is added into the traditional scheduling model. The third is to slow down a machine speed. Energy consumption depends on a speed of a machine. We can save energy by adjusting a speed of a machine without impacting the makespan. The fourth is off-peak production. In the peak time, electricity costs are high. Therefore, a production at nonpeak time can save a significant amount of electricity costs. Table1 categorizes studies on energy-efficient scheduling by this criterion. See Gahm et al. [37] and Gao et al. [38] for reviews of energy-efficient scheduling.Table 1
Articles including energy-efficient scheduling models.
Saving methodEnvironmentReferencesReduce idle timeSingle machineJiang et al. [18]Hybrid flow shopLi et al. [19]; Zhang et al. [20]JSPJiang et al. [21]FJSPYin et al. [22]; Jiang et al. [23]Shutdown idle machinesSingle machineMouzon et al. [5]; Che et al. [7]Hybrid flow shopMeng et al. [24]FJSPMeta HeuristicDai et al. [25]; Wu and Sun [26]MILP-MPFZhang et al. [8]; Meng et al. [9]; Meng et al. [27]MILP-IPFThis studyExploit variable machine speedSingle machineChe et al. [28]Flow shopFang et al. [29]; Mansouri et al. [30]JSPZhang and Chiong [31]FJSPZhang et al. [32]Shift production soft-enter to off-peakSingle/parallel machineRager et al. [33]Hybrid flow shopSchulz et al. [34]FJSPMoon and Park [35]; Gong et al. [36]Our study belongs to the energy-efficient FJSP using the shutdown option. Among the studies, Dai et al. [25] and Wu and Sun [26] developed a genetic simulated annealing algorithm. Zhang et al. [8] developed MILP model and discovered energy-efficient rules that could be implemented in real practice. Meng et al. [9, 27] proposed several effective MILP models and evaluated the performance of these models. Zhang et al. [8] and Meng et al. [9, 27] used MPF, while our paper uses IPF. Moreover, we develop constraint programming and genetic algorithm models.


### 2.3. Constraint Programming

Hiller and Lieberman [39] noted that no presentation of the basic ideas of MILP is complete these days without introducing CP––that is promising to greatly expand our ability to formulate and solve various scheduling problems. CP has been applied to various scheduling problems, demonstrating a rapid computational speed. The search within IBM CPLEX CP Optimizer is equipped with the presolve functionality, some constraint propagation algorithms, temporal linear relaxation used to guide the search, and two search space exploration strategies that are used concurrently: the large neighborhood search for producing good quality solutions and failure-directed search for proving infeasibility or optimality [40].


## 2.1. Flexible Job Shop Scheduling Problem

The FJSP has been extensively studied over the past 30 years. A variety of techniques from exact methods to heuristics have been used in this research. Exact methods include branch-and-bound algorithm, MILP, and Lagrangian relaxation method among others, while heuristics include ant colony optimization, artificial bee colony, artificial immune system, evolutionary algorithms, greedy randomized adaptive search procedure, neighborhood search, particle swarm optimization, simulated annealing, Tabu search, hybrid techniques, and so on. See Chaudhry and Khan [10] for the survey about FJSP. We focus on the MILP method.MILP models for FJSP are classified into four different types by the main binary decision variable. The first is the machine-position formulation (MPF) that determines the position of the machine, where each operation is processed [8, 9, 11, 12]. The second is the general precedence formulation (GPF) that determines whether one operation precedes the other operation on the same machine [13, 14]. Note that one operation is not necessarily positioned immediately before the other operation. The third is the immediate precedence formulation (IPF) that determines whether one operation immediately precedes the other operation on the same machine [15]. The fourth is the time indexed formulation (TIF) that determines the time of the machine when each operation is started [16]. Demir and Kürşat Isleyen [17] classified mathematical models by this criterion and compared the computational results of MILP models.


## 2.2. Energy-Efficient Scheduling

The studies for energy-efficient scheduling are classified into four groups based on saving methods. The first is to reduce unnecessary idle time. This is a model that extends the existing model to save energy by reducing unnecessary idle time. The second is to shut down the idle machines. Turning off machines during the idle can save energy when idle time is long enough. The decision when to shut down a machine is added into the traditional scheduling model. The third is to slow down a machine speed. Energy consumption depends on a speed of a machine. We can save energy by adjusting a speed of a machine without impacting the makespan. The fourth is off-peak production. In the peak time, electricity costs are high. Therefore, a production at nonpeak time can save a significant amount of electricity costs. Table1 categorizes studies on energy-efficient scheduling by this criterion. See Gahm et al. [37] and Gao et al. [38] for reviews of energy-efficient scheduling.Table 1
Articles including energy-efficient scheduling models.
Saving methodEnvironmentReferencesReduce idle timeSingle machineJiang et al. [18]Hybrid flow shopLi et al. [19]; Zhang et al. [20]JSPJiang et al. [21]FJSPYin et al. [22]; Jiang et al. [23]Shutdown idle machinesSingle machineMouzon et al. [5]; Che et al. [7]Hybrid flow shopMeng et al. [24]FJSPMeta HeuristicDai et al. [25]; Wu and Sun [26]MILP-MPFZhang et al. [8]; Meng et al. [9]; Meng et al. [27]MILP-IPFThis studyExploit variable machine speedSingle machineChe et al. [28]Flow shopFang et al. [29]; Mansouri et al. [30]JSPZhang and Chiong [31]FJSPZhang et al. [32]Shift production soft-enter to off-peakSingle/parallel machineRager et al. [33]Hybrid flow shopSchulz et al. [34]FJSPMoon and Park [35]; Gong et al. [36]Our study belongs to the energy-efficient FJSP using the shutdown option. Among the studies, Dai et al. [25] and Wu and Sun [26] developed a genetic simulated annealing algorithm. Zhang et al. [8] developed MILP model and discovered energy-efficient rules that could be implemented in real practice. Meng et al. [9, 27] proposed several effective MILP models and evaluated the performance of these models. Zhang et al. [8] and Meng et al. [9, 27] used MPF, while our paper uses IPF. Moreover, we develop constraint programming and genetic algorithm models.


## 2.3. Constraint Programming

Hiller and Lieberman [39] noted that no presentation of the basic ideas of MILP is complete these days without introducing CP––that is promising to greatly expand our ability to formulate and solve various scheduling problems. CP has been applied to various scheduling problems, demonstrating a rapid computational speed. The search within IBM CPLEX CP Optimizer is equipped with the presolve functionality, some constraint propagation algorithms, temporal linear relaxation used to guide the search, and two search space exploration strategies that are used concurrently: the large neighborhood search for producing good quality solutions and failure-directed search for proving infeasibility or optimality [40].


## 3. Problem Description and Solutions

Consider a flexible job shop environment that consists of a set of heterogeneous machines (k∈K) and a set of jobs (i∈I). Each job i consists of a set of operations (Ji=1,…,ni). Each operation needs to be processed in a specific order (known as precedence constraints) for a given job. A machine can perform at most one operation at a time. Each operation must be processed by one of qualified machines. In addition to the standard FJSP problem, an amount of energy consumption is considered in this energy-aware scheduling approach. The energy is consumed during production, idle, and shutdown. The production requires the highest amount of energy, while the idle does the medium and the shutdown requires the lowest. In particular, the shutdown can be enforced when a continuous idle period of a machine is expected to be long enough to compensate the shutdown penalty. When idle times are inevitable, the key is to adjust small-size idle intervals and locate them in a single large-size interval to turn on a long-size shutdown.


### 3.1. Mixed Integer Linear Programing Models

Meng et al. [9] presented six MILP models for our problem and showed that the second model outperforms all the other models through the numerical experiments. We term this efficient model MILP-2. Despite the superiority of MILP-2, we found that it can be further improved during the implementation by employing tuples instead of arrays, thus dramatically reducing the number of binary decision variables. For instance, the MILP-2 uses a binary variable Yi,j,k,t that represents whether the j-th operation of job i is processed at the t-th position of machine k. This variable is a sparse array, in which most of the elements are zero. Moreover, Meng et al. [9] set the maximum number of the positions of machine k (denoted by mk) to the total number of operations (∑i∈Ini), which is excessively large. We set mk to the number of operations that machine k can process in the instance. By taking those measures, we were able to reduce the number of binary variables by 50–60% in the same instances. We term this efficient model MILP-2A.MILP-2 is an extension of MPF for FJSP so that energy consumption can be considered. However, Demir and Kürşat Isleyen [17] showed that MPF is the slowest model among alternative models. Choi and Choi [15] proposed a new immediate precedence formulation (IPF) that decides whether one operation immediately precedes the other as shown in Figure 1.Figure 1
An illustration of immediate precedence formulation using a decision variableWo,q.Now, we will propose a new model that improves IPF and extends it to account for energy consumption. We mostly use the same notations as Meng et al. [9]. The details are as follows.Parameters:I: set of jobs.ni: number of operations of job i∈I.Ji: set of operations of job i∈I, that is, Ji=1,…,ni.O: set of job and operation pairs, that is, O=i,j|i∈I,j∈Ji.K: set of all machines.Ko: set of machines which can process operation o∈O.po,k: processing time of o∈O by machine k∈Ko.Dk: the unit energy consumed at the idle time for machine k when the shutdown strategy is not usedP0: the unit energy consumed by a facility for lighting, heating, and cooling during the makespan.Eo,k: the energy consumed when operation o is processed by machine k.Nk: the maximum times of shutdown strategy for machine k.Gk: the energy consumption of machine k when the shutdown strategy is used.TBk: the breakeven period of machine k in which the same amount of energy is consumed during the idle time whether the shutdown strategy is used or not. Hence, TBk = Gk/Dk.Oq: the set of operations which can be processed by the same machine with operation q∈O.PO: the set of precedence operation pairs in the same job operations, that is, PO=o,q|o=i,j,q=i,j+1,i∈I,j=1,…,ni−1.M1=∑o∈Omaxpo,k|k∈Ko.M2=maxDk⋅TBk|k∈K.Decision variables:Xo,k: 1 if o∈O is processed by machine k∈Ko and 0 otherwise.So: start time of o∈O.Co: completion time of o∈O.Cmax: makespan, that is, Cmax=maxco|o=i,ni∈O.Vo: idle time after operation o∈O.Ro: energy consumption during Vo.Wo,q: 1 if o∈O immediately precedes q∈O on the same machine and 0 otherwise.Zo,k: 1 if turning shutdown strategy is implemented during Vo on machine k∈Ko and 0 otherwise.Qo,k: 1 if o∈O is processed last on machine k∈Ko and 0 otherwise.


#### 3.1.1. MILP-3 for Energy-Aware Flexible Job Shop Scheduling

(1)Min∑o∈O∑k∈KoEo,kXo,k+∑o∈ORo+P0Cmax,(2)∑k∈KoXo,k=1,∀o∈O,(3)Co=So+∑k∈Kopo,kXo,k,∀o∈O,(4)Sq≥Co,∀o,q∈PO,(5)Cmax≥Co,∀o=i,ni∈O,(6)∑o∈OQo,k≤1,∀k∈K,(7)∑o∈OqWo,q≤1,∀q∈O,(8)∑q∈OoWo,q+∑k∈KoQo,k=1,∀o∈O,(9)Wo,q−1≤Xo,k−Xq,k,∀o∈O,q∈Oo,k∈Ko∩Kq,(10)Xo,k−Xq,k≤1−Wo,q,∀o∈O,q∈Oo,k∈Ko∩Kq,(11)∑k∈Ko∩KqXo,k≥Wo,q,∀o∈O,q∈Oo,(12)∑k∈Ko∩KqXq,k≥Wo,q,∀o∈O,q∈Oo,(13)Qo,k≤Xo,k,∀o∈O,k∈Ko,(14)Sq≥Co+M1Wo,q−1,∀o∈O,q∈Oo,(15)Vo≤M11−∑k∈KoQo,k,∀o∈O,(16)Vo≤Sq−Co+M11−Wo,q,∀o∈O,q∈Oo,(17)Vo≥Sq−Co−M11−Wo,q,∀o∈O,q∈Oo,(18)∑o∈OZo,k≤Nk,∀k∈K,(19)Vo≥TBkZo,k,∀o∈O,k∈Ko,(20)Ro≥GkZo,k,∀o∈O,k∈Ko,(21)Ro≥DkVo+M2Xo,k−Zo,k−1,∀o∈O,k∈Ko,(22)Zo,k≤Xo,k,∀o∈O,k∈Ko,(23)Zo,k≤1−Qo,k,∀o∈O,k∈Ko.Objective (1) is to minimize the total energy, which is consumed for production, idle (including shutdown), and common. Constraint (2) ensures that each operation is processed by exactly one machine. Constraint (3) links the completion time of an operation with its starting time. Constraint (4) enforces that each operation starts after its precedent operation is finished. Constraint (5) indicates the makespan. Constraint (6) imposes that each machine has at most one last job. Constraint (7) imposes that each operation has at most one immediate precedence operation. Constraint (8) imposes that each operation has an immediate next operation or it is the last operation on some machine. Constraints (9)–(12) encode that if o immediately precedes q, then they should be processed by the same machine. Constraint (13) imposes that o can be the last job of machine k only when machine k processes o. Constraint (14) enforces that operation q starts after the completion of operation o if it is processed immediately after operation o on the same machine. Constraint (15) imposes that idle time of the last job is zero. Constraints (16)–(17) compute the idle time Vo of o. Constraint (18) restricts the number of times of shutdown strategy in machine k. Constraint (19) restricts the minimum length of Vowhen shutdown strategy is used during Vo. Constraints (20)–(21) compute the idle energy consumption during Vo. Constraints (22)–(23) enforce that shutdown strategy can be turned during Vo on machine k only when o is processed by machine k and it is not the last operation of machine k. We term this newly proposed model MILP-3.


### 3.2. Constraint Programming

All time durations, such as makespan, shutdowns, and productions, are explicitly modeled as the interval variables as shown in Figure2.Figure 2
Modeling overview.As Ham [41] pointed out, there is no standard in CP formulation, unlike a similar MILP formulation. Therefore, this paper formulates the model using generic keywords and syntaxes as we refer to the CP formulations by Laborie et al. [40] and IBM ILOG CP Optimizer [42].The proposed CP model is built upon the following decision variables:Zk,s: interval representing s-th shutdown on machine k∈KCk: interval representing makespan of k∈KTo: interval representing operation o∈OXo,k: interval representing operation o∈O on machine k∈KoSeqk←Xo,k: collection of variables assigned to machine keS: total energy consumption during shutdownseP: total energy consumption during productionseI: total energy consumption during idleseC: total common energy consumption


#### 3.2.1. CP-1

(24)MineP+eS+eI+eC,(25)alternativeTo,Xo,k:k∈Ko,∀o∈O,(26)endBeforeStartTo,Tq,∀o,q∈PO,(27)noOverlapSeqk,∀k∈K,(28)spanCk,Xo,k:o∈O,k∈K,∀k∈K,(29)startOfZk,s>startOfCk,∀k∈K,s≤Nk,(30)endOfZk,s<endOfCk,∀k∈K,s≤Nk,(31)sizeOfZk,s≥TBk,∀k∈K,s≤Nk,(32)eP=∑o∈O∑k∈KoEo,ksizeOfTo,(33)eS=Gk∑k∈Ko∑s≤NkpresenceOfZk,s,(34)eI=Dk∑k∈KsizeOfCk−∑s≤NksizeOfZk,s−∑o∈OsizeOfXo,k,(35)eC=P0Max∀o∈OendOfTo.Objective (24) is to minimize the total energy consumption, which is comprised of production, shutdown, idle, and common. Constraint (25) ensures that each operation is processed by exactly one machine. Constraint (26) enforces each operation starts after its precedent operation is finished. Constraint (27) prevents intervals in a sequence from overlapping. Constraint (28) determines the makespan of each machine. Constraints (29)–(30) ensure that a shutdown can occur during a makespan. Constraint (31) ensures the minimum length of each shutdown. Constraints (32)–(35) compute the total energy consumption for production, shutdown, idle, and common, respectively. We term this model CP-1.During the preliminary study, the CP-1 could not outperform the MILP-2A model. Here, we explored an alternative CP model. In the CP-1, the idle time was computed based on other interval variables in Constraint (34). We here present an alternative CP model, which explicitly captures the idle intervals.Ik,t: interval representing t-th idle on machine k∈K.(36)eI=Dk∑k∈K∑t≤mksizeOfIk,t,(37)sizeOfCk=∑o∈OsizeOfXo,k+∑s≤NksizeOfZk,s+∑t≤mksizeOfIk,t.Constraint (36) replaces Constraint (34). Then, Constraint (37) is introduced to ensure that a makespan of the machine must be packed by productions, shutdowns, and idles. All other constraints stay in place. We term this revised model CP-2.Figure3 represents an optimal schedule for a small benchmark instance (mfjs07). Figure 3(a) shows the detailed production schedule per machine with an objective of makespan minimization, and Figure 3(b) depicts the schedule with an objective of energy minimization, while maintaining the same productivity. The proposed model merges the small-size idles enough to turn on shutdown strategy. For instance, the two idles that occurred in machine 4 are replaced by a single shutdown in the same machine. The energy-aware scheduling saved the energy consumption by 1.35% without hurting productivity in the mfjs07 instance.Figure 3
Schedules for the mfjs07 instance. (a) Traditional scheduling to minimizeCmax. (b) Energy-aware scheduling to minimize energy consumption while keeping the same productivity.
(a)(b)


## 3.1. Mixed Integer Linear Programing Models

Meng et al. [9] presented six MILP models for our problem and showed that the second model outperforms all the other models through the numerical experiments. We term this efficient model MILP-2. Despite the superiority of MILP-2, we found that it can be further improved during the implementation by employing tuples instead of arrays, thus dramatically reducing the number of binary decision variables. For instance, the MILP-2 uses a binary variable Yi,j,k,t that represents whether the j-th operation of job i is processed at the t-th position of machine k. This variable is a sparse array, in which most of the elements are zero. Moreover, Meng et al. [9] set the maximum number of the positions of machine k (denoted by mk) to the total number of operations (∑i∈Ini), which is excessively large. We set mk to the number of operations that machine k can process in the instance. By taking those measures, we were able to reduce the number of binary variables by 50–60% in the same instances. We term this efficient model MILP-2A.MILP-2 is an extension of MPF for FJSP so that energy consumption can be considered. However, Demir and Kürşat Isleyen [17] showed that MPF is the slowest model among alternative models. Choi and Choi [15] proposed a new immediate precedence formulation (IPF) that decides whether one operation immediately precedes the other as shown in Figure 1.Figure 1
An illustration of immediate precedence formulation using a decision variableWo,q.Now, we will propose a new model that improves IPF and extends it to account for energy consumption. We mostly use the same notations as Meng et al. [9]. The details are as follows.Parameters:I: set of jobs.ni: number of operations of job i∈I.Ji: set of operations of job i∈I, that is, Ji=1,…,ni.O: set of job and operation pairs, that is, O=i,j|i∈I,j∈Ji.K: set of all machines.Ko: set of machines which can process operation o∈O.po,k: processing time of o∈O by machine k∈Ko.Dk: the unit energy consumed at the idle time for machine k when the shutdown strategy is not usedP0: the unit energy consumed by a facility for lighting, heating, and cooling during the makespan.Eo,k: the energy consumed when operation o is processed by machine k.Nk: the maximum times of shutdown strategy for machine k.Gk: the energy consumption of machine k when the shutdown strategy is used.TBk: the breakeven period of machine k in which the same amount of energy is consumed during the idle time whether the shutdown strategy is used or not. Hence, TBk = Gk/Dk.Oq: the set of operations which can be processed by the same machine with operation q∈O.PO: the set of precedence operation pairs in the same job operations, that is, PO=o,q|o=i,j,q=i,j+1,i∈I,j=1,…,ni−1.M1=∑o∈Omaxpo,k|k∈Ko.M2=maxDk⋅TBk|k∈K.Decision variables:Xo,k: 1 if o∈O is processed by machine k∈Ko and 0 otherwise.So: start time of o∈O.Co: completion time of o∈O.Cmax: makespan, that is, Cmax=maxco|o=i,ni∈O.Vo: idle time after operation o∈O.Ro: energy consumption during Vo.Wo,q: 1 if o∈O immediately precedes q∈O on the same machine and 0 otherwise.Zo,k: 1 if turning shutdown strategy is implemented during Vo on machine k∈Ko and 0 otherwise.Qo,k: 1 if o∈O is processed last on machine k∈Ko and 0 otherwise.


### 3.1.1. MILP-3 for Energy-Aware Flexible Job Shop Scheduling

(1)Min∑o∈O∑k∈KoEo,kXo,k+∑o∈ORo+P0Cmax,(2)∑k∈KoXo,k=1,∀o∈O,(3)Co=So+∑k∈Kopo,kXo,k,∀o∈O,(4)Sq≥Co,∀o,q∈PO,(5)Cmax≥Co,∀o=i,ni∈O,(6)∑o∈OQo,k≤1,∀k∈K,(7)∑o∈OqWo,q≤1,∀q∈O,(8)∑q∈OoWo,q+∑k∈KoQo,k=1,∀o∈O,(9)Wo,q−1≤Xo,k−Xq,k,∀o∈O,q∈Oo,k∈Ko∩Kq,(10)Xo,k−Xq,k≤1−Wo,q,∀o∈O,q∈Oo,k∈Ko∩Kq,(11)∑k∈Ko∩KqXo,k≥Wo,q,∀o∈O,q∈Oo,(12)∑k∈Ko∩KqXq,k≥Wo,q,∀o∈O,q∈Oo,(13)Qo,k≤Xo,k,∀o∈O,k∈Ko,(14)Sq≥Co+M1Wo,q−1,∀o∈O,q∈Oo,(15)Vo≤M11−∑k∈KoQo,k,∀o∈O,(16)Vo≤Sq−Co+M11−Wo,q,∀o∈O,q∈Oo,(17)Vo≥Sq−Co−M11−Wo,q,∀o∈O,q∈Oo,(18)∑o∈OZo,k≤Nk,∀k∈K,(19)Vo≥TBkZo,k,∀o∈O,k∈Ko,(20)Ro≥GkZo,k,∀o∈O,k∈Ko,(21)Ro≥DkVo+M2Xo,k−Zo,k−1,∀o∈O,k∈Ko,(22)Zo,k≤Xo,k,∀o∈O,k∈Ko,(23)Zo,k≤1−Qo,k,∀o∈O,k∈Ko.Objective (1) is to minimize the total energy, which is consumed for production, idle (including shutdown), and common. Constraint (2) ensures that each operation is processed by exactly one machine. Constraint (3) links the completion time of an operation with its starting time. Constraint (4) enforces that each operation starts after its precedent operation is finished. Constraint (5) indicates the makespan. Constraint (6) imposes that each machine has at most one last job. Constraint (7) imposes that each operation has at most one immediate precedence operation. Constraint (8) imposes that each operation has an immediate next operation or it is the last operation on some machine. Constraints (9)–(12) encode that if o immediately precedes q, then they should be processed by the same machine. Constraint (13) imposes that o can be the last job of machine k only when machine k processes o. Constraint (14) enforces that operation q starts after the completion of operation o if it is processed immediately after operation o on the same machine. Constraint (15) imposes that idle time of the last job is zero. Constraints (16)–(17) compute the idle time Vo of o. Constraint (18) restricts the number of times of shutdown strategy in machine k. Constraint (19) restricts the minimum length of Vowhen shutdown strategy is used during Vo. Constraints (20)–(21) compute the idle energy consumption during Vo. Constraints (22)–(23) enforce that shutdown strategy can be turned during Vo on machine k only when o is processed by machine k and it is not the last operation of machine k. We term this newly proposed model MILP-3.


## 3.1.1. MILP-3 for Energy-Aware Flexible Job Shop Scheduling

(1)Min∑o∈O∑k∈KoEo,kXo,k+∑o∈ORo+P0Cmax,(2)∑k∈KoXo,k=1,∀o∈O,(3)Co=So+∑k∈Kopo,kXo,k,∀o∈O,(4)Sq≥Co,∀o,q∈PO,(5)Cmax≥Co,∀o=i,ni∈O,(6)∑o∈OQo,k≤1,∀k∈K,(7)∑o∈OqWo,q≤1,∀q∈O,(8)∑q∈OoWo,q+∑k∈KoQo,k=1,∀o∈O,(9)Wo,q−1≤Xo,k−Xq,k,∀o∈O,q∈Oo,k∈Ko∩Kq,(10)Xo,k−Xq,k≤1−Wo,q,∀o∈O,q∈Oo,k∈Ko∩Kq,(11)∑k∈Ko∩KqXo,k≥Wo,q,∀o∈O,q∈Oo,(12)∑k∈Ko∩KqXq,k≥Wo,q,∀o∈O,q∈Oo,(13)Qo,k≤Xo,k,∀o∈O,k∈Ko,(14)Sq≥Co+M1Wo,q−1,∀o∈O,q∈Oo,(15)Vo≤M11−∑k∈KoQo,k,∀o∈O,(16)Vo≤Sq−Co+M11−Wo,q,∀o∈O,q∈Oo,(17)Vo≥Sq−Co−M11−Wo,q,∀o∈O,q∈Oo,(18)∑o∈OZo,k≤Nk,∀k∈K,(19)Vo≥TBkZo,k,∀o∈O,k∈Ko,(20)Ro≥GkZo,k,∀o∈O,k∈Ko,(21)Ro≥DkVo+M2Xo,k−Zo,k−1,∀o∈O,k∈Ko,(22)Zo,k≤Xo,k,∀o∈O,k∈Ko,(23)Zo,k≤1−Qo,k,∀o∈O,k∈Ko.Objective (1) is to minimize the total energy, which is consumed for production, idle (including shutdown), and common. Constraint (2) ensures that each operation is processed by exactly one machine. Constraint (3) links the completion time of an operation with its starting time. Constraint (4) enforces that each operation starts after its precedent operation is finished. Constraint (5) indicates the makespan. Constraint (6) imposes that each machine has at most one last job. Constraint (7) imposes that each operation has at most one immediate precedence operation. Constraint (8) imposes that each operation has an immediate next operation or it is the last operation on some machine. Constraints (9)–(12) encode that if o immediately precedes q, then they should be processed by the same machine. Constraint (13) imposes that o can be the last job of machine k only when machine k processes o. Constraint (14) enforces that operation q starts after the completion of operation o if it is processed immediately after operation o on the same machine. Constraint (15) imposes that idle time of the last job is zero. Constraints (16)–(17) compute the idle time Vo of o. Constraint (18) restricts the number of times of shutdown strategy in machine k. Constraint (19) restricts the minimum length of Vowhen shutdown strategy is used during Vo. Constraints (20)–(21) compute the idle energy consumption during Vo. Constraints (22)–(23) enforce that shutdown strategy can be turned during Vo on machine k only when o is processed by machine k and it is not the last operation of machine k. We term this newly proposed model MILP-3.


## 3.2. Constraint Programming

All time durations, such as makespan, shutdowns, and productions, are explicitly modeled as the interval variables as shown in Figure2.Figure 2
Modeling overview.As Ham [41] pointed out, there is no standard in CP formulation, unlike a similar MILP formulation. Therefore, this paper formulates the model using generic keywords and syntaxes as we refer to the CP formulations by Laborie et al. [40] and IBM ILOG CP Optimizer [42].The proposed CP model is built upon the following decision variables:Zk,s: interval representing s-th shutdown on machine k∈KCk: interval representing makespan of k∈KTo: interval representing operation o∈OXo,k: interval representing operation o∈O on machine k∈KoSeqk←Xo,k: collection of variables assigned to machine keS: total energy consumption during shutdownseP: total energy consumption during productionseI: total energy consumption during idleseC: total common energy consumption


### 3.2.1. CP-1

(24)MineP+eS+eI+eC,(25)alternativeTo,Xo,k:k∈Ko,∀o∈O,(26)endBeforeStartTo,Tq,∀o,q∈PO,(27)noOverlapSeqk,∀k∈K,(28)spanCk,Xo,k:o∈O,k∈K,∀k∈K,(29)startOfZk,s>startOfCk,∀k∈K,s≤Nk,(30)endOfZk,s<endOfCk,∀k∈K,s≤Nk,(31)sizeOfZk,s≥TBk,∀k∈K,s≤Nk,(32)eP=∑o∈O∑k∈KoEo,ksizeOfTo,(33)eS=Gk∑k∈Ko∑s≤NkpresenceOfZk,s,(34)eI=Dk∑k∈KsizeOfCk−∑s≤NksizeOfZk,s−∑o∈OsizeOfXo,k,(35)eC=P0Max∀o∈OendOfTo.Objective (24) is to minimize the total energy consumption, which is comprised of production, shutdown, idle, and common. Constraint (25) ensures that each operation is processed by exactly one machine. Constraint (26) enforces each operation starts after its precedent operation is finished. Constraint (27) prevents intervals in a sequence from overlapping. Constraint (28) determines the makespan of each machine. Constraints (29)–(30) ensure that a shutdown can occur during a makespan. Constraint (31) ensures the minimum length of each shutdown. Constraints (32)–(35) compute the total energy consumption for production, shutdown, idle, and common, respectively. We term this model CP-1.During the preliminary study, the CP-1 could not outperform the MILP-2A model. Here, we explored an alternative CP model. In the CP-1, the idle time was computed based on other interval variables in Constraint (34). We here present an alternative CP model, which explicitly captures the idle intervals.Ik,t: interval representing t-th idle on machine k∈K.(36)eI=Dk∑k∈K∑t≤mksizeOfIk,t,(37)sizeOfCk=∑o∈OsizeOfXo,k+∑s≤NksizeOfZk,s+∑t≤mksizeOfIk,t.Constraint (36) replaces Constraint (34). Then, Constraint (37) is introduced to ensure that a makespan of the machine must be packed by productions, shutdowns, and idles. All other constraints stay in place. We term this revised model CP-2.Figure3 represents an optimal schedule for a small benchmark instance (mfjs07). Figure 3(a) shows the detailed production schedule per machine with an objective of makespan minimization, and Figure 3(b) depicts the schedule with an objective of energy minimization, while maintaining the same productivity. The proposed model merges the small-size idles enough to turn on shutdown strategy. For instance, the two idles that occurred in machine 4 are replaced by a single shutdown in the same machine. The energy-aware scheduling saved the energy consumption by 1.35% without hurting productivity in the mfjs07 instance.Figure 3
Schedules for the mfjs07 instance. (a) Traditional scheduling to minimizeCmax. (b) Energy-aware scheduling to minimize energy consumption while keeping the same productivity.
(a)(b)


## 3.2.1. CP-1

(24)MineP+eS+eI+eC,(25)alternativeTo,Xo,k:k∈Ko,∀o∈O,(26)endBeforeStartTo,Tq,∀o,q∈PO,(27)noOverlapSeqk,∀k∈K,(28)spanCk,Xo,k:o∈O,k∈K,∀k∈K,(29)startOfZk,s>startOfCk,∀k∈K,s≤Nk,(30)endOfZk,s<endOfCk,∀k∈K,s≤Nk,(31)sizeOfZk,s≥TBk,∀k∈K,s≤Nk,(32)eP=∑o∈O∑k∈KoEo,ksizeOfTo,(33)eS=Gk∑k∈Ko∑s≤NkpresenceOfZk,s,(34)eI=Dk∑k∈KsizeOfCk−∑s≤NksizeOfZk,s−∑o∈OsizeOfXo,k,(35)eC=P0Max∀o∈OendOfTo.Objective (24) is to minimize the total energy consumption, which is comprised of production, shutdown, idle, and common. Constraint (25) ensures that each operation is processed by exactly one machine. Constraint (26) enforces each operation starts after its precedent operation is finished. Constraint (27) prevents intervals in a sequence from overlapping. Constraint (28) determines the makespan of each machine. Constraints (29)–(30) ensure that a shutdown can occur during a makespan. Constraint (31) ensures the minimum length of each shutdown. Constraints (32)–(35) compute the total energy consumption for production, shutdown, idle, and common, respectively. We term this model CP-1.During the preliminary study, the CP-1 could not outperform the MILP-2A model. Here, we explored an alternative CP model. In the CP-1, the idle time was computed based on other interval variables in Constraint (34). We here present an alternative CP model, which explicitly captures the idle intervals.Ik,t: interval representing t-th idle on machine k∈K.(36)eI=Dk∑k∈K∑t≤mksizeOfIk,t,(37)sizeOfCk=∑o∈OsizeOfXo,k+∑s≤NksizeOfZk,s+∑t≤mksizeOfIk,t.Constraint (36) replaces Constraint (34). Then, Constraint (37) is introduced to ensure that a makespan of the machine must be packed by productions, shutdowns, and idles. All other constraints stay in place. We term this revised model CP-2.Figure3 represents an optimal schedule for a small benchmark instance (mfjs07). Figure 3(a) shows the detailed production schedule per machine with an objective of makespan minimization, and Figure 3(b) depicts the schedule with an objective of energy minimization, while maintaining the same productivity. The proposed model merges the small-size idles enough to turn on shutdown strategy. For instance, the two idles that occurred in machine 4 are replaced by a single shutdown in the same machine. The energy-aware scheduling saved the energy consumption by 1.35% without hurting productivity in the mfjs07 instance.Figure 3
Schedules for the mfjs07 instance. (a) Traditional scheduling to minimizeCmax. (b) Energy-aware scheduling to minimize energy consumption while keeping the same productivity.
(a)(b)


## 4. Computational Experiments

In this section, the effectiveness of the proposed models is examined. The MILP, CP, and flow control models are all coded in IBM OPL 12.8.0 on a personal computer with an Intel® Core i7-4770 CPU with 16 GB of RAM. All the test instances, MILP codes, CP codes in IBM OPL, and GA code can be found online athttps://github.com/hamcruise/FJSP-Shutdown.


### 4.1. Problem Instances

Meng et al. [9] proposed a set of test instances derived from the known benchmark instances SFJS01-10 and MFJS01-10 [12] by considering energy consumption. We adopted the same test instances. SFJS01-10 are small-sized, and MFJS01-10 are medium-sized. We also adopted another FJSP benchmark test instance suggested by Behnke and Geiger [43]. Among their extensive 60 instances, we adopted the first 10 instances and added energy parameters in the same way Meng et al. [9] did. Finally, we also used another FJSP benchmark test instance suggested by Kacem et al. [44], which has been adopted by Singh and Mahapatra [45]. The detailed size of the instance (a/b/c) is recorded in Table 2, where index a denotes the number of jobs, b denotes the maximum number of operations for a job, and c denotes the number of machines.Table 2
Characteristics of the test instances.
Fattahi instancesBehnke instancesNameSizeNameSizeNameSizesfjs012/2/2mfjs015/3/6Behnke110/3/20sfjs022/2/2mfjs025/3/7Behnke210/3/20sfjs033/2/2mfjs036/3/7Behnke310/3/20sfjs043/2/2mfjs047/3/7Behnke410/3/20sfjs053/2/2mfjs057/3/7Behnke510/3/20sfjs063/3/2mfjs068/3/7Behnke620/3/20sfjs073/3/5mfjs078/4/7Behnke720/3/20sfjs083/3/4mfjs089/4/8Behnke820/3/20sfjs093/3/3mfjs0911/4/8Behnke920/3/20sfjs104/3/5mfjs1012/4/8Behnke1020/3/20Kacem instancesNameSizeNameSizeNameSizeKacem18/4/8Kacem210/3/10Kacem315/4/10For all instances, the common powerP0 and maximum times of shutdown (Nk) are set to be 5 and 3, respectively. The processing powers are drawn from the uniform distribution [3, 5]. The idle power Dk is randomly generated from the set {1, 2, 3}, and the energy consumption during shutdown (Gk) is generated from the set {10, 30, 60}.


### 4.2. Experimental Results

Figure4 shows the ratio of the number of binary variables of MILP models to MILP-2. As the size of MILP-2 increases, the binary variables of MILP-2A and MILP-3 decrease. In particular, it is observed that the reduction ratio of the binary variable of MILP-3 sharply decreases as the size increases.Figure 4
Comparison of the number of binary variables of MILP models.In this subsection, we implemented a genetic algorithm to compare the performance between proposed methods and metaheuristic. Genetic algorithm (GA) is known as an effective metaheuristic to solve flexible job shop scheduling problems [46–49]. The overall GA framework in Zhang et al. [50] was adopted. We had conducted a preliminary test for tuning hyperparameters with respect to the quadruple (popSize, numGen, crRate, mutRate), where popSize is the population size (popSize ∈ {100, 200, 400}), numGen is the maximum number of generations (numGen ∈ {50, 100, 200}), crRate is the crossover rate (crRate ∈ {0.6, 0.7, 0.8, 0.9, 1.0}), and mutRate is the mutation rate (mutRate ∈ {0.0, 0.1, 0.2, 0.3}). The best GA hyperparameters that were obtained from the preliminary test were as follows: popSize = 100, numGen = 50, crRate = 0.7, and mutRate = 0.1. The increasing population size and number of generations did not ensure obtaining better solutions. The value of the fitness function converged fast in practice.Tables3 and 4 compare the proposed MILP and GA with CP models in terms of the objective function value (total energy consumption) and computation times within 600 seconds for Fattahi and Behnke’s instances, respectively. Column 1 identifies the name of the instance, columns 2–7 include the total energy consumption, and columns 8–13 report the computation times. The bold font indicates the optimality.Table 3
Comparison of models in terms of total cost and computation times on Fattahi instances.
InstanceTotal energy consumptionComputation time (second)CP-1CP-2MILP-2MILP-2AMILP-3GACP-1CP-2MILP-2MILP-2AMILP-3GAsfjs01815.2815.2815.2815.2815.2815.254.60.30.00.00.00.2sfjs021362.21362.21362.21362.21362.21362.265.40.30.00.00.00.2sfjs032806.22806.22806.22806.22806.22806.2507.30.30.00.00.00.2sfjs044560.34560.34560.34560.34560.34560.3600.10.30.00.00.00.2sfjs051405.41405.41405.41405.41405.41405.4547.70.30.00.00.00.2sfjs064304.64304.64304.64304.64304.64420.6600.10.30.10.00.00.3sfjs075256.05256.05256.05256.05256.05345.2600.00.30.10.00.00.3sfjs083429.73429.73429.73429.73429.73477.7600.00.30.30.10.00.3sfjs092848.02848.02848.02848.02848.03023.2600.20.40.10.10.10.3sfjs108877.08877.08877.08877.08877.08877600.00.40.10.00.00.4mfjs019380.79380.79380.79380.79380.79981.2600.0600.12.90.81.60.5mfjs028642.08642.08642.08642.08642.09082600.0600.02.81.11.90.5mfjs0310799.410762.810757.810757.810757.811700600.0600.035.34.710.80.6mfjs0413075.913038.613038.613038.613038.613696600.0600.1117.527.382.30.6mfjs0512744.412600.112600.112600.112600.113579.1600.0600.193.323.7426.80.6mfjs0615169.714960.114960.114960.114960.116257.5600.0600.149.616.752.00.7mfjs0720842.120542.121098.320990.321179.621884.9600.0600.0607.5600.2600.31.0mfjs0824295.023763.824289.623999.023993.425812.3600.0600.1601.8600.3600.31.0mfjs0930999.429788.131386.730882.530846.432237.1600.1600.0601.1600.5600.11.2mfjs1034946.834410.736794.535168.637136.637293.6600.0600.1600.4601.6600.81.5Average10828.010677.710930.710804.210910.011380.8538.8300.2135.7123.9148.90.5Table 4
Comparison of models in terms of total cost and computation times on Behnke instances.
InstanceTotal energy consumptionComputation time (second)CP-1CP-2MILP-2MILP-2AMILP-3GACP-1CP-2MILP-2MILP-2AMILP-3GABehnke11839.21795.81795.81795.81795.81889.3600.0600.1600.1104.6600.11.1Behnke21787.81768.01763.91763.91763.91884.6600.0600.1318.3167.3180.81.1Behnke31752.41749.91749.91749.91749.91902.6600.0600.2332.655.3309.21.1Behnke42012.41964.21961.41945.91950.42082.9600.0600.1600.2379.7600.11.1Behnke51928.21865.71867.31865.71872.62101.1600.0600.1600.3124.4600.11.0Behnke63565.13354.13385.83361.33381.63637.7600.1600.2600.4600.2600.12.2Behnke73875.43483.13475.33454.63455.23734.9600.0600.2602.7600.3600.32.2Behnke83701.73445.23509.63474.43521.33774.9600.0600.3604.4600.4600.31.9Behnke93526.53326.63324.43294.43340.03579.2600.0600.3600.4600.3600.22.1Behnke104150.03703.43742.83705.73784.63916.8600.0600.3603.3600.4600.32.1Average2813.92645.62657.62641.22661.52850.4600.0600.2546.3383.3529.11.6Table3 reports the results based on Fattahi’s instances. For small-sized instances (SFJS01-10), all approaches found the optimal solutions, except GA. In computation times, all approaches, except CP-1, terminated in one second. For medium-sized instances (MFJS01-10), CP-2 yielded the best results on average. In computation times, GA significantly outperforms all other approaches seconds. However, MILP-2, MILP-2A, and MILP-3 terminated at a similar time.Table4 reports the results based on Behnke’s instances. The proposed MILP-2A performed the best in average. GA is significantly faster than the MILP and CP approaches. However, the total energy consumption is increased up to 8.1% on average.In order to determine if the means of two sets of data are significantly different from each other, we conducted thet-test: Paired Two-Sample for Means at an alpha level of 0.05. Table 5 indicates that, for medium-sized Fattahi’s instances, there is a statistically significant difference between CP-2 vs. CP-1 and GA, while there is no statistically significant difference between CP-2 vs. MILP-2, MILP-2A, and MILP-3. For Behnke’s instances, there is a statistically significant difference between MILP-2A vs. CP-1, MILP-2, MILP-2A, MILP-3, and GA methods, while there is no statistically significant difference between MILP-2A and CP-2.Table 5
Comparison of models in terms oft-test: paired two-sample for means.
CP-2 vs.Medium-sized Fattahi instances (MFJS01-10)MILP-2A vs.Behnke instancesCP-1MILP-2MILP-2AMILP-3GACP-1CP-2MILP-2MILP-3GAt-value t (9)−2.511−1.918−2.038−1.684−5.185t-value t (9)−3.387−0.780−3.426−2.337−8.547p-value0.03330.08740.07200.12650.0006p-value0.00800.45520.00760.04420.0000The previous tables compared the performance of models with a fixed computation time. It is necessary to check how the performance changes according to different computation times. Table6 summarizes the total energy consumption in terms of computational run time for the Kacem’s instances. Both CP and MILP models proved the optimality of Kacem1 instance within 60 s. CP managed to prove the optimality of Kacem2 instance within 60 s, while MILP spent 150 s. In the Kacem3 instance, the CP-2 found an optimal solution within 60 s, while MILP-2A could not find an optimal solution within 600 s. In addition, the CP-2 found a much better solution, in just 10 seconds, than the one MILP-2A found in 600 seconds. This experiment demonstrates that CP is quick to generate efficient (or optimal) solutions.Table 6
Comparison of models in terms of total energy consumption according to different CPU times.
InstanceModelCPU (sec)10306090120150180300600Kacem1CP-2407.5401.4393.4——————MILP-2A443.0408.6393.4——————GA422.6Kacem2CP-2205.8202.2200.8——————MILP-2A238.6220.8215.5210.0201.5200.8———GA227.5Kacem3CP-2520.2435.8435.8435.8435.8435.8435.8435.8435.8MILP-2A1909.21908.11908.11908.11908.11908.11908.11908.11908.1GA501.8The energy saving does not appeal to highly capitalized manufacturing industries, such as automobiles and semiconductors, because the total energy cost is not even comparable to the revenue the manufacturers yield, so their sole goal is to maximize productivity. However, if we can maintain the same productivity, while significantly reducing energy consumption, the energy-aware production scheduling will be embraced by the industries. This type of mathematical approach is known as epsilon-constraint method, where one of the objectives is taken as a single objective function and the others are included into a model as constraint [51].Tables7 and 8 attempt to meet this demand by comparing the traditional scheduling and energy-aware scheduling. The traditional scheduling minimizes the makespan (cycle time reduction), whereas the energy-aware scheduling minimizes the total energy consumption as it maintains the same makespan. Column 1 identifies the name of the instance. Column 2 reports the total energy consumption when the model solves each test instance with the makespan minimization. Columns 3-4 report the total energy consumption when the model runs with the energy consumption minimization with the same makespan. This experimentation identifies potential energy-saving without compromising productivity. For Fattahi’s instances, Table 7 shows 1.57% and 1.69% saving without and with shutdown strategy, respectively. The mild saving can be explained by the test instance itself.Table 7
Potential energy saving based on Fattahi instances.
InstanceTotal energy consumptionEnergy savingTraditionEnergy-aware schedulingEnergy-aware schedulingw/o shutdownw/ shutdownw/o shutdown (%)w/ shutdown (%)sfjs01815.2815.2815.20.000.00sfjs021362.21362.21362.20.000.00sfjs032806.22806.22806.20.000.00sfjs044560.34560.34560.30.000.00sfjs051405.41405.41405.40.000.00sfjs064630.64360.64360.65.835.83sfjs075530.25304.25304.24.094.09sfjs083599.23599.23599.20.000.00sfjs093121.02951.02951.05.455.45sfjs109217.88893.08877.03.523.70mfjs019498.69468.69468.60.320.32mfjs029036.28918.28918.21.311.31mfjs0311410.011356.011278.00.471.16mfjs0413233.913163.913075.90.531.19mfjs0513333.613293.613293.60.300.30mfjs0616443.116086.716086.72.172.17mfjs0722072.921973.121775.10.451.35mfjs0824884.424509.624503.81.511.53mfjs0932144.431262.231262.22.742.74mfjs1035857.734874.934874.92.742.74Average1.571.69Table 8
Potential energy saving based on Behnke instances.
InstanceTotal energy consumptionEnergy savingTraditionEnergy-aware schedulingInstancew/o shutdownw/ shutdownw/o shutdown (%)w/ shutdown (%)Behnke12156.21809.91809.916.0616.06Behnke21955.21789.31789.38.498.49Behnke32106.11840.91796.312.5914.71Behnke42237.81945.91945.913.0413.04Behnke52125.11953.21953.28.098.09Behnke64356.73358.33358.322.9222.92Behnke74210.83543.73543.715.8415.84Behnke84200.73502.83502.816.6116.61Behnke94022.53341.83297.916.9218.01Behnke104558.53740.13714.517.9518.51Average14.8515.23Table8 reports the results of Behnke’s instances. This experimentation identified the potential energy-saving without compromising productivity by 14.85% (w/o shutdown) and 15.23% (w/shutdown). The increased savings compared with the ones with Fattahi’s instance are due to the size of this Behnke’s instance, allowing the solver the flexibility to find better solutions. In order to determine if the means of two sets of data are significantly different from each other, we conducted the t-test: Paired Two-Sample for Means at an alpha level of 0.05. The test indicates that there is a statistically significant difference between traditional and energy-aware methods with t (19) = 3.5 and p<0.01 in Fattahi’s instance and t (9) = 5.53 and p<0.001 in Behnke’s instance.Table9 records the amount of energy saving by applying the proposed energy-aware method according to different multipliers on Eo,k. This experimentation identified the potential energy-saving without compromising productivity by 6–8%. The improvement was slightly decreased as the multiplier was increased.Table 9
Energy saving according to different energy consumption.
InstanceEo,k (%)2Eo,k (%)3Eo,k (%)4Eo,k (%)Kacem110.59.59.28.9Kacem22.81.71.31.1Kacem311.49.78.98.6Average8.27.06.56.2


## 4.1. Problem Instances

Meng et al. [9] proposed a set of test instances derived from the known benchmark instances SFJS01-10 and MFJS01-10 [12] by considering energy consumption. We adopted the same test instances. SFJS01-10 are small-sized, and MFJS01-10 are medium-sized. We also adopted another FJSP benchmark test instance suggested by Behnke and Geiger [43]. Among their extensive 60 instances, we adopted the first 10 instances and added energy parameters in the same way Meng et al. [9] did. Finally, we also used another FJSP benchmark test instance suggested by Kacem et al. [44], which has been adopted by Singh and Mahapatra [45]. The detailed size of the instance (a/b/c) is recorded in Table 2, where index a denotes the number of jobs, b denotes the maximum number of operations for a job, and c denotes the number of machines.Table 2
Characteristics of the test instances.
Fattahi instancesBehnke instancesNameSizeNameSizeNameSizesfjs012/2/2mfjs015/3/6Behnke110/3/20sfjs022/2/2mfjs025/3/7Behnke210/3/20sfjs033/2/2mfjs036/3/7Behnke310/3/20sfjs043/2/2mfjs047/3/7Behnke410/3/20sfjs053/2/2mfjs057/3/7Behnke510/3/20sfjs063/3/2mfjs068/3/7Behnke620/3/20sfjs073/3/5mfjs078/4/7Behnke720/3/20sfjs083/3/4mfjs089/4/8Behnke820/3/20sfjs093/3/3mfjs0911/4/8Behnke920/3/20sfjs104/3/5mfjs1012/4/8Behnke1020/3/20Kacem instancesNameSizeNameSizeNameSizeKacem18/4/8Kacem210/3/10Kacem315/4/10For all instances, the common powerP0 and maximum times of shutdown (Nk) are set to be 5 and 3, respectively. The processing powers are drawn from the uniform distribution [3, 5]. The idle power Dk is randomly generated from the set {1, 2, 3}, and the energy consumption during shutdown (Gk) is generated from the set {10, 30, 60}.


## 4.2. Experimental Results

Figure4 shows the ratio of the number of binary variables of MILP models to MILP-2. As the size of MILP-2 increases, the binary variables of MILP-2A and MILP-3 decrease. In particular, it is observed that the reduction ratio of the binary variable of MILP-3 sharply decreases as the size increases.Figure 4
Comparison of the number of binary variables of MILP models.In this subsection, we implemented a genetic algorithm to compare the performance between proposed methods and metaheuristic. Genetic algorithm (GA) is known as an effective metaheuristic to solve flexible job shop scheduling problems [46–49]. The overall GA framework in Zhang et al. [50] was adopted. We had conducted a preliminary test for tuning hyperparameters with respect to the quadruple (popSize, numGen, crRate, mutRate), where popSize is the population size (popSize ∈ {100, 200, 400}), numGen is the maximum number of generations (numGen ∈ {50, 100, 200}), crRate is the crossover rate (crRate ∈ {0.6, 0.7, 0.8, 0.9, 1.0}), and mutRate is the mutation rate (mutRate ∈ {0.0, 0.1, 0.2, 0.3}). The best GA hyperparameters that were obtained from the preliminary test were as follows: popSize = 100, numGen = 50, crRate = 0.7, and mutRate = 0.1. The increasing population size and number of generations did not ensure obtaining better solutions. The value of the fitness function converged fast in practice.Tables3 and 4 compare the proposed MILP and GA with CP models in terms of the objective function value (total energy consumption) and computation times within 600 seconds for Fattahi and Behnke’s instances, respectively. Column 1 identifies the name of the instance, columns 2–7 include the total energy consumption, and columns 8–13 report the computation times. The bold font indicates the optimality.Table 3
Comparison of models in terms of total cost and computation times on Fattahi instances.
InstanceTotal energy consumptionComputation time (second)CP-1CP-2MILP-2MILP-2AMILP-3GACP-1CP-2MILP-2MILP-2AMILP-3GAsfjs01815.2815.2815.2815.2815.2815.254.60.30.00.00.00.2sfjs021362.21362.21362.21362.21362.21362.265.40.30.00.00.00.2sfjs032806.22806.22806.22806.22806.22806.2507.30.30.00.00.00.2sfjs044560.34560.34560.34560.34560.34560.3600.10.30.00.00.00.2sfjs051405.41405.41405.41405.41405.41405.4547.70.30.00.00.00.2sfjs064304.64304.64304.64304.64304.64420.6600.10.30.10.00.00.3sfjs075256.05256.05256.05256.05256.05345.2600.00.30.10.00.00.3sfjs083429.73429.73429.73429.73429.73477.7600.00.30.30.10.00.3sfjs092848.02848.02848.02848.02848.03023.2600.20.40.10.10.10.3sfjs108877.08877.08877.08877.08877.08877600.00.40.10.00.00.4mfjs019380.79380.79380.79380.79380.79981.2600.0600.12.90.81.60.5mfjs028642.08642.08642.08642.08642.09082600.0600.02.81.11.90.5mfjs0310799.410762.810757.810757.810757.811700600.0600.035.34.710.80.6mfjs0413075.913038.613038.613038.613038.613696600.0600.1117.527.382.30.6mfjs0512744.412600.112600.112600.112600.113579.1600.0600.193.323.7426.80.6mfjs0615169.714960.114960.114960.114960.116257.5600.0600.149.616.752.00.7mfjs0720842.120542.121098.320990.321179.621884.9600.0600.0607.5600.2600.31.0mfjs0824295.023763.824289.623999.023993.425812.3600.0600.1601.8600.3600.31.0mfjs0930999.429788.131386.730882.530846.432237.1600.1600.0601.1600.5600.11.2mfjs1034946.834410.736794.535168.637136.637293.6600.0600.1600.4601.6600.81.5Average10828.010677.710930.710804.210910.011380.8538.8300.2135.7123.9148.90.5Table 4
Comparison of models in terms of total cost and computation times on Behnke instances.
InstanceTotal energy consumptionComputation time (second)CP-1CP-2MILP-2MILP-2AMILP-3GACP-1CP-2MILP-2MILP-2AMILP-3GABehnke11839.21795.81795.81795.81795.81889.3600.0600.1600.1104.6600.11.1Behnke21787.81768.01763.91763.91763.91884.6600.0600.1318.3167.3180.81.1Behnke31752.41749.91749.91749.91749.91902.6600.0600.2332.655.3309.21.1Behnke42012.41964.21961.41945.91950.42082.9600.0600.1600.2379.7600.11.1Behnke51928.21865.71867.31865.71872.62101.1600.0600.1600.3124.4600.11.0Behnke63565.13354.13385.83361.33381.63637.7600.1600.2600.4600.2600.12.2Behnke73875.43483.13475.33454.63455.23734.9600.0600.2602.7600.3600.32.2Behnke83701.73445.23509.63474.43521.33774.9600.0600.3604.4600.4600.31.9Behnke93526.53326.63324.43294.43340.03579.2600.0600.3600.4600.3600.22.1Behnke104150.03703.43742.83705.73784.63916.8600.0600.3603.3600.4600.32.1Average2813.92645.62657.62641.22661.52850.4600.0600.2546.3383.3529.11.6Table3 reports the results based on Fattahi’s instances. For small-sized instances (SFJS01-10), all approaches found the optimal solutions, except GA. In computation times, all approaches, except CP-1, terminated in one second. For medium-sized instances (MFJS01-10), CP-2 yielded the best results on average. In computation times, GA significantly outperforms all other approaches seconds. However, MILP-2, MILP-2A, and MILP-3 terminated at a similar time.Table4 reports the results based on Behnke’s instances. The proposed MILP-2A performed the best in average. GA is significantly faster than the MILP and CP approaches. However, the total energy consumption is increased up to 8.1% on average.In order to determine if the means of two sets of data are significantly different from each other, we conducted thet-test: Paired Two-Sample for Means at an alpha level of 0.05. Table 5 indicates that, for medium-sized Fattahi’s instances, there is a statistically significant difference between CP-2 vs. CP-1 and GA, while there is no statistically significant difference between CP-2 vs. MILP-2, MILP-2A, and MILP-3. For Behnke’s instances, there is a statistically significant difference between MILP-2A vs. CP-1, MILP-2, MILP-2A, MILP-3, and GA methods, while there is no statistically significant difference between MILP-2A and CP-2.Table 5
Comparison of models in terms oft-test: paired two-sample for means.
CP-2 vs.Medium-sized Fattahi instances (MFJS01-10)MILP-2A vs.Behnke instancesCP-1MILP-2MILP-2AMILP-3GACP-1CP-2MILP-2MILP-3GAt-value t (9)−2.511−1.918−2.038−1.684−5.185t-value t (9)−3.387−0.780−3.426−2.337−8.547p-value0.03330.08740.07200.12650.0006p-value0.00800.45520.00760.04420.0000The previous tables compared the performance of models with a fixed computation time. It is necessary to check how the performance changes according to different computation times. Table6 summarizes the total energy consumption in terms of computational run time for the Kacem’s instances. Both CP and MILP models proved the optimality of Kacem1 instance within 60 s. CP managed to prove the optimality of Kacem2 instance within 60 s, while MILP spent 150 s. In the Kacem3 instance, the CP-2 found an optimal solution within 60 s, while MILP-2A could not find an optimal solution within 600 s. In addition, the CP-2 found a much better solution, in just 10 seconds, than the one MILP-2A found in 600 seconds. This experiment demonstrates that CP is quick to generate efficient (or optimal) solutions.Table 6
Comparison of models in terms of total energy consumption according to different CPU times.
InstanceModelCPU (sec)10306090120150180300600Kacem1CP-2407.5401.4393.4——————MILP-2A443.0408.6393.4——————GA422.6Kacem2CP-2205.8202.2200.8——————MILP-2A238.6220.8215.5210.0201.5200.8———GA227.5Kacem3CP-2520.2435.8435.8435.8435.8435.8435.8435.8435.8MILP-2A1909.21908.11908.11908.11908.11908.11908.11908.11908.1GA501.8The energy saving does not appeal to highly capitalized manufacturing industries, such as automobiles and semiconductors, because the total energy cost is not even comparable to the revenue the manufacturers yield, so their sole goal is to maximize productivity. However, if we can maintain the same productivity, while significantly reducing energy consumption, the energy-aware production scheduling will be embraced by the industries. This type of mathematical approach is known as epsilon-constraint method, where one of the objectives is taken as a single objective function and the others are included into a model as constraint [51].Tables7 and 8 attempt to meet this demand by comparing the traditional scheduling and energy-aware scheduling. The traditional scheduling minimizes the makespan (cycle time reduction), whereas the energy-aware scheduling minimizes the total energy consumption as it maintains the same makespan. Column 1 identifies the name of the instance. Column 2 reports the total energy consumption when the model solves each test instance with the makespan minimization. Columns 3-4 report the total energy consumption when the model runs with the energy consumption minimization with the same makespan. This experimentation identifies potential energy-saving without compromising productivity. For Fattahi’s instances, Table 7 shows 1.57% and 1.69% saving without and with shutdown strategy, respectively. The mild saving can be explained by the test instance itself.Table 7
Potential energy saving based on Fattahi instances.
InstanceTotal energy consumptionEnergy savingTraditionEnergy-aware schedulingEnergy-aware schedulingw/o shutdownw/ shutdownw/o shutdown (%)w/ shutdown (%)sfjs01815.2815.2815.20.000.00sfjs021362.21362.21362.20.000.00sfjs032806.22806.22806.20.000.00sfjs044560.34560.34560.30.000.00sfjs051405.41405.41405.40.000.00sfjs064630.64360.64360.65.835.83sfjs075530.25304.25304.24.094.09sfjs083599.23599.23599.20.000.00sfjs093121.02951.02951.05.455.45sfjs109217.88893.08877.03.523.70mfjs019498.69468.69468.60.320.32mfjs029036.28918.28918.21.311.31mfjs0311410.011356.011278.00.471.16mfjs0413233.913163.913075.90.531.19mfjs0513333.613293.613293.60.300.30mfjs0616443.116086.716086.72.172.17mfjs0722072.921973.121775.10.451.35mfjs0824884.424509.624503.81.511.53mfjs0932144.431262.231262.22.742.74mfjs1035857.734874.934874.92.742.74Average1.571.69Table 8
Potential energy saving based on Behnke instances.
InstanceTotal energy consumptionEnergy savingTraditionEnergy-aware schedulingInstancew/o shutdownw/ shutdownw/o shutdown (%)w/ shutdown (%)Behnke12156.21809.91809.916.0616.06Behnke21955.21789.31789.38.498.49Behnke32106.11840.91796.312.5914.71Behnke42237.81945.91945.913.0413.04Behnke52125.11953.21953.28.098.09Behnke64356.73358.33358.322.9222.92Behnke74210.83543.73543.715.8415.84Behnke84200.73502.83502.816.6116.61Behnke94022.53341.83297.916.9218.01Behnke104558.53740.13714.517.9518.51Average14.8515.23Table8 reports the results of Behnke’s instances. This experimentation identified the potential energy-saving without compromising productivity by 14.85% (w/o shutdown) and 15.23% (w/shutdown). The increased savings compared with the ones with Fattahi’s instance are due to the size of this Behnke’s instance, allowing the solver the flexibility to find better solutions. In order to determine if the means of two sets of data are significantly different from each other, we conducted the t-test: Paired Two-Sample for Means at an alpha level of 0.05. The test indicates that there is a statistically significant difference between traditional and energy-aware methods with t (19) = 3.5 and p<0.01 in Fattahi’s instance and t (9) = 5.53 and p<0.001 in Behnke’s instance.Table9 records the amount of energy saving by applying the proposed energy-aware method according to different multipliers on Eo,k. This experimentation identified the potential energy-saving without compromising productivity by 6–8%. The improvement was slightly decreased as the multiplier was increased.Table 9
Energy saving according to different energy consumption.
InstanceEo,k (%)2Eo,k (%)3Eo,k (%)4Eo,k (%)Kacem110.59.59.28.9Kacem22.81.71.31.1Kacem311.49.78.98.6Average8.27.06.56.2


## 5. Conclusion

We have investigated the energy-efficient FJSP with a shutdown (on/off) strategy to save idle energy consumption. The shutdown can be enforced when a continuous idle period of a machine is expected to be long enough to compensate for the shutdown penalty. An alternative MILP model is proposed. Then, a novel constraint programming is proposed. Finally, practical operational scenarios are examined.The computational study demonstrated that (1) the proposed models significantly outperform the best benchmark model (MILP-2) and (2) we can maintain the maximum productivity while significantly reducing the energy-consumption by 14.85% (w/o shutdown) and 15.23% (w/shutdown) on average, thus promoting energy-aware production scheduling to highly capitalized manufacturing industries. We offer benchmarking instances, CPLEX MIP, CP, and GA source codes, which have been used in this research, in order to promote related research, thus expediting the adoption of energy-efficient scheduling in manufacturing facilities.In future research, we will extend the proposed models to consider time-of-use (TOU) electricity and peak power load since the energy cost can be further saved. Utility companies across the U.S. are offering TOU-based electricity demand response programs. The key is to shift productions to off-peak periods.



---

*Source: 8035806-2021-06-30.xml*