<figure><img src="image_1.png" /></figure>

HAL
open science

# A mixed integer linear programming approach for closed-loop food supply chain with returnable transport items

Yipei Zhang, Feng Chu, Ada Che

► To cite this version:

Yipei Zhang, Feng Chu, Ada Che. A mixed integer linear programming approach for closed-loop food supply chain with returnable transport items. 46th International Conferences on Computers and Industrial Engineering (CIE 2016), Oct 2016, Tianjin, China. hal-01486683

HAL Id: hal-01486683

https://hal.science/hal-01486683

Submitted on 18 Aug 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
AN EFFICIENT MIXED INTEGER LINEAR PROGRAMMING MODEL FOR ENERGY-
CONSCIOUS SINGLE MACHINE SCHEDULING UNDER TIME-OF-USE TARIFFS

Shibohua ZHANG, Xueqi WU, Ada CHE*

School of Management

Northwestern Polytechnical University, Xi'an, China

ache@nwpu.edu.cn

ABSTRACT

This paper investigates an energy-conscious single machine scheduling problem to minimize total electricity cost under the time-of-use (TOU) electricity pricing scheme. In such a scheme, the electricity consumed in different periods of a day requires different prices. Each job to be processed on the machine is characterized by their processing time and electricity consumption per hour. The objective is to arrange the processing of the jobs under TOU electricity tariffs so as to minimize the total electricity cost. An improved mix-integer linear programming model with less number of constraints is formulated for the problem. Computational results demonstrate that our model can solve the problem more effectively.

**Keywords:** single machine scheduling, time-of-use tariffs, mixed-integer linear programming model, total electricity cost

# 1 INTRODUCTION

With the mounting concern over the energy consumption in the manufacturing sector, energy efficiency has become another crucial criterion for production managers to consider when formulating production plans apart from production efficiency. Among a wide range of energy forms, the electricity is regarded as the main form utilized in production activities [1]. However, the process of generating electricity can take a heavy toll on environment protection. For example, generating 1 kwh of electricity means to release two pounds of carbon dioxide[2], which is the main contributor of the global warming process. On the other hand, with the increase in demand and price for fossil fuels and the decrease in their reserves [3], energy-saving has become increasingly urgent. Since the manufacturing sector is the main consumer of electricity in most countries around the world, for example, according to [4], manufacturing occupies about half of the total electricity generated each year in China, containing the usage of electricity in the manufacturing sector is of vital significance.

To achieve the improvement of electricity efficiency in the manufacturing sector, there are mainly three strategies on different levels, which are called structure energy-saving, technical energy saving and management energy-saving[5], respectively. The first two strategies focus on bringing in more energy-efficient production equipment, while the third one tries to achieve the purpose via

This work was in part supported by National Natural Science Foundation of China under grant no. 71471145.

* Corresponding Author.
scientific management, which is quite prevalent in many electricity companies nowadays. Since the demand of electricity may vary greatly in different periods during a day, extra pressure has been put on the electricity suppliers. To tackle the condition, several time-dependent electricity pricing schemes have been proposed and adopted, such as the time-of-use (TOU) pricing scheme.

The TOU pricing scheme works by setting different prices for electricity in different periods during a day. Specifically, each day is divided into different types of periods according to the demand for electricity, such as on-peak periods, mid-peak periods and off-peak periods. In on-peak periods, the electricity prices are set at the highest level because the demands for electricity in these periods are the highest. Accordingly, the electricity prices in the mid-peak and off-peak periods are moderate and the lowest, respectively, because of the moderate and the lowest demand in these periods. Obviously, effective TOU pricing scheme will help shift the workloads from on-peak periods to mid-peak periods and off-peak periods [6]. Hence the demand for electricity during a day may be effectively balanced, thus reducing the burden on the electricity suppliers.

To improve the efficiency of electricity as well as of production under the TOU tariffs, production managers may need the help of scheduling. According to [7], scheduling is to allocate resources to tasks with the goal of optimizing one or several objectives. A special case of scheduling is the single machine scheduling, which is the basis of more complicated machine environments and has been studied widely in the literature. For example, Hariri and Potts [8] developed a branch and bound algorithm to minimize the weighted number of tardy jobs. Boland, Clement and Waterer [9] presented a bucket indexed (BI) MILP model for non-preemptive single machine scheduling problems. Computational results demonstrate that the BI model outperforms significantly the classical time indexed model.

