# A Proposal of Scheduling Method Based on Decision Criteria Considering Electric Power Costs and Productivity

Masayuki Yabuuchi, Toshiya Kaihara, Nobutada Fujii, Daisuke Kokuryo, Mio Nonaka, Kotone Senju

► To cite this version:

Masayuki Yabuuchi, Toshiya Kaihara, Nobutada Fujii, Daisuke Kokuryo, Mio Nonaka, et al. A Proposal of Scheduling Method Based on Decision Criteria Considering Electric Power Costs and Productivity. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2021, Nantes, France. pp.637-645, 10.1007/978-3-030-85906-0_69. hal-04022132

HAL Id: hal-04022132

https://inria.hal.science/hal-04022132

Submitted on 9 Mar 2023

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# A proposal of scheduling method based on decision criteria considering electric power costs and productivity

Masayuki Yabuuchi¹, Toshiya Kaihara¹, Nobutada Fujii¹,

Daisuke Kokuryo¹, Mio Nonaka² and Kotone Senju²

¹ Graduate School of System Informatics, Kobe University,
1-1 Rokkodai-cho, Nada, Kobe, Hyogo 657-8501, Japan
yabuuchi@kaede.cs.kobe-u.ac.jp, kaihara@kobe-u.ac.jp,
nfujii@phoenix.kobe-u.ac.jp, kokuryo@port.kobe-u.ac.jp

² Mitsubishi Electric Corporation,
8-1-1 Tsukaguchi-honmachi, Amagasaki, Hyogo, 661-0001 Japan
Nonaka.Mio@dc.MitsubishiElectric.co.jp,
Senju.Kotone@ak.MitsubishiElectric.co.jp

**Abstract.** In recent years, the price of electricity in Japan has increased, and then manufacturing industries are required to implement production plan in consideration of the electric power costs. In response to this demand, production scheduling has to be implemented in consideration of several decision criteria such as productivity and electric power costs. In this paper, we propose a production scheduling with satisfying trade-off method in order to maintain productivity and reduce electricity costs, and evaluate the effectiveness of the proposed method.

**Keywords:** Production scheduling, Electric power costs, Satisficing trade-off method

## 1 Introduction

In Japan, the price of electricity has increased due to the change in the ratio of thermal power generation since the Great East Japan Earthquake [1]. In the manufacturing industry, the production activities are performed in consideration of reduction of the electric power costs such as peak shifting. Furthermore, in order to reduce the electric power costs, the manufacturing industry is considering the introduction of Energy Management System (EMS), the renewal and installation of energy-efficient equipment, and the production scheduling for electricity cost saving [2]. We have so far focused on the relationship between productivity and electricity in production lines, and proposed an optimized scheduling method that considers the total weighted productivity and electricity [3]. However, it was not clear how to set the weighting factor for multiobjective optimization problem in consideration of the various decision criteria. In order to solve this issue, we focus on the Satisficing Trade-Off Method (STOM), which is one of the multi-objective optimization technique. STOM is an optimization method that is satisfied with the multiple decision criteria [4], and is applied to scheduling problems and
layout optimization problems [5, 6]. In this paper, we propose a scheduling method using STOM that can simultaneously consider to reduce electric power costs and to maintain productivity. The computational experiments are carried out to evaluate the performance of the proposed method.

## 2 Target Model

In this paper, our target model is a flexible flow shop type production line including EMS as shown in Fig. 1. The electric power costs are different depending on the time range. The length of planning period, the number of jobs and the processing time of each job are determined in advance as practical case. The features of the stage, job, and machine in this paper are described as follows:

<figure><img src="image_3.png" /><figcaption>Fig. 1. A schematic diagram of the target model</figcaption></figure>

**Stage:**

* There are multiple machines in each stage.

* There is no capacity of each buffer between connected stages.

**Machine:**

* All machines can be used from the start of production.

* Each machine can process all jobs, but the ability such as processing time and electric power consumption differs depending on the machine.

* During the planning period, the state of each machine is either processing or idle, and the electric power consumption differs depending on the state.

* No interruption occurs during job processing.

* No machine failure occurs.

* Setup time is not considered.

**Job:**

* All jobs are known at the beginning of the production.

* Each job is assigned to only one machine in each stage, and each machine can process at most one job at a time.

* The job in a certain stage is started after the processing completion time in the previous stage.
# 3 Proposal of scheduling method based on decision criteria considering electric power costs and productivity

