An MILP Model for Energy-Conscious Flexible Job Shop Problem with Transportation and Sequence-Dependent Setup Times

Abstract

As environmental awareness grows, energy-aware scheduling is attracting increasing attention. Compared with traditional flexible job shop scheduling problem (FJSP), FJSP, with considering sequence-dependent setup times and transportation times (FJSP-SDST-T), is closer to real production. In existing research, little research has focused on FJSP-SDST-T with the minimization energy consumption. In order to make up the gap, a mixed integer linear programming (MILP) model has been formulated to solve FJSP-SDST-T with minimizing energy. Firstly, the total energy consumption of the workshop included the processing energy consumption, setup energy consumption, idle energy consumption, transportation energy consumption and common energy consumption, which were analyzed and formulated by introducing related decision variables. Then, the MILP model was detailedly formulated from the formulation of the energy consumption composition, the objective function, the decision variables and the constraint sets and the linearization. Finally, experiments were carried out on extended benchmark cases and the results showed the effectiveness of the MILP model.

1. Introduction

The flexible job shop scheduling problem (FJSP) is very important in the modern manufacturing system. For FJSP, an operation can be performed on different machines, and two sub-problems, namely the machine selection of all operations and the operations sequencing of all machines, should be addressed. Moreover, FJSP has already proved to be a type of NP-hard problem [1,2,3,4,5].

In previous studies, to solve FJSP, most of the research aimed at minimizing the makespan [1]. However, in recent years, with the dual pressure of environmental issues and energy costs, more and more attention has been paid to energy-conscious scheduling and the fact it is effective in reducing energy consumption without increasing costs [2,6,7,8,9,10,11,12,13,14]. In actual production, some machine tools remain in an idle state for a long time, and they can be turned off and then back on to save energy [15]. This energy-saving strategy is called the Turn Off/On strategy [16], and it has been widely implemented in different scheduling problems [2,6,7,8,15,17].

In the classical FJSP, setup and transportation times are overlooked, which does not conform to the actual production situation. In real cases, a job cannot be processed on the next machine immediately after its completion on the previous machine; instead, jobs should be transported between the machines by transportation systems [18]. Moreover, when an operation is completed on a machine, the machine has to be equipped with appropriate tools for the next operation, which incurs sequence-dependent setup times [19,20]. The FJSP with sequence-dependent setup and transportation times (FJSP-SDST-T) is more in line with the actual situation and should be studied [21,22].

Our work focuses on minimizing the total energy consumption of FJSP-SDST-T. Moreover, Turn Off/On is implemented to save energy. The aim of our work is to solve FJSP-SDST-T with MILP model. Compared with previous studies, the contributions of our work can be summarized as having two aspects, which are described as follows:

(1) To the best of our knowledge, this paper is the first attempt to study the energy-conscious FJSP-SDST-T with considering the Turn Off/On strategy;

(2) A novel MILP model is firstly formulated for FJSP-SDST-T with minimizing total energy consumption.

The rest of the paper is organized as follows. Section 2 introduces the related works on FJSP-SDST-T. Section 3 formulates the energy-efficient MILP model. Section 4 presents the experimental evaluations. Conclusions and future works are presented in Section 5.

2. Literature Review

With regard to the scheduling problem, it can be solved by two classes of methods, among which the first one is the exact method and the second one is the approximation method. Regarding exact methods, they mainly contain a branch-and-bound algorithm and mixed integer programming (MIP), among others [23]. As to approximation methods, they include heuristic rules and meta-heuristic algorithms.

2.1. Related Research about MILP Models

The MIP model can solve small-sized problems to optimality and can elaborate all the characteristics of a scheduling problem. Moreover, it is very important in designing new dispatching rules. In recent years, MIP solvers, such as Cplex and Gurobi, have been improved significantly, and MIP modeling of scheduling problems has attracted more and more attention. Based on different modeling ideas, Mehrabad and Fattahi [24] and Shen et al. [20] both proposed an MILP model for FJSP-SDST with the objective of minimizing the makespan. Karimi and Ardalan [18] designed two MILP models (a sequence-based model and a position-based model) for FJSP with transportation times (FJSP-T). Aimed at minimizing the total tardiness, Mousakhani [25] developed an adjacent sequence-based MILP model for FJSP-SDST.

With regard to energy consumption, the existing research commonly adopted the position-based modeling idea. Zhang et al. [15] first developed an MILP model for FJSP with the Turn Off/On strategy, and then Meng et al. [7] proposed five much more efficient MILP models. Moreover, Meng et al. [8] designed an MILP model for FJSP with considering worker flexibility and the Turn Off/On strategy, and Meng et al. [2] proposed an MILP model for distributed FJSP with minimizing energy consumption.

When considering different scheduling problems, objectives, constraints and modeling ideas, the decision variables and constraint sets of the MILP model vary greatly. Compared with the existing research, our research focused on FJSP-SDST-T by considering the energy consumption objective and Turn Off/On energy-saving strategy, and it was more complex and novel. The differences in terms of the MILP model described in our paper with the previous works are given in

Table 1. The differences of the MILP model described in our paper with the previous works.

References	Problem	Objective	MILP Modeling Idea
[20]	FJSP-SDST	makespan	sequence-based idea
[24]	FJSP-SDST	makespan	adjacent sequence-based idea
[25]	FJSP-SDST	total tardiness	adjacent sequence-based idea
[18]	FJSP-T	makespan	sequence-based and position-based ideas
[15]	FJSP	energy consumption with Turn Off/On strategy	position-based idea
[7]	FJSP	energy consumption with Turn Off/On strategy	position-based idea
[8]	FJSP with worker flexibility	energy consumption with Turn Off/On strategy	position-based idea
[2]	distributed FJSP	energy consumption with Turn Off/On strategy	position-based idea
This paper	FJSP-SDST-T	energy consumption with Turn Off/On strategy	position-based idea