Besides, single machine scheduling problems considering energy consumption have been a hot topic lately. Basically, there are two typical types of energy-saving mechanisms, which are the power-down mechanism (e.g. [3, 10-12]) and the speed-scaling problems (e.g. [13-15]). For single machine scheduling under TOU tariffs, Shrouf, Ordieres-Meré, García-Sánchez and Ortega-Mier [16] formulated a discrete-time integer programming model based on power-down mechanism with the objective of minimizing the total electricity cost. In their work, the processing sequence of jobs is assumed to be pre-determined and a genetic algorithm is proposed to obtain the approximate optimal solutions. Fang, Uhan, Fu and Sutherland [15] studied several speed-scaling versions of the single machine scheduling problem to minimize the total electricity cost. Another work was conducted by Che et al.[17], who proposed a continuous-time mixed-integer linear programming (MILP) model and an efficient greedy insertion heuristic. In this paper, we propose a new MILP model for single machine scheduling problem to minimize the total electricity cost under the TOU tariffs. We will also compare our model with that presented by Che et al.[17].

The remainder of the paper is organized as follows. In section II, we give a clear description of the problem addressed and formulate a new MILP model for it. The computational results and the comparison with a previous model are presented in section III. Finally, we draw a conclusion in section IV.

# 2 PROBLEM DESCRIPTION AND FORMULATION:

## 2.1 Problem description

This paper addresses a single machine scheduling problem with the objective of minimizing total electricity cost under the time-of-use tariffs. Its NP-hardness was proven by Fang, Uhan, Fu and Sutherland [15]. In this problem, a set of *N* jobs to be processed on the machine are specified by their own processing time $t_i$ and electricity consumption rate $p_i$, $1 \le i \le N$. All the jobs are available
at the beginning of the processing course and so is the machine. No preemption is allowed, that is, once a job is processed on the machine, no interruption is permitted until the processing of this job comes to an end. The machine can only process one job each time and breakdowns are not considered.

In terms of the TOU pricing scheme, the electricity prices vary in different periods during a day. Obviously, the same workload assigned to different periods leads to different amount of electricity cost. To better illustrate the problem addressed, without loss of generality, suppose that the whole processing horizon is divided into K periods. We use $s_j$ to denote the start time of period j, $1 \le j \le K+1$, and note that $s_{K+1}$ represents the end time of the last period. The electricity price in period j is denoted by $c_j$, $1 \le j \le K$. For simplicity, we assume that $s_1=0$. To guarantee the feasibility of the problem addressed, the value of $s_{K+1}$ should be larger than the sum of the processing times of all the jobs.

To achieve the goal of minimizing the total electricity cost, the majority of efforts should be focused on the assignment of jobs among different periods of the machine. Hence we need to develop the decision variables to describe whether job i is handled in period j and further know how much processing time of job i is assigned to period j. Since the processing time of job i may be larger than the duration of period j or job i is assigned to be processed across two adjacent periods, we propose another decision variable to describe whether job i is processed across periods to better formulate the problem addressed.

## 2.2 Problem formulation

As is discussed above, the decision variables of the MILP model for the problem addressed are:

$x_{ij}$: The assigned processing time of job i in period j, for $1 \le i \le N, 1 \le j \le K$

$y_{ij}$: Binary variable. If job i is processed in period j, then $y_{ij} = 1$; otherwise, $y_{ij} = 0$, for $1 \le i \le N, 1 \le j \le K$

$z_{ij}$: Binary variable. If job i is processed across period j and period j+1, then $z_{ij} = 1$; otherwise $z_{ij} = 0$, for $1 \le i \le N, 1 \le j \le K-1$

With the notations presented above, the MILP model can be written as follows:

$$ \begin{array}{ll} \min & \displaystyle\sum_{i=1}^{N} \sum_{j=1}^{K} p_i c_j x_{ij} \\ \text{s.t.} & \displaystyle\sum_{j=1}^{K} x_{ij} = t_i, \quad 1 \le i \le N \\ & \sum_{i=1}^{N} x_{ij} \le s_{j+1} - s_j, \quad 1 \le j \le K \\ & x_{ij} \le t_i y_{ij}, \quad 1 \le i \le N, 1 \le j \le K \\ & z_{ij} \ge y_{ij} + y_{i,j+1} - 1, \quad 1 \le i \le N, 1 \le j \le K-1 \\ & \displaystyle\sum_{i=1}^{N} z_{ij} \le 1, \quad 1 \le j \le K-1 \end{array} \quad (1) $$

$$ \sum_{i=1}^{N} x_{ij} \le s_{j+1} - s_j, \quad 1 \le j \le K \quad (2) $$