In production scheduling, it is important to obtain the appropriate solution in practical time even if the optimal solution cannot be acquired. Thus, we propose the scheduling method applying STOM in considering of various decision criteria such as electric power costs and productivity [4]. In the proposed method, the ideal level, which consists of the ideal value of each decision criteria and the aspiration level which is the satisfaction solution of each decision criteria, are set, and a solution which is satisfied for aspiration level is obtained. The algorithm of proposed method is described in Section 3.2, and the formulation of scheduling within the algorithm is shown in Section 3.3.

## 3.1 Notation

The definition of the characters used in the formulation is as follows:

### Parameters

* $j, k$: job number ($j, k = 1, ..., J$)

* $i$: stage number ($i = 1, ..., I$)

* $l$: machine number ($l = 1, ..., M_i$)

* $t$: timeslot number ($t = 0, ..., T - 1$)

* $a$: state number ($a = 1, ..., A$)

In this paper, there are two states: processing and idle, where $a = 1$ represents processing and $a = 2$ represents idle.

* $P_{ij}$: processing time of job $j$ at machine $l$ on stage $i$

* $EC_{ila}$: electric power consumption of state $a$ at machine $l$ on stage $i$

* $Rate_t$: electricity charges at time $t$

* $f_{cmax}^{best}$: ideal level of makespan

* $f_{cost}^{best}$: ideal level of electric power costs

* $\tilde{f}_{cmax}$: aspiration level of makespan

* $\tilde{f}_{cost}$: aspiration level of electric power costs

* $w_{cmax} = \frac{1}{\tilde{f}_{cmax} - f_{cmax}^{best}}$: weighting factor of makespan

* $w_{cost} = \frac{1}{\tilde{f}_{cost} - f_{cost}^{best}}$: weighting factor of electric power costs

* $\alpha$: weighting factor used for objective function

* $BigM$: large constant for constraints

### Variables

* $C_{max} \in \mathbb{N} \cup \{0\}$: makespan (total time from the start time of the planning period to the end time of the last job)

* $Cost \in \mathbb{R}_0^+$: electric power costs

* $s_{ij} \in \mathbb{N} \cup \{0\}$: start time of job $j$ at machine $l$ on stage $i$

* $c_{ij} \in \mathbb{N} \cup \{0\}$: completion time of job $j$ at machine $l$ on stage $i$
* $e_t \in \mathbb{R}_0^+$: electric power consumption at time t

* $x_{iljk} : \begin{cases} 1: & \text{if job } j \text{ precedes job } k \text{ at machine } l \text{ on stage } i \\ 0: & \text{otherwise} \end{cases}$

* $y_{iljt} : \begin{cases} 1: & \text{if job } j \text{ starts to process at time } t \text{ at machine } l \text{ on stage } i \\ 0: & \text{otherwise} \end{cases}$

* $ms_{ilat} : \begin{cases} 1: & \text{if machine } l \text{ on stage } i \text{ is in state } a \text{ at time } t \\ 0: & \text{otherwise} \end{cases}$

* $mp_{iljt} : \begin{cases} 1: & \text{if job } j \text{ is processing at time } t \text{ at machine } l \text{ on stage } i \\ 0: & \text{otherwise} \end{cases}$

* $z \in \mathbb{R}$: auxiliary variable

In our proposed method, $y_{iljt}$ is decision variable.

## 3.2 Algorithm of proposed method

In the proposed method using STOM, the purpose is to schedule based on the decision maker's value judgment, and obtain a schedule that the decision maker is satisfied with. The algorithm of proposed method is as follows.

**STEP1.** Set the ideal levels $f_{cmax}^{best}$ and $f_{cost}^{best}$, and show them to the decision maker. Each ideal level is set as the optimized solution in each single objective optimization problem.

**STEP2.** Decision maker determines the aspiration levels $\bar{f}_{cmax}$ and $\bar{f}_{cost}$. The aspiration level is the value the decision maker is satisfied.

**STEP3.** Solve the optimization problem shown in Section 3.3 and find the closest Pareto-optimal solution to the aspiration level given by the decision maker and show it to the decision maker.

**STEP4.** If the decision maker is satisfied with the shown schedule, the process ends. Otherwise, return to **STEP2** and reset the aspiration level.

## 3.3 Formulation

The scheduling problem in **STEP3** is formulated as follows:

$$ \min \quad OF = z + \alpha\{w_{cmax}(C_{max} - \bar{f}_{cmax}) + w_{cost}(Cost - \bar{f}_{cost})\} \quad (1) $$