.

2.2. Related Research about Approximation Methods

Although the MILP model can obtain optimal solutions and is very important, it consumes more time and computer memory when the problem size increases. Therefore, it cannot be applied to solve large-scale problems [26]. The approximation methods, especially meta-heuristic algorithms such as the genetic algorithm (GA) [12,17], tabu search (TS) algorithm [20], grey wolf optimization algorithm [27] and virus optimization algorithm(VOA)[28], have been proven to solve the scheduling problems well, particularly large-sized problems. To optimize the makespan of FJSP-SDST, Shen et al. [20] proposed a tabu search algorithm, and Zhang et al. [5] designed a different genetic algorithm. To minimize the makespan and the total setup costs of FJSP-SDST, Li et al. [29] designed an elitist non-dominated sorting hybrid algorithm.

With regard to energy-efficient FJSP, Zhang et al. [15] designed a Gene Expression Programming (GEP) algorithm to mine dispatching rules and to minimize energy consumption. Meng et al. [8] designed a VNS for FJSP with consideration for worker flexibility and the Turn Off/On strategy. For FJSP with controllable processing times (FJSP-CPT), Gong et al. [30] proposed a hybrid GA to simultaneously minimize the makespan, worker cost and green objective, while Luo et al. [27] designed a multi-objective grey wolf optimization algorithm to simultaneously minimize the makespan and total energy consumption. Wu and Sun [17] designed a NSGA-II to optimize makespan, energy consumption and the number of Turn Off/On strategies simultaneously. With regard to FJSP-T, Dai et al. [21] proposed an enhanced genetic algorithm (EGA) that was based on a combination of the GA, the particle swarm optimization (PSO) and the simulated annealing algorithm (SAA) to minimize the energy consumption and makespan. With regard to distributed flexible job shop scheduling with crane transportations, Du et al. [4] proposed a hybrid algorithm consisting of estimation of distribution algorithm (EDA) and variable neighborhood search (VNS) to minimize makespan and energy consumption simultaneously.

With regard to FJSP-SDST-T, Zhang et al. [5] developed an improved GA to simultaneously minimize the makespan time, total setup time and total transportation time simultaneously. Zhang et al. [31] designed an effective novel heuristic method (NHM) that included three strategies, namely population initialization, greedy iterative decoding and local intensification to simultaneously optimize the energy consumption and makespan of FJSP-SDST-T. Liu et al. [22] designed a hybrid fruit fly algorithm to minimize carbon footprints and makespan of FJSP-SDST-T simultaneously. Li and Lei [32] designed an imperialist competitive algorithm to solve the energy-efficient FJSP-SDST-T while minimizing the makespan, total tardiness and total energy consumption simultaneously.

Reading the relevant literature, one can conclude that more and more researchers are paying more and more attention to energy-efficient scheduling both based on MILP formulations and meta-heuristic algorithms. Due to the complexity of the energy-efficient FJSP-SDST-T, this paper study aims to formulate a feasible MILP model to excavate the characteristics of the energy-efficient FJSP-SDST-T. Moreover, FJSP-SDST-T is much closer to the actual production workshop; therefore, this research is significant both in theory and application.

3. MILP Modeling for FJSP-SDST-T

3.1. Notations

The notations used in the MILP model are presented in

Table 2. Notations in the MILP model.

Notations	Definition
$i,i’$	indices for jobs that are to be machined
$n$	job number
$I$	job set and $I=\left\{1,2,\cdot \cdot \cdot ,n\right\}$
$j,j’$	operations indices
$n_i$	number of operations of job i
$J_i$	operation set of job i and $J_i=\left\{1,2,\cdot \cdot \cdot ,n_i\right\}$
$J_i^{’}$	operation set of first $n_i-1$ operations of job i and $J_i^{’}=\left\{1,2,\cdot \cdot \cdot ,n_i-1\right\}$
$k,k’$	machine indices
Oi,j	the j-th operation of job i
$m$	number of machines
$m_{i,j}$	number of machines that are able to process operation $O_{i,j}$
$K$	machine set and $K=\left\{1,2,\cdot \cdot \cdot ,m\right\}$
$K_{i,j}$	machine set that is able to process operation $O_{i,j}$
$s_{i,i’,k}$	setup time when job $i’$ is immediately processed after job i on machine k. Moreover, $s_{i,i’,k}=0$ when $i=i’$
t	index for the position of a machine
$p_k$	maximum number of positions for machine k and $p_k={\displaystyle {\sum }_{i\in I}{\displaystyle {\sum }_{j\in J_i}{x}_{i,j,k}}}$
$L_k$	position set of machine k and $L_k=\left\{1,2,\cdot \cdot \cdot ,p_k\right\}$
$L_k^{’}$	set of first $p_k-1$ positions of machine k and $L_k^{’}=\left\{1,2,\cdot \cdot \cdot ,p_k-1\right\}$
Tk	required time of Turn Of/On strategy
TBk	break-even time of machine k for implementing Turn Off/On strategy
$E_{\mathit{turn}}^k$	energy consumption for Turn Off/On strategy
Nk	maximum allowable times of Turn Off/On strategy of machine k
$x_{i,j,k}$	a binary constant that is equal to 1 if machine k can process operation $O_{i,j}$;0 otherwise
Ki,j	machine set that is able to process operation $O_{i,j}$
$p{t}_{i,j,k}$	time of machine k for processing operation $O_{i,j}$
$P_{i,j,k}$	power of machine k for processing operation $O_{i,j}$
$P{E}_{i,j,k}$	energy consumption of machine k for processing operation $O_{i,j}$
$PE$	total processing energy consumption
$IE$	total idle energy consumption
$I{E}_{k,t}$	energy consumption of machine k when it is in idle state between positions t and t+1
$P_{idle}^k$	power consumed by machine k when it is in idle state
$P_{set}^k$	power consumed by machine k when it is in setup state
M	a very large positive value, and it is set to 10,000 in this paper
$CE$	common energy that is consumed by auxiliary equipment in the workshop
$P_t$	power consumption of the transporter
$t_{k,t}^{idle}$	idle time between positions t and t+1 of machine k
$se{t}_{k,t}^{}$	setup time between positions t and t+1 of machine k
$S{E}_{k,t}^{}$	setup energy consumption between positions t and t+1 of machine k
$T{E}_{i,j}$	energy consumption for transporting job i from the machine k that $O_{i,j}$ is processed on to machine $k’$ that $O_{i,j+1}$ is assigned to
$T_{i,j}^r$	transportation time for transporting job i from the machine k that $O_{i,j}$ is processed on to machine $k’$ that $O_{i,j+1}$ is assigned to
$T{t}_{k,k^{’}}$	transportation time between machine k and machine $k’$
P0	common power that is consumed by auxiliary equipment