$$ x_{ij} \le t_i y_{ij}, \quad 1 \le i \le N, 1 \le j \le K \quad (3) $$

$$ z_{ij} \ge y_{ij} + y_{i,j+1} - 1, \quad 1 \le i \le N, 1 \le j \le K-1 \quad (4) $$

$$ \sum_{i=1}^{N} z_{ij} \le 1, \quad 1 \le j \le K-1 \quad (5) $$
$$ \sum_{i=j+2}^{K} y_{il} \leq K(1 - y_{ij} + y_{i,j+1}), \quad 1 \leq j \leq K-2 \qquad (6) $$

$$ x_{ij} \geq (y_{i,j-1} + y_{i,j+1} - 1)(s_{j+1} - s_j), \quad 1 \leq i \leq N, \quad 2 \leq j \leq K-1 \qquad (7) $$

The objective is to minimize the total electricity cost represented by $\sum_{i=1}^{N} \sum_{j=1}^{K} p_i c_j x_{ij}$. Constraint (1) ensures that the sum of the assigned processing time of job i to different periods is equal to its total processing time. Constraint (2) states that the total processing time of all jobs assigned to period j should be no larger than its own duration $s_{j+1} - s_j$. Constraint (3) shows that if $y_{ij} = 0$, then the processing time of job i assigned to period j should be zero as well.

Constraint (4) tells that if job i is processed both in period j and period j+1 (i.e., $y_{ij} = 1$ and $y_{i,j+1} = 1$), then $z_{ij}$ should take the value of 1. Constraint (5) ensures that at most one job can be processed across two adjacent periods. Constraint (6) is the processing continuity constraint ensuring that the processing of a job in different periods are continuous. To be more specific, if job i is processed in period j but not in period j+1 (i.e., $y_{ij} = 1$ and $y_{i,j+1} = 0$), then the end time of processing job i must be in period j, that is, job i cannot be processed in the periods afterwards anymore. We note that constraint (6) can also be equivalently written as:

$$ \sum_{l=1}^{j-1} y_{il} \leq K(1 - y_{i,j+1} + y_{ij}), \quad 2 \leq j \leq K-1. $$

Constraint (7) ensures that if job i is assigned to both period j-1 and period j+1 (i.e., $y_{i,j-1} = 1$ and $y_{i,j+1} = 1$), namely it is processed across at least three periods, then the assigned processing time of job i to period j should be no less than the duration of this period.

We note that Che et al. [17] only defined the first two groups of binary variables (i.e. $x_{ij}$ and $y_{ij}$) to formulate the single machine scheduling problem under TOU tariffs. In this work, the number of constraints is greatly reduced due to the use of the third group of binary variables (i.e. $z_{ij}$). We also note that similar definitions of the three groups of binary variables given above and their corresponding constraints can also be found in Ding et al. [18], who proposed an interesting MILP model for unrelated parallel machine scheduling problem under TOU Tariffs. In fact, they defined five groups of binary variables to formulate their problem. In this work, we need to define three groups of binary variables due to improvements of the formulation.

It is worthwhile to note that we improve the processing continuity constraint given by Che et al. [17] and Ding et al. [18], which is a very key constraint for machine scheduling problems under TOU tariffs. In the work of Che et al. [17], the processing continuity constraints formulated as $O(NK^2)$ inequalities. However, in this work, it is formulated as $O(NK)$ inequalities without introducing any additional binary variables. In Ding et al [18], for a given unrelated parallel machine, the processing continuity constraint is also formulated as $O(NK)$ inequalities by introducing additional NK binary variables. From the above analysis, our formulation of the processing continuity constraint is more compact than Che et al.'s and Ding et al.'s, which speeds up the resolution of the model. It is worthwhile to point out that the formulation for processing continuity constraint developed in this work can also be applied to other machine scheduling problems under TOU tariffs.

## 3 COMPUTATIONAL RESULTS
In this section, we compare the performance of our MILP model with a previous one developed by Che et al.[17] through randomly generated instances. The model formulations are coded and implemented in C++ and solved by the MILP solver of CPLEX (Version 12.6). All the experiments are performed on a Lenovo PC with 1.7 GHz quad-core Intel i5 CPU and 8GB RAM.