$$ \text{where} \quad C_{max} = \max_{\forall i, \forall l, \forall j} \{c_{ilj}\} \quad (2) $$

$$ Cost = \sum_{\forall t} e_t \times Rate_t \quad (3) $$

$$ e_t = \sum_{\forall i} \sum_{\forall l} \sum_{\forall a} ms_{ilat} \times EC_{ila}, \forall t \quad (4) $$

$$ \text{s. t.} \quad \sum_{\forall l} \sum_{\forall t} y_{iljt} = 1, \forall i, \forall j \quad (5) $$

$$ s_{ilj} + c_{ilj} \leq BigM \times \sum_{\forall t} y_{iljt}, \forall i, \forall l, \forall j \quad (6) $$

$$ c_{ilj} \geq s_{ilj} + P_{ilj} - BigM(1 - \sum_{\forall t} y_{iljt}), \forall i, \forall l, \forall j \quad (7) $$

$$ \sum_{\forall l} s_{ilj} \geq \sum_{\forall l} c_{(i-1)lj}, \forall i \in \{I \setminus \{1\}, \forall j\} \quad (8) $$

$$ \sum_{\forall l} s_{ilj} = \sum_{\forall l} \sum_{\forall t} t \times y_{iljt}, \forall i, \forall j \quad (9) $$

$$ \sum_{\forall l} c_{ilj} = \sum_{\forall l} \sum_{\forall t} (t + P_{ilj}) \times y_{iljt}, \forall i, \forall j \quad (10) $$

$$ s_{ilk} \geq c_{ilj} - BigM(1 - x_{iljk}), \forall i, \forall l, \forall j, k, j \neq k \quad (11) $$

$$ s_{ilj} \geq c_{ilk} - BigM \times x_{iljk}, \forall i, \forall l, \forall j, k, j \neq k \quad (12) $$

$$ C_{max} \leq T \quad (13) $$
$$ \sum_{v_j} mp_{iljt} = ms_{il1t}, \forall i, \forall l, \forall t \qquad (14) $$

$$ \sum_{v_a} ms_{ilat} = 1, \forall i, \forall l, \forall t \qquad (15) $$

$$ \sum_{v_j} mp_{iljt} \le 1, \forall i, \forall l, \forall t \qquad (16) $$

$$ P_{ilj} \times y_{iljt} \le \sum_{q=t}^{t+P_{ilj}-1} mp_{iljq}, \forall i, \forall l, \forall j \text{ (if } P_{ilj} > 0 \text{ and } T-t \ge P_{ilj}) \qquad (17) $$

$$ P_{ilj} \times \sum_{v_t} y_{iljt} = \sum_{v_t} mp_{iljt}, \forall i, \forall l, \forall j \qquad (18) $$

$$ w_{cmax} (C_{max} - \bar{f}_{cmax}) \le z \qquad (19) $$

$$ w_{cost} (Cost - \bar{f}_{cost}) \le z \qquad (20) $$

Objective function (1) minimizes the sum of z and weighted dissatisfaction with both makespan and electric power costs. The auxiliary variable z represents the dissatisfaction levels for makespan and electric power costs. The dissatisfaction level for makespan and electric power costs are close as much as possible by minimizing z, and reduce the dissatisfaction with both makespan and electric power costs. The second term of the objective function is a correction term to prevent weak Pareto solutions, and the weighting factor α should be small enough to prevent the second term from becoming dominant [7]. Equations (5) – (20) are constraints. Equation (5) guarantees that a job is assigned to one machine in each stage. Equations (6) – (10) are constraints on the start and completion times. Equations (11) and (12) represents the precedence relation constraints for jobs. Equation (13) is a constraint that prevents the makespan from exceeding the planning period. Equations (14) - (16) are constraints on the allocation of machines and jobs. Equations (17) and (18) are constraints to determine the operating state of the machine. Equations (19) and (20) are inequalities that select the evaluation criteria with the weighted dissatisfaction levels for makespan and the electric power costs using the auxiliary variable z.

# 4 Computational experiments

In order to evaluate the relationship between the ideal level and the aspiration level acquired the schedule, the computational experiments are performed with different conditions. In this paper, **STEP4** of Section 3.2 is not executed and the aspiration level is not reset as basic study. IBM ILOG CPLEX 12.9 [8] is used to solve the scheduling problem. The evaluation criteria are as follows:

* $C_{max}$ : makespan

* Cost : electric power costs