.

The decision variables in the MILP model are given in

Table 3. Decision variables in the MILP model.

Decision Variables	Definition
$Z_{k,t}$	a binary decision variable that is equal to 1 if Turn Off/On is applied between position t and t+1 if machine k; 0 otherwise
$X_{i,j,k}$	a binary decision variable that is equal to 1 if operation $O_{i,j}$ is processed on machine k; 0 otherwise
$Y_{i,j,k,t}$	a binary decision variable that is equal to 1 if operation $O_{i,j}$ is processed on position t of machine k; 0 otherwise
$E_{k,t}$	a continuous decision variable that represents for energy consumed by machine k between position t and t+1
$E{O}_{i,j}$	a continuous decision variable that stands for transportation energy consumption $T{E}_{i,j}$
$S_{k,t}$	a continuous decision variable that denotes the starting time of position t of machine k
$F_{k,t}$	a continuous decision variable that indicates the completion time of position t of machine k
$B_{i,j}$	a continuous decision variable that represents for the starting time of operation $O_{i,j}$

.

3.2. Problem Description

The FJSP-SDST-T can be stated as follows: there are a set $I=\left\{1,2,\cdot \cdot \cdot ,n\right\}$ of independent jobs and a set $K=\left\{1,2,\cdot \cdot \cdot ,m\right\}$ of machines. Each job i involved $n_i$ operations $\{O_{i,1},O_{i,2},\mathrm{\dots },O_{i,n_i}\}$ that had to follow the processing route. For each operation $O_{i,j}$, it could be machined by a set $K_{i,j}$ of machines. Motivated by practical applications, such as changing tools, replacing fixtures and positioning that have to be performed before the processing of another job, sequence and machine dependent setup times were considered. A setup time $s_{i,i’,k}$ was needed when operations of jobs i and $i’$ are processed successively on machine k. When an operation for a job is finished, the job needs to be moved to another machine by a transporting vehicle. Therefore, transportation times were taken into consideration. Moreover, the Turn Off/On strategy (described in detail in Section 3.3) were taken into consideration to reduce idle energy consumption. Moreover, we took the following assumptions into consideration:

• The number of the transporters is considered to be infinite;
• No more than one operation can be simultaneously performed on a machine;
• The operations of the same job must follow the given processing route;
• All the jobs, machines and transporters are available at time 0;
• For every operation, preemption is not allowed;
• The power of the transporter is the same when transporting all jobs;
• A transporter can transport at most one job at a time and cannot be interrupted during transportation;
• The magnitude of the transportation times depends on the distance among the machines.

In this paper, the objective was to minimize energy consumption of FJSP-SDST-T. Specifically, three sub-problems, namely assigning each operation to an appropriate machine (machine selection subproblem), sequencing the operations on the machines (operations sequencing subproblem) and deciding whether to apply the Turn Off/On strategy or not when the machine is in an idle state (Turn Off/On strategy decision subproblem) had to be solved to ensure that the energy consumption was minimized.

3.3. Total Energy Consumption of the Workshop

In this paper, we divided the energy consumed by the workshop into five parts, namely processing energy consumption (PE), setup energy consumption (SE), idle energy consumption (IE), transportation energy consumption (TE) and common energy consumption (CE), among which PE, SE, and IE are the energy consumed by the machines when they are in processing, setup and idle modes respectively. TE is the energy consumed by the transportation systems and CE represents for the energy consumed by auxiliary equipment in the workshop. The total energy consumption (TotalE) is the sum of PE, SE, IE, TE and CE.

3.3.1. Processing Energy Consumption

Regarding processing energy consumption, it was the energy consumption of machines when they were in the processing state and it was calculated as,

$$PE={\displaystyle \sum _{i\in I}{\displaystyle \sum _{j\in J_i}{\displaystyle \sum _{k\in K_{i,j}}{P}_{i,j,k}}}}p{t}_{i,j,k}{X}_{i,j,k}$$