The instances are generated in the following way. The processing time $t_i$ for job $i$ follows a uniform distribution between 10 and 100 minutes, while the power consumption per hour $p_i$ between 30 and 100kW/h. The TOU pricing scheme adopted in this paper is the one implemented in Shaanxi Province, whose parameters are shown in [16]. To test the performances of the two models, we utilize 8 groups of random instances with different number of jobs from 30 to 100 with an increment of 10. Note that the chosen processing horizon length (i.e., the makespan) can affect the performances of the two models as well as the feasibility of the problem. Obviously, when the processing time of each job in an instance takes the value of its upper bound (i.e., 100 minutes), we can obtain the least makespan needed to keep each problem of that scale feasible. Therefore, to better test the performances of the two models, we use different lengths of processing horizon. To achieve that, we test each problem under several given $K$ periods, and in each setting the feasibility of the problem is guaranteed by the above rule.

We test each setting of the problem with 10 instances, and the computational results are shown in Table I. To better demonstrate the performance of our model compared to the previous one under different settings, we propose the following measurement, which reflects how much our model is faster than the previous one under certain setting. Let $t_{O,N,K}$ denotes the average computational time of our model to solve the problem with $N$ jobs and $K$ periods and $t_{C,N,K}$ represents that of the previous model under the same setting. We define

$$F_{N,K} = \frac{t_{C,N,K}}{t_{O,N,K}}$$

From Table I, we can see that our model outperforms the previous one in terms of computational time, especially for large-size problems. For example, when dealing with problems with 100 jobs and 48 periods, the previous model cannot find the optimal solutions for all the random instances within one hour, while our model find the optimal solution within about 230 seconds on average. Specifically, the previous model cannot solve two of the ten instances to optimality within one hour. But the gaps from the lower bounds when the two instances are solved for one hour are both below 0.03%. Here we regard the computational time for the two instances both as 3600 seconds and calculate their mean. Even under such a circumstance, our model still runs nearly 5 times faster than the previous one. This is because the improved model is more compact in terms of the number of constraints.

# 4 CONCLUSION

This paper considers an energy-conscious single machine scheduling problem to minimize total electricity cost under the TOU tariffs. To tackle the problem, we formulate an improved mixed-integer linear programming model and compare it with a previous one. The computational results on randomly generated instances demonstrate that our model is more efficient in dealing with the problems, especially for large-size problems. In the future, efficient heuristics shall be developed, which can increase the problem scale solved greatly.
<table><caption>Table 1. Comparison of the two models under different settings</caption><thead><tr><th colspan="2">Problem</th><th colspan="2">CPU Time(s)</th><th rowspan="2">F<sub>N,K</sub></th></tr><tr><th>N</th><th>K</th><th>Our Model</th><th>Previous Model</th></tr></thead><tbody><tr><td rowspan="3">30</td><td>12</td><td>0.38</td><td>0.62</td><td>1.63</td></tr><tr><td>14</td><td>0.25</td><td>0.38</td><td>1.52</td></tr><tr><td>16</td><td>0.65</td><td>1.17</td><td>1.8</td></tr><tr><td rowspan="3">40</td><td>16</td><td>1.95</td><td>2.19</td><td>1.12</td></tr><tr><td>20</td><td>2.47</td><td>3.11</td><td>1.26</td></tr><tr><td>24</td><td>0.48</td><td>1.17</td><td>2.44</td></tr><tr><td rowspan="3">50</td><td>20</td><td>3.47</td><td>5.8</td><td>1.67</td></tr><tr><td>24</td><td>0.62</td><td>1.54</td><td>2.48</td></tr><tr><td>28</td><td>9.18</td><td>11.46</td><td>1.25</td></tr><tr><td rowspan="3">60</td><td>24</td><td>4.39</td><td>12.85</td><td>2.93</td></tr><tr><td>28</td><td>7.21</td><td>20.78</td><td>2.88</td></tr><tr><td>32</td><td>17.44</td><td>31.03</td><td>1.78</td></tr><tr><td rowspan="3">70</td><td>28</td><td>7.58</td><td>24.84</td><td>3.28</td></tr><tr><td>32</td><td>22.94</td><td>44.55</td><td>1.94</td></tr><tr><td>36</td><td>48</td><td>73.3</td><td>1.53</td></tr><tr><td rowspan="3">80</td><td>32</td><td>17.2</td><td>64.1</td><td>3.73</td></tr><tr><td>36</td><td>75.64</td><td>112.52</td><td>1.49</td></tr><tr><td>40</td><td>91.47</td><td>167.01</td><td>1.83</td></tr><tr><td rowspan="3">90</td><td>36</td><td>42.93</td><td>149.87</td><td>3.49</td></tr><tr><td>40</td><td>79.18</td><td>242.05</td><td>3.06</td></tr><tr><td>44</td><td>29.81</td><td>172.04</td><td>5.77</td></tr><tr><td rowspan="3">100</td><td>40</td><td>107.9</td><td>278.08</td><td>2.58</td></tr><tr><td>44</td><td>238.09</td><td>401.18</td><td>1.68</td></tr><tr><td>48</td><td>229.97</td><td>1138.44*</td><td>4.95</td></tr></tbody></table>