* MSNA = $\frac{C_{max}-\bar{f}_{cmax}}{\bar{f}_{cmax}-f_{best}}$ : the dissatisfaction degree of makespan

* CONA = $\frac{Cost-\bar{f}_{cost}}{\bar{f}_{cost}-f_{best}}$ : the dissatisfaction degree of electric power costs

## 4.1 Experimental conditions

In general, each production machine differs the required manufacturing time and usage electric power for making the same product. In order to take into consideration these conditions, this experiment assumes that each stage has two type machines: Machine 1 in each stage has a high job processing speed but high power consumption, and
Machine 2 in each stage has a slower job processing speed and lower electric power consumption than Machine 1. There are three price time range for electricity charges; high, middle and low. We set the experimental conditions to understand the characteristics of the proposed method as follows:

* Total number of jobs (J): 8

* Total number of stages (I): 2

* The number of machines in each stage ($M_i$): 2

* Total number of timeslots (T): 48

* Total number of states (A): 2 ($a = 1$, represents processing; $a = 2$, represents idle)

* Processing time of job j at machine 1 on stage i ($P_{i1j}$): 2(1 ≤ j ≤ 4), 3(5 ≤ j ≤ 8)

* Processing time of job j at machine 2 on stage i ($P_{i2j}$): 4(1 ≤ j ≤ 4), 6(5 ≤ j ≤ 8)

* Electric power consumption of state a at machine 1 on stage i ($EC_{i1a}$): 80($a = 1$), 8($a = 2$)

* Electric power consumption of state a at machine 2 on stage i ($EC_{i2a}$): 10($a = 1$, state is processing), 1($a = 2$, state is idle)

* Electricity charges ($Rate_t$): 5(0 ≤ t < 16), 10(16 ≤ t < 32), 1(32 ≤ t < 48)

* BigM: 50000

* Weighting factor for the second term of the objective function ($\alpha$): $1.0 \times 10^{-3}$

An appropriate $\alpha$ value is set by conducting a preliminary experiment.

## Setting the ideal and aspiration level of makespan and electric power costs

The ideal level of makespan $f_{cmax}^{best}$ and electric power costs $f_{cost}^{best}$ are set the value acquired from the makespan and electric power costs minimization scheduling problem respectively as follows:

* Ideal level of makespan ($f_{cmax}^{best}$): 17

* Ideal level of electric power costs ($f_{cost}^{best}$): 6714

For setting the aspiration level of makespan and electric power costs, the four cases of aspiration level are used as shown in Table 1. In Case 1, the both aspiration levels are twice as many as the ideal levels. In Case 2, the aspiration level for electric power costs is increased from Case 1 as tougher requirement. In Case 3, the aspiration level for makespan is increased. In Case 4, the both aspiration level is 1.2 times as many as the ideal levels. In this time, Case 1 is loose aspiration level that gets a result that meets the aspiration level. Case 2 - 4 values are set to analyze how the scheduling result will be affected if the aspiration level of each evaluation criteria or all of them are increased.

<table><caption>**Table 1.** Aspiration level of makespan and electric power costs</caption><thead><tr><td>Case</td><td>f&#773;<sub>cmax</sub></td><td>f&#773;<sub>cost</sub></td></tr></thead><tbody><tr><td>1</td><td>34 (f<sup>best</sup><sub>cmax</sub> × 2.0)</td><td>13428 (f<sup>best</sup><sub>cost</sub> × 2.0)</td></tr><tr><td>2</td><td>34 (f<sup>best</sup><sub>cmax</sub> × 2.0)</td><td><b>8057</b> (f<sup>best</sup><sub>cost</sub> × 1.2)</td></tr><tr><td>3</td><td><b>20</b> (f<sup>best</sup><sub>cmax</sub> × 1.2)</td><td>13428 (f<sup>best</sup><sub>cost</sub> × 2.0)</td></tr><tr><td>4</td><td><b>20</b> (f<sup>best</sup><sub>cmax</sub> × 1.2)</td><td><b>8057</b> (f<sup>best</sup><sub>cost</sub> × 1.2)</td></tr></tbody></table>
## 4.2 Experimental result