(1)

3.3.2. Setup Energy Consumption

Setup energy consumption was the energy consumed by the machine tool for adjustments such as changing tool and replacing fixtures and it was computed as,

$$SE={\displaystyle \sum _{k\in K}{\displaystyle \sum _{t\in L_k^{’}}S{E}_{k,t}={\displaystyle \sum _{k\in K}{\displaystyle \sum _{t\in L_k^{’}}{P}_{set}^{k}se{t}_{k,t}}}}}$$

(2)

where, the setup time $se{t}_{k,t}$ was dependent on the jobs that were assigned to the two adjacent positions of a machine, and it could be computed as,

$$se{t}_{k,t}={\displaystyle \sum _{i\in I}{\displaystyle \sum _{i’\in I}{\displaystyle \sum _{j\in J_i}{\displaystyle \sum _{j’\in J_{i’}}{Y}_{i,j,k,t}{Y}_{i’,j’,k,t+1}}}}}{s}_{i,i’,k}$$

(3)

where, the purpose of binary variable $Y_{i,j,k,t}$ was to determine the operation sequence on each machine. Moreover, variable $Y_{i,j,k,t}$ played the role of variable $X_{i,j,k}$ to solve the subproblem of machine selection.

3.3.3. Idle Energy Consumption

Idle energy consumption was the energy consumed by the machines in idle mode. In actual production, a machine often waits for jobs due to their late arrivals. This energy consumption is wasteful and should be reduced as far as possible. IE was calculated as,

$$IE={\displaystyle \sum _{k\in K}{\displaystyle \sum _{t\in L_k^{’}}I{E}_{k,t}}}={\displaystyle \sum _{k\in K}{\displaystyle \sum _{t\in L_k^{’}}{P}_{idle}^k{t}_{k,t}^{idle}}}$$

(4)

where, $t_{k,t}^{idle}$ was the difference in $S_{k,t+1}$, $F_{k,t}$$F_{k,t}$ and $se{t}_{k,t}$, and it was calculated as,

$$t_{k,t}^{idle}=S_{k,t+1}-F_{k,t}-se{t}_{k,t}$$

(5)

when a machine is in the setup state, it must remain activated so as to perform the adjustments. Meanwhile, if a machine remains in an idle state for a long time, it is economically justifiable to turn it off and then turn it on. A power curve that includes the idle, setup, processing and Turn Off/On states is displayed in Figure 1. Here, we defined an important variable $T{B}_k$, for which Turn Off/On is energy-saving.

$$T{B}_k=\max \{T_k,E_{turn}^k/P_{idle}^k\}$$

(6)

For the sake of determining the Turn Off/On strategy decision subproblem, we introduced a binary variable $Z_{k,t}$. If the Turn Off/On strategy was implemented, $Z_{k,t}=1$; otherwise, $Z_{k,t}=0$. IE considering the Turn off/On strategy was processed as follows,

$$IE={\displaystyle \sum _{k\in K}{\displaystyle \sum _{t\in L_k^{’}}((1-Z_{k,t})P_{idle}^k{t}_{k,t}^{idle}+Z_{k,t}{E}_{turn}^k)}}$$

(7)

3.3.4. Transportation Energy Consumption

Regarding the transportation energy consumption, it was the energy consumed by the transporters when transporting the jobs between different machines. Moreover, it was defined as,

$$TE={\displaystyle \sum _{i\in I}{\displaystyle \sum _{j\in J_i^{’}}T{E}_{i,j}}}=P_t{\displaystyle \sum _{i\in I}{\displaystyle \sum _{j\in J_i^{’}}{\displaystyle \sum _{k\in K_{i,j}}{\displaystyle \sum _{k’\in K_{i,j+1}}T{t}_{k,k’}{X}_{i,j,k}{X}_{i,j+1,k’}}}}}$$

(8)

where, $T{E}_{i,j}$ was the product of transportation time $T_{i,j}^r$ and the power of the transporter $Pt$, and it was calculated as below,

$$T{E}_{i,j}=P_t{T}_{i,j}^r=P_t{\displaystyle \sum _{k\in K_{i,j}}{\displaystyle \sum _{k’\in K_{i,j+1}}T{t}_{k,k’}{X}_{i,j,k}{X}_{i,j+1,k’}}}$$

(9)

3.3.5. Common Energy Consumption

In actual production, many types of auxiliary equipment are used to maintain the workshop environment, the energy consumed by which is the common energy consumption. CE was calculated as below,

$$CE=P_0{C}_{\max }$$

(10)

3.3.6. Total Energy Consumption with Considering Turn Off/On Strategy

To summarize, the total energy consumption of the workshop with considering the Turn Off/On strategy was calculated by Equation (11),