<footnote>*: Two of ten instances cannot be solved to optimality within 3600 seconds.</footnote>
5 REFERENCES

[1] Park, C.W., Kwon, K.S., Kim, W.B., Min, B.K., Park, S.J., Sung, I.H., Yoon, Y.S., Lee, K.S., Lee, J.H., and Seok, J. 2010. Energy consumption reduction technology in manufacturing – A selective review of policies, standards, and research, International Journal of Precision Engineering & Manufacturing, 10(5), pp 151-173.

[2] Group, T.C. 1998. Regional Electricity Emission Factors Final Report.

[3] Mouzon, G., and Yildirim, M.B. 2008. A framework to minimise total energy consumption and total tardiness on a single machine, International Journal of Sustainable Engineering, 1(2), pp 105-116.

[4] Tang Decai, L.L., Du Kai. 2006. On the development path of Chinese manufacturing industry based on resource restraint, Jiangsu Social Sciences, 4, pp 51-58.

[5] Cheng, J., Chu, F., Xia, W., and Ding, J. 2014. Bi-objective optimization for single-machine batch scheduling considering energy cost, International Conference on Control, Decision and Information Technologies, Metz, France, November 3-5, pp 236 - 241.

[6] Wang, Y., and Li, L. 2013. Time-of-use based electricity demand response for sustainable manufacturing systems, Energy, 63(1), pp 233-244.

[7] Pinedo, M.L. 2012. Scheduling: Theory, Algorithms, and Systems, Springer-Verlag New York.

[8] Hariri, A.M.A., and Potts, C.N. 1994. Single Machine Scheduling with Deadlines to Minimize the Weighted Number of Tardy Jobs, Management Science, 40(12), pp 1712-1719.

[9] Boland, N., Clement, R., and Waterer, H. 2016. A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems, INFORMS Journal on Computing, 28(1), pp 14-30.

[10] Liu, C., Yang, J., Lian, J., Li, W., Evans, S., and Yin, Y. 2014. Sustainable performance oriented operational decision-making of single machine systems with deterministic product arrival time, Journal of Cleaner Production, 85, pp 318-330.

[11] Yildirim, M.B., and Mouzon, G. 2012. Single-Machine Sustainable Production Planning to Minimize Total Energy Consumption and Total Completion Time Using a Multiple Objective Genetic Algorithm, IEEE Transactions on Engineering Management, 59(4), pp 585-597.

[12] Mouzon, G., Yildirim, M.B., and Twomey, J. 2007. Operational methods for minimization of energy consumption of manufacturing equipment, International Journal of Production Research, volume, 45(18), pp 4247-4271.

[13] Che, A., Lv, K., Levner, E., and Kats, V. 2015. Energy consumption minimization for single machine scheduling with bounded maximum tardiness, 12th IEEE International Conference on Networking, Sensing and Control, Taipei, April 9-11, pp146-150.

[14] Dürr, C., Jež, Ł., and Vásquez, O.C. 2014. Scheduling under dynamic speed-scaling for minimizing weighted completion time and energy consumption, Discrete Applied Mathematics, 196(C), pp 20-27

[15] Fang, K., Uhan, N.A., Zhao, F., and Sutherland, J.W. 2016. Scheduling on a single machine under time-of-use electricity tariffs, Annals of Operations Research, 238(1-2), pp 199-227

[16] Shrouf, F., Ordieres-Meré, J., García-Sánchez, A., and Ortega-Mier, M. 2014. Optimizing the production scheduling of a single machine to minimize total energy consumption costs, Journal of Cleaner Production, 67(6), pp 197-207

[17] Che, A., Zeng, Y., and Lyu, K. 2016. An efficient greedy insertion heuristic for energy-conscious single machine scheduling problem under time-of-use electricity tariffs, Journal of Cleaner Production, 129, pp 565-577.

[18] Ding, J.Y., Song, S., Zhang, R., and Chiong, R. 2016. Parallel Machine Scheduling Under Time-of-Use Electricity Prices: New Models and Optimization Approaches, IEEE Transactions on Automation Science & Engineering, 13 (2), pp 1138-1154.