Table 2 shows the evaluation values acquired from solving the scheduling problem using proposed method with each case. The schedules acquired from Case 1 and Case 2 are shown in Fig. 2. The objective function value *OF* is less than or equal to zero when all aspiration levels are satisfied. In Case 1, the objective function value is negative and both the aspiration level of makespan and electric power costs are satisfied. On the other hand, in Cases 2 to 4, the objective function values are positive because the some aspiration levels are not satisfied. In Case 2, the aspiration level of electric power costs is increased, and then the electric power costs decrease as shown in Table 2. As shown in Fig. 2, Job 1 (Blue box) and Job 4 (Pink box) in Case 2 are processed in low price range to reduce the electric power costs. Thus, the result in Case 2 indicates that the proposed method can adjust the production schedule for satisfying the aspiration level. However, the aspiration level of electric power costs in Case 2 may be strict, so *CONA* in Case 2 is positive and then the *OF* and *MSNA* are positive. In Case 3, the aspiration level of electric power costs increase from the level in Case 1 though the aspiration level of makespan is satisfied. This indicates that the proposed method may adjust the schedule to satisfy the strict aspiration level of makespan. In Case 4, the both aspiration levels are increased so that the proposed method may acquire the schedule while adjusting *MSNA* and *CONA* to improve the both values. Therefore, these results indicate that it is possible to adjust the production schedule in consideration of *MSNA* and *CONA* using the proposed method.

<table><caption>**Table 2.** Results of Experiment</caption><thead><tr><th>Case (f&#772;<sub>cmax</sub>, f&#772;<sub>cost</sub>)</th><th>OF</th><th>MSNA (C<sub>max</sub>)</th><th>CONA (Cost)</th></tr></thead><tbody><tr><td>1 (34, 13428)</td><td><strong>-0.118</strong></td><td><strong>-0.1176 (32)</strong></td><td><strong>-0.1206 (12618)</strong></td></tr><tr><td>2 (34, 8057)</td><td>0.353</td><td><strong>0.3529 (40)</strong></td><td><strong>0.1124 (8208)</strong></td></tr><tr><td>3 (20, 13428)</td><td>0.174</td><td><strong>0.0 (20)</strong></td><td><strong>0.1743 (14598)</strong></td></tr><tr><td>4 (20, 8057)</td><td>3.67</td><td><strong>3.333 (30)</strong></td><td><strong>3.664 (12978)</strong></td></tr></tbody></table>

<figure><img src="image_4.png" /><figcaption>**Fig. 2.** Schedules obtained in Case 1 and Case 2. Red arrow: some jobs are scheduled in low price range in Case 2.</figcaption></figure>
# 5 Conclusion

In this paper, we proposed a scheduling method that can handle decision criteria of productivity and electric power costs in the flexible flow shop type production line with usage electric power. As a result of the experiment, we have confirmed that the proposed method can adjust the production schedule in consideration of the various decision criteria such as productivity and electric power costs. In future work, we will implement the adjustment mechanism of aspiration level autonomously and consider how to set the aspiration level to satisfy decision makers. Then, with the aim of applying it to the realization field, we will investigate the characteristics of the proposed method such as the calculation time and the scale of the problem that can obtain the optimum result, and compare it with other multi-objective optimization methods.

# References

1. Agency for Natural Resources and Energy, 2020 Japan's Energy Problems (Part 1), https://www.enecho.meti.go.jp/about/special/johoteikyo/energyissue2020_1.html

2. C Gahm et al.: Energy-efficient scheduling in manufacturing companies: A review and research framework. European Journal of Operational Research, Vol. 248, Issue 3, pp. 744-757. (2016)

3. M. Yabuuchi et al.: A Basic Study on Scheduling Method for Electric Power Saving of Production Machine. In: IFIP International Conference on Advances in Production Management Systems. Springer, Cham, pp. 524-530. (2020)

4. H. Nakayama, and Y. Sawaragi.: Satisficing trade-off method for multiobjective programming and its applications. IFAC Proceedings Vol. 17, Issue 2, pp. 1345-1350. (1984)

5. H. Tamura et al.: Multiobjective combinatorial optimization for performance evaluation by a meta-heuristic satisficing tradeoff method. In: Global Production Management. Springer, Boston, MA, pp. 490-497. (1999)

6. M. Shirakawa., & M. Arakawa.: Multi-objective optimization system for plant layout design (3rd report, Interactive multi-objective optimization technique for pipe routing design). Journal of Advanced Mechanical Design Systems, and Manufacturing, Vol. 12, No. 2, p. JAMDSM0053. (2018)

7. H. Nakayama et al.: Multi-Objective Optimization and Engineering Design-Supply Systems Engineering Approach-, Gendaitosho Co.,Ltd, Japan (2008) [published in Japanese].

8. ILOG CPLEX-IBM, https://www.ibm.com/jp-ja/products/ilog-cplex-optimization-studio