$$\begin{array}{c}TotalE=PE+SE+IE+TE+CE=\\ {\displaystyle \sum _{i\in I}{\displaystyle \sum _{j\in J_i}{\displaystyle \sum _{k\in K_{i,j}}{P}_{i,j,k}p{t}_{i,j,k}{X}_{i,j,k}}}}+{\displaystyle \sum _{k\in K}{\displaystyle \sum _{t\in L_k^{’}}{\displaystyle \sum _{i\in I}{\displaystyle \sum _{i’\in I}{\displaystyle \sum _{j\in J_i}{\displaystyle \sum _{j’\in J_{i’}}{Y}_{i,j,k,t}{Y}_{i’,j’,k,t+1}}}}}{s}_{i,i’,k}{P}_{set}^k}}\\ +{\displaystyle \sum _{k\in K}{\displaystyle \sum _{t\in L_k^{’}}((1-Z_{k,t})(S_{k,t+1}-F_{k,t}-{\displaystyle \sum _{i\in I}{\displaystyle \sum _{i’\in I}{\displaystyle \sum _{j\in J_i}{\displaystyle \sum _{j’\in J_{i’}}{Y}_{i,j,k,t}{Y}_{i’,j’,k,t+1}{s}_{i,i’,k}}}}})P_{idle}^k+Z_{k,t}{E}_{turn}^k)}}\\ +P_t{\displaystyle \sum _{i\in I}{\displaystyle \sum _{j\in J_i^{’}}{\displaystyle \sum _{k\in K_{i,j}}{\displaystyle \sum _{k’\in K_{i,j+1}}T{t}_{k,k’}{X}_{i,j,k}{X}_{i,j+1,k’}}}}}+P_0{C}_{\max }\end{array}$$

(11)

3.4. MILP Modeling

3.4.1. Model Linearization and Simplification

As we can see from objective function (11), there were four non-linear terms, namely $Z_{k,t}{S}_{k,t+1}$, $Z_{k,t}{F}_{k,t}$, $Z_{k,t}{Y}_{i,j,k,t}{Y}_{i’,j’,k,t+1}$ and $X_{i,j,k}{X}_{i,j+1,k’}$. Thus, the model was highly non-linear and non-convex. Non-linear models are much more difficult to solve than linear ones. Owing to the existence of many local optical solutions in the feasible solution space of the non-convex models, it is NP-hard to solve their optimal solutions. Therefore, we linearized the nonlinear model by introducing two intermediate variables, namely $E{O}_{i,j}$ and $E_{k,t}$. Intermediate variable $E{O}_{i,j}$ was used to represent $T{E}_{i,j}$. Intermediate variable $E_{k,t}$ represented the energy between position t and t+1 of machine k, and it was the sum of $S{E}_{k,t}$ and $I{E}_{k,t}$. The related constraint was set to restrict $E{O}_{i,j}$ and $E_{k,t}$ were formulated as shown in Section 3.4.4.

As can be seen from Equations (12) and (13), the binary variable $X_{i,j,k}$ was the summary of variable $Y_{i,j,k,t}$.Therefore, variable $X_{i,j,k}$ can be removed. Moreover, variable $F_{k,t}$ was the aggregation of variables $S_{k,t}$ and $p{t}_{i,j,k}{Y}_{i,j,k,t}$, thus, it was redundant and could also be deleted.

$${\displaystyle \sum _{t\in L_k}{Y}_{i,j,k,t}=X_{i,j,k}},\forall i\in I,j\in J_i,k\in K_{i,j}$$

(12)

$$F_{k,t}=S_{k,t}+{\displaystyle \sum _{i\in I}{\displaystyle \sum _{j\in J_i}p{t}_{i,j,k}{Y}_{i,j,k,t}}},\forall k\in K,t\in L_k$$

(13)

3.4.2. Decision Variable

In total, the MILP model included seven decision variables, among which two were binary variables namely $Y_{i,j,k,t}$ and $Z_{k,t}$, and five were continuous variables, namely $S_{k,t}$,$B_{i,j}$,$C_{\max }$,$E{O}_{i,j}$ and $E_{k,t}$.

3.4.3. Objective Function

$$TotalE={\displaystyle \sum _{i\in I}{\displaystyle \sum _{j\in J_i}{\displaystyle \sum _{k\in K_{i,j}}{\displaystyle \sum _{t\in L_k}{P}_{i,j,k}}}p{t}_{i,j,k}{Y}_{i,j,k,t}}}+{\displaystyle \sum _{k\in K}{\displaystyle \sum _{t\in L_k^{’}}{E}_{k,t}}}+{\displaystyle \sum _{i\in I}{\displaystyle \sum _{j\in J_i^{’}}E{O}_{i,j}+P_0{C}_{\max }}}$$

(14)

In this function, the first term to the last term represented for the total processing energy consumption, the total idle energy consumption, the total transportation energy consumption and the common energy consumption, respectively.

3.4.4. Constraint Sets

$${\displaystyle \sum _{k\in K_{i,j}}{\displaystyle \sum _{t\in L_k}{Y}_{i,j,k,t}=1}},\forall i\in I,j\in J_i$$

(15)

This constraint set forces that $O_{i,j}$ was performed once and had to be assigned to exactly one machine position.

$${\displaystyle \sum _{i\in I}{\displaystyle \sum _{j\in J_i}{Y}_{i,j,k,t}\le 1}},\forall k\in K,t\in L_k$$

(16)

Constraint set (16) stated that each position of each machine could execute no more than one operation at the same time.

$${\displaystyle \sum _{i\in I}{\displaystyle \sum _{j\in J_i}{Y}_{i,j,k,t}}}\ge {\displaystyle \sum _{i\in I}{\displaystyle \sum _{j\in J_i}{Y}_{i,j,k,t+1}}},\forall k\in K,t\in L_k^{’}$$

(17)

Constraint set (17) showed that the back position could not be assigned to an operation if any of the front positions was free.

$$B_{i,j}+{\displaystyle \sum _{k\in K_{i,j}}{\displaystyle \sum _{t\in L_k}(p{t}_{i,j,k}{Y}_{i,j,k,t})}}+{\displaystyle \sum _{k\in K_{i,j}}{\displaystyle \sum _{t\in L_k}T{t}_{k,k’}}{Y}_{i,j,k,t}}\le B_{i,j+1}+M(1-{\displaystyle \sum _{t\in L_{k’}}{Y}_{i,j+1,k’,t}}),\forall i\in I,j\in J_i^{’},k’\in K_{i,j+1}$$

(18)

Constraints (18) enforced that each operation could only be started when its preceding operation had finished and been transported to the current machine.

$$S_{k,t}\le B_{i,j}+M(1-Y_{i,j,k,t}),\forall i\in I,j\in J_i,k\in K_{i,j},t\in L_k$$

(19)

$$S_{k,t}+M(1-Y_{i,j,k,t})\ge B_{i,j},\forall i\in I,j\in J_i,k\in K_{i,j},t\in L_k$$

(20)

Constraint sets (19) and (20) altogether forced that variable $B_{i,j}$ was equal to variable $S_{k,t}$ when variable $Y_{i,j,k,t}$ was equal to 1. Specifically, if $Y_{i,j,k,t}=0$, these two constraint sets were relaxed; otherwise, they forced that variable $B_{i,j}$ was equal to variable $S_{k,t}$.

$$T{B}_k{Z}_{k,t}+{\displaystyle \sum _{ii\in I}{\displaystyle \sum _{jj\in J_{ii}}(Y_{i’,j’,k,t+1}{s}_{i,i’,k})}}\le S_{k,t+1}-S_{k,t}-{\displaystyle \sum _{i\in I}{\displaystyle \sum _{j\in J_i}(p{t}_{i,j,k}{Y}_{i,j,k,t})}}+M(1-Y_{i,j,k,t}),\forall i,i’\in I,j\in J_i,j’\in J_{i’},k\in K_{i,j}\cap K_{i’,j’},t\in L_k^{’}$$

(21)

$$S_{k,t}+{\displaystyle \sum _{i\in I}{\displaystyle \sum _{j\in J_i}(p{t}_{i,j,k}{Y}_{i,j,k,t})}}\le S_{k,t+1},\forall k\in K,t\in L_k^{’}$$

(22)

$$E_{turn}^k{Z}_{k,t}+{\displaystyle \sum _{i’\in I}{\displaystyle \sum _{j’\in J_{i’}}(Y_{i’,j’,k,t+1}{s}_{i,i’,k}}}{P}_{set}^k)\le E_{k,t}+M(1-Y_{i,j,k,t}),\forall i,i’\in I,j\in J_i,j’\in J_{i’},k\in K_{i,j}\cap K_{i’,j’},t\in L_k^{’}$$

(23)

$$\begin{array}{c}(S_{k,t+1}-S_{k,t}-{\displaystyle \sum _{i\in I}{\displaystyle \sum _{j\in J_i}(p{t}_{i,j,k}{Y}_{i,j,k,t})-{\displaystyle \sum _{i’\in I}{\displaystyle \sum _{j’\in J_{i’}}(Y_{i’,j’,k,t+1}{s}_{i,i’,k})}}}})P_{idle}^k+{\displaystyle \sum _{i’\in I}{\displaystyle \sum _{j’\in J_{i’}}(Y_{i’,j’,k,t+1}{s}_{i,i’,k})}}{P}_{set}^k\le E_{k,t}+M{Z}_{k,t}+M(1-Y_{i,j,k,t})\\ \forall i\in I,j\in J_i,k\in K_{i,j},t\in L_k^{’}\end{array}$$

(24)

Constraint sets (21), (23) and (24) concurrently demonstrated the Turn Off/On strategy. Constraint set (21) restricted that, for two adjacent operations that have been assigned to machine k, the succeeding operation could start only if the preceding operation had been completely finished and the setup operations have been completed. Specifically, if $Z_{k,t}=1$, constraint set (21) ensured that the idle time between positions t and t+1 of machine k was no less than the breakeven time. If a position in a machine was not assigned to any operation, constraint set (22) guaranteed its starting time to be no less than that of its preceding position; otherwise, constraint set (22) was valid inequality and constraint set (21) held. Constraint sets (23)–(24) worked together to ensure the energy consumption between position t and t+1 of machine k. More specifically, if the waiting time was longer than the breakeven time, the machine was turned off and back on ($Z_{k,t}=1$); constraint set (23) showed that the energy consumption $E_{k,t}$ was equal to the sum of $E_{turn}^k$ and the setup energy consumption between positions t and t+1 of machine k; otherwise, machine k remained idle and constraint set (24) showed that $E_{k,t}$ was equal to the sum of the real idle energy consumption and setup energy consumption.

$${\displaystyle \sum _{t\in L_k}{Z}_{k,t}\le N_k},\forall k\in K$$

(25)

The Turn Off/On method may have significantly reduced the energy consumption. However, frequently using the Turn Off/On method could shorten the service life of a machine tool, and constraint set (25) aimed to limit its maximum allowable times.

Transportation energy consumption constraint set:

$${\displaystyle \sum _{k\in K_{i,j}}{\displaystyle \sum _{t\in L_k}{Y}_{i,j,k,t}T{t}_{k,k’}}}{P}_t\le E{O}_{i,j}+M(1-{\displaystyle \sum _{t\in L_{k’}}{Y}_{i,j+1,k’,t}}),\forall i\in I,j\in J_i^{’},k’\in K_{i,j+1}$$

(26)

This constraint set showed that the decision variable $E{O}_{i,j}$ was dependent on the machines that $O_{i,j}$ and $O_{i,j+1}$ were assigned to.

$$C_{\max }\ge B_{i,S_i}+{\displaystyle \sum _{k\in K_{i,S_i}}{\displaystyle \sum _{t\in L_k}(p{t}_{i,S_i,k}{Y}_{i,S_i,k,t})}},\forall i\in I,j\in J_i$$

(27)

Constraint set (27) defined the makespan.

$$B_{i,j},S_{k,t}\ge 0,\forall i\in I,j\in J_i,k\in K,t\in L_k$$

(28)

$$0\le E_{k,t},\forall k\in K,t\in L_k^{’}$$

(29)

$$0\le E{O}_{i,j},\forall i\in I,j\in J_i^{’}$$

(30)

$$Y_{i,j,k,t},Z_{k,t}\in \{0,1\},\forall i\in I,j\in J_i,k\in K,t\in L_k$$

(31)

Constraint sets (28)–(30) enforced that the continuous decision variables were positive, and constraint set (31) defined the binary decision variables.

3.5. An Example Illustration

To intuitively present the MILP model, an example that included three jobs and six machines is shown in Figure 1. The processing data of the example can be seen in

Table 4. Processing data of the example.

Jobs	Ops	Machines
		M1	M2	M3	M4	M5	M6
Job1	$O_{1,1}$	50, 7.2	-	40, 7.0	-	-	-
	$O_{1,2}$	-	10, 4.2	50, 5.0	-	30, 7.8	-
	$O_{1,3}$	-	-	40, 6.0	-	-	20, 4.4
	$O_{1,4}$	10, 7.6	60, 4.2	-	-	-	50, 7.8
	$O_{1,5}$	-	-	10, 7.6	-	-	-
	$O_{1,6}$	-	-	60, 7.8	30, 4.6	-	60, 6.0
Job2	$O_{2,1}$	-	60, 6.8	-	-	-	-
	$O_{2,2}$	-	-	10, 4.6	-	-	-
	$O_{2,3}$	20, 7.8	-	-	-	-	-
	$O_{2,4}$	-	60, 4.2	-	60, 5.4	-	-
	$O_{2,5}$	10, 4.6	60, 5.8	-	-	-	50, 7.2
Job3	$O_{3,1}$	-	60, 7.0	-	-	-	-
	$O_{3,2}$	-	-	40, 5.0	-	-	20, 5.6
	$O_{3,3}$	10, 7.2	60, 4.8	-	-	-	50, 4.4
	$O_{3,4}$	-	60, 6.0	40, 5.4	-	-	60, 4.6
	$O_{3,5}$	10, 5.6	-	-	-	50, 7.4	-
$P_{idle}^{}$		1	2	3	1	2	3
$P_{set}^{}$		1.2	2.4	3.6	1.2	2.4	3.6
$TB$		10	15	20	10	15	20
$E_{turn}$		10	30	60	10	30	60

Note:- The machine cannot process the corresponding operation.

and

Table 5. Transportation times of the example.

Time	M1	M2	M3	M4	M5	M6
M1	0	10	20	22	14	10
M2	10	0	10	14	10	14
M3	20	10	0	10	14	22
M4	22	14	10	0	10	20
M5	14	10	14	10	0	10
M6	10	14	22	20	10	0

. In each cell of the first 16 rows of Table 4, there are two numbers, of which the first one denotes the processing time and the second one represents the processing power. The last 4 rows of the table give the idle power, setup power, break-even time and Turn Off/On energy of each machine.

As can be seen in Figure 2, operation $O_{1,1}$ was the first operation on Machine 1 and its starting time was 47. Then, $Y_{1,1,1,1}$, $B_{1,1}$, $S_{1,1}$ were equal to 1,47 and 47, respectively. On Machine 1, the first Turn Off/On strategy was performed after operation $O_{1,1}$. Then, $Z_{1,1}$ was equal to 1. Moreover, the idle time between the first and second operations was 169, which was much larger than the Turn Off/On $T{B}_1$ of 10. As can be seen in Table 1 that $E_{turn}^1$ and $P_{idle}^1$ of Machine 1 were equal to 10 and 1, respectively. Therefore, 159 energy was saved by performing the Turn Off/On strategy. Operations $O_{3,5}$, $O_{2,3}$ and $O_{2,5}$ were machined in the second, the third and the fourth positions of Machine 1, and decision variables $Y_{3,5,1,1}$, $Y_{2,3,1,2}$ and $Y_{2,5,1,3}$ were equal to 1. The second Turn Off/On strategy of Machine 1 was performed between operations $O_{2,3}$ and $O_{2,5}$, and $Z_{1,3}$ was equal to 1. The starting time of operation $O_{2,5}$ was 411, and $B_{2,5}$ and $S_{1,4}$ were equal to 411. With regard to operations $O_{3,1}$ and $O_{3,2}$, the ending time of operation $O_{3,1}$ on Machine 2 was 60, and the transportation time between Machines 2 and 3 was 10. Therefore, the starting time 70 of operation $O_{3,2}$ was no less than the sum of 60 and 10.

With the same analysis method above, all the other operations and their related decision variables could be analyzed in a similar manner.

4. Computational Results and Discussions

In order to test the MILP, two sets of existing benchmark instances, namely MFJS01-10 [33] and MK01-10 [34], were used. We adapted all the instances by adding energy consumption information and magnifying the processing times of MK01-10. The processing power was randomly generated within [4,8]. The idle powers of machines were randomly generated among {1, 2, 3}. The setup power was obtained by $P_{set}^k=1.2\ast P_{idle}^k$. The energy consumption of the Turn Off/On strategy for each machine was randomly generated among {10, 30, 60}. The breakeven time of Turn Off/On for each machine was randomly generated among {10, 15, 20}. The Turn Off/On time for each machine is randomly generated among {8, 12, 16}. The transporter power and the common power were set as 3 and 10, respectively. The maximum time of Turn Off/On for each machine was set to 3. IBM ILOG CPLEX 12.7.1 was used to solve the MILP model. The time limit was set as 3600 s. The solving method of the CPLEX solver was the branch-and-cut method, which is the combination of cutting plane and branch-and-bound method [23,35,36]. All the methods were run on a computer with a Win 7 system and an Intel(R) Core(TM) 2 Duo CPU with a 3.20 GHz processor and 8 GB of RAM memory.

In

Table 6. Results of MILP model for all instances.

Problem	NBVs	NCVs	NCs	CPU(s)	TotalE	Gap(%)
MFJS01	212	86	1066	5.71	16,234.0 a	0
MFJS02	263	97	1318	24.24	14,787.6 a	0
MFJS03	393	120	1962	417.99	18,386.8 b	0
MFJS04	515	141	2569	3600(8705.37)	22,374.2 b(22,069.6 a)	4.14(0)
MFJS05	503	139	2510	3600	21,414.8 b	3.11
MFJS06	635	158	3168	3600	25,610.2 b	2.56
MFJS07	1009	206	5046	3600	35,722.6 b	20.58
MFJS08	1086	228	5434	3600	41,535.8 b	18.32
MFJS09	1558	276	7793	3600	53,495.6 b	25.27
MFJS10	1862	301	9312	3600	60,622.0 b	24.34
MK01	2732	325	13,692	3600	22,437.2 b	44.26
MK02	9848	581	49,108	3600	33,068.4 b	68.21
MK03	26,372	1180	131,791	3600	-	-
MK04	4696	502	23,556	3600	49,061.2 b	50.58
MK05	8600	556	43,101	3600	132,944.8 b	66.64
MK06	27,980	1261	139,822	3600	178,419.0 b	84.15
MK07	16,433	742	82,079	3600	-	-
MK08	13,507	1066	67,858	3600	-	-
MK09	40,536	1663	202,730	3600	-	-
MK10	53,937	1882	269,606	3600	-	-

Note: ^a Optimum solution. ^b Feasible but not optimum solution. - The MILP model cannot get a feasible solution within 3600 s.

, Gap is the average optimality gap of the solution, and it was calculated as (CS-BS)*100%/CS. Here, CS denoted the best feasible solution that was obtained within the time limit, and BS represented the lower bound obtained within the time limit. Moreover, a solution is optimal when its Gap is equal to 0. Therefore, the Gap value is usually used for judging whether the optimal solution is achieved and to evaluate different solutions. Moreover, NBVs, NCVs and NCs represented the number of binary variables, the number of continuous variables and the number of constraints, respectively. Finally, the CPU time in Table 6 is the time when the optimal solution was proved or the time limit was reached.

It can be seen from Table 6 that the MILP model only could solve very small-sized instances, such as MFJS01-02, to optimality efficiently. For MFSJ01 and MFJS02, the MILP model obtained the optimal solution of 16,234.0 and 14,787.6 within 5.71 s and 24.24 s, respectively. However, the solving time exponentially increased with the increasing size of the instance. For example, the solving time of MFJS03 was 417.99 s, which was nearly 20 times of the solving time of MFJS02. The solving time for obtaining the optimal solution of MFSJ04 was 8705.37 s, which was also approximately 20 times of the solving time of MFJS03. For MFJS04-10, MK01-02 and MK04-06, it could only achieve feasible solutions within 3600 s. For MK03 and 07-10, it could not obtain any feasible solution within 3600 s. The reason behind this is that the NBVs, NCVs and NCs increase sharply when the problem scale becomes larger. The solving efficiency of the MILP model was inversely proportional to the NBVs, NCVs and NCs. With more constraints and decision variables, it became more difficult to achieve branching, find new low bounds and cutting. Moreover, more memory was needed to save more branching nodes.

5. Conclusions and Future Research

MILP modeling of the complex FJSP-SDST-T is an interesting issue. This study considered the energy-conscious FJSP-SDST-T and proposed an MILP model to solve it. To the best of our knowledge, there are no published papers addressing this problem. We firstly analyzed the energy composition of the workshop and then formulated an MILP model from the formulation of the energy consumption composition, the objective function, the decision variables, the constraint sets and the linearization. Experimental results showed that the MILP model was effective and could solve small-sized problems to optimality.

Obtaining the optimal solutions of a scheduling problem is extremely important, and it is the main merit of the MILP model proposed in this paper. However, as we can see from Section 4, the solving time of MILP model exponentially increased with the increasing size of the instance. For these large instances, the MILP model may not have obtained any feasible solution within one hour, which is the main disadvantage of the MILP model.

Our future research will focus on exploring the natural characteristics of the energy-conscious FJSP-SDST-T and designing effective meta-heuristic algorithms (e.g., grey wolf optimization (GWO) algorithm, tabu search (TS) algorithm, migrating birds optimization (MBO) algorithm, virus optimization algorithm (VOA) algorithm and evolution (DE)). We invite related researchers to propose more efficient meta-heuristic algorithms to solve the problem described in this paper. It is also important to design an improved MILP model to solve FJSP-SDST-T. Moreover, it would be an interesting topic to study the multi-objective FJSP-SDST-T with simultaneously minimizing total energy consumption and makespan.