# Combinatorial Benders' Cut for the Admission Control Decision in Flow Shop Scheduling Problems with Queue Time Constraints

Rudi Nurdiansyah, I-Hsuan Hong

► To cite this version:

Rudi Nurdiansyah, I-Hsuan Hong. Combinatorial Benders' Cut for the Admission Control Decision in Flow Shop Scheduling Problems with Queue Time Constraints. IFIP International Conference on Advances in Production Management Systems (APMS), Aug 2018, Seoul, South Korea. pp.399-405, 10.1007/978-3-319-99704-9_49. hal-02164907

HAL Id: hal-02164907

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

Submitted on 25 Jun 2019

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
Combinatorial Benders' cut for the admission control
decision in flow shop scheduling problems with queue
time constraints

Rudi Nurdiansyah¹,² and I-Hsuan Hong¹✉

¹ Institute of Industrial Engineering, National Taiwan University, Taipei 10617, Taiwan

² Department of Industrial Engineering, Universitas Negeri Malang, Malang 65145, Indonesia
ihong@ntu.edu.tw

**Abstract.** This paper presents the mixed-integer linear programming (MILP) based model to approach the admission control in flow shop scheduling problem with queue time constraints, where there are various upper bounds limit in each queue. The scheduling proposed in this paper iteratively retrieves the real-time status of a production system such as machine failures and recoveries, and job arrivals in each step and generate the most updated scheduling result at each decision time. Our objective function is to minimize the occurrence of queue time violation. We solve the MILP using combinatorial Benders' cut (CBC), where the MILP model is decomposed into two independent parts: the binary variables as a master problem and the continuous variables as a slave problem. We compare the CBC with the results gained from the CPLEX. The numerical results indicate that the CBC indeed effectively and efficiently reaches the good feasible solution within a reasonable timeframe in the context of timely updating scheduling problem.

**Keywords:** flow shop, queue time constraint, combinatorial Benders' cut.

# 1 Introduction

Flow shop production is a common system in a manufacturing system, where there are several steps and each step has multiple machines. A current mega factory may have a hundred of steps and machines with thousands of jobs; hence, the flow shop scheduling is a challenge nowadays. Furthermore, each step in a flow shop typically has queue time constraints, which prescribes an upper bound of waiting time between two consecutive steps. Such constraints are commonly observed in the semiconductor manufacturing [1] and [2], food industries [3], and steel-making industries [4]. A typical queue time constraint occurs after the furnace tube operations in a semiconductor wafer fabrication process since the queue time constraint can avoid the absorption of the particulates in air [5].

Due to the stochastic nature, several studies apply Markov decision processes to flow shop scheduling problems with queue time constraints such as [6] and [7]. [8] investigates a two-step model to determine the admission control of jobs in a flow
shop scheduling with queue time constraints while it may not return the decision as the problem size increases due to *curse of dimensionality* [9]. Moreover, the communication with industries reveals that statistical distribution information may be unavailable in the real-world production system or the front line manager may not believe that the statistical model from historical data precisely describes the future stochastic process in the manufacturing line.

Another approach for flow shop scheduling problem with queue time constraints is heuristics [10], [11] and [12]. [10] uses the ant colony optimization algorithm (ACO) to propose a feasible solution of admission control problems. [11] determines a threshold to decide whether the job is admissible to each step. [12] investigates production scheduling with queue time constraints in semiconductor manufacturing by using several heuristics methods. Although heuristics methods are able to look for a feasible (or near optimal) solution within a reasonable time, the heuristics solutions may perform poorly if it falls into a pitfall of local optimum. The lack of flexibility to the change in heuristics model settings is another disadvantage.

We present a mixed integer linear programming (MILP) based model to approach the admission control decision in a flow shop with queue time constraints by frequently revising uncertain parameters such as machine failures and job arrival processes in each step in the model. Due to the fast development of Industry 4.0, the vast deployment of monitoring sensors enables frequently updating uncertain parameters in a stochastic nature production system to enhance the accuracy of a deterministic model approaching a stochastic nature system.

We further use combinatorial Benders' cuts (CBC) to promptly solve the MILP model when uncertain parameters are frequently revised according to the most updated information from deployed sensors in a production system. With the CBC, the proposed MILP is decomposed into two independent parts: integer and continuously parts. The decomposition technique allows us to accelerate the computational time and combines the if-then rule to reduce redundant constraints with the big-M method.

CBC is a relatively new method to solve MILP problems containing “big-M” [13]. Successful applications of CBC for solving integer programming models have been shown by [14] and [15]. [14] used CBC to solve quayside operations problem at container terminals and reported that their approach is more efficient than the branch and cut algorithm. [15] solved assembly line balancing problem and notified that the CBC is capable to solve small to medium instances. [16] proposed a modification of CBC for solving a vaccine allocation problem. Their computational results confirm that these cuts extensively reduce solution times and the number of nodes explored in the branch-and-bound tree for their problem.

The CBC will be applied to solve the admission control decision in a flow shop scheduling problem with queue time constraints. The comparison between our proposed method with the commercial optimization package ILOG CPLEX solver (IBM ILOG 2014) shows that our method has better performance than the results gained from the CPLEX. The remainder of the paper is organized as follows. Section 2 describes the problem and mathematically formulates the proposed MILP model. Section 3 introduces the solution methodology of CBC and the computation results. Section 4 concludes of the research.
## 2 The Model

The proposed model considers a multi-step manufacturing process where each step has multiple identically machines with a common queue. In each consecutive step, only one machine can process one job at most in each time, and one job can only be processed by one machine in each step. Various upper bounds limit the waiting times in each queue. If the queue time is longer than the upper bound of the queue time constraints, the job cannot be further processed and becomes scrapped.

A real-world production system involves with several uncertainties including machine failures and recovery, and job arrival processes in each step. Unexpected uncertain events typically cause the scheduled production plan infeasible to a real-world production system and lead to a substantial loss due to scraped jobs. We explore such stochastic-nature flow shop scheduling problems with queue time constraints by frequently revising uncertain parameters in a production system and solving the mixed integer linear programming model (MILP) for admission control decisions of jobs. Following the similar concept, the scheduling proposed in this paper iteratively retrieves the real-time status of a production system such as machine failures and recoveries, and job arrivals in each step and generate the most updated scheduling result at each decision time. The parameters and decision variables of the model are described in Table 1. Equations (1)-(10) are the objective functions and the constraints.

<table><caption>**Table 1.** Parameters and decision variables</caption><thead><tr><th>Parameters:</th><th>Decision variables:</th></tr></thead><tbody><tr><td>S total number of steps in the production loop;</td><td>s<sup>f</sup><sub>q,i</sub> starting time of job i in queue q at future step f;</td></tr><tr><td>M<sup>f</sup> number of machines at step f;</td><td>c<sup>f</sup><sub>q,i</sub> ending time of job i in queue q at future step f;</td></tr><tr><td>Ω<sub>q</sub> set of jobs in queue q;</td><td>e<sup>f</sup><sub>q,i</sub> queue time violation of job i in queue q at future step f;</td></tr><tr><td>p<sup>f</sup><sub>j</sub> processing time of machine j at step f;</td><td>k<sup>f</sup><sub>q,m,p,n</sub> 0-1 variable that is equal to 1 if job m in queue q at future step f is produced before job n in queue p, 0 otherwise;</td></tr><tr><td>qT<sup>f</sup> queue time limit of step f;</td><td>y<sup>f</sup><sub>q,i,j</sub> 0-1 variable that is equal to 1 if job i in queue q will be processed in machine j in future step f, 0 otherwise;</td></tr><tr><td>a<sup>f</sup><sub>j</sub> earliest time of machine j can process at step f;</td><td></td></tr><tr><td>T current time decision</td><td></td></tr></tbody></table>

$$ \min_{s,e} \sum_{q=1}^{S} \sum_{i=1}^{|\Omega_q|} \sum_{f=q}^{S} \left( s_{q,i}^{f} + \frac{\alpha}{S-f} \cdot e_{q,i}^{f} \right) \qquad (1) $$

subject to

$$ \sum_{j=1}^{M^f} y_{q,i,j}^{f} = 1, \forall q \in \{1, \dots, S\}, \forall i \in \Omega_q, \forall f \in \{q, \dots, S\} \qquad (2) $$

$$ s_{q,i}^{f} + \sum_{j=1}^{M^f} p_{j}^{f} \cdot y_{q,i,j}^{f} = c_{q,i}^{f}, \forall q \in \{1, \dots, S\}, \forall i \in \Omega_{q}, \forall f \in \{q, \dots, S\} \qquad (3) $$
$$s_{q,i}^{f} \geq \sum_{j=1}^{M} a_{j}^{f} \cdot y_{q,i,j}^{f}, \forall q \in \{1, \dots, S\}, \forall i \in \Omega_{q}, \forall f \in \{q, \dots, S\} \quad (4)$$

$$s_{q,i}^{f} \geq c_{q,i}^{f-1}, \forall q \in \{2, \dots, S\}, \forall i \in \Omega_{q}, \forall f \in \{q, \dots, S\} \quad (5)$$

$$s_{1,i}^{1} \geq T, \forall i \in \Omega_{1} \quad (6)$$

$$s_{q,i}^{f} - c_{q,i}^{f-1} - qT^{f} \leq e_{q,i}^{f}, \forall q \in \{2, \dots, S\}, \forall i \in \Omega_{q}, \forall f \in \{q, \dots, S\} \quad (7)$$

$$s_{q,m}^{f} + M \left( 2 + k_{q,m,q',n}^{f} - y_{q,m,j}^{f} - y_{q',n,j}^{f} \right) \geq c_{q',n}^{f} \\ \forall q \in \{1, \dots, S\}, \forall i \in \Omega_{q}, \forall f \in \{q, \dots, S\} \quad (8)$$

$$s_{q',n}^{f} + M \left( 3 - k_{q,m,q',n}^{f} - y_{q,m,j}^{f} - y_{q',n,j}^{f} \right) \geq c_{q,m}^{f} \\ \forall q \in \{1, \dots, S\}, \forall i \in \Omega_{q}, \forall f \in \{q, \dots, S\} \quad (9)$$

$$s_{f,1}^{f} \leq \dots \leq s_{f,|\Omega_{f}|}^{f} \leq s_{f-1,1}^{f} \leq \dots \leq s_{f-1,|\Omega_{f-1}|}^{f} \leq \dots \leq s_{1,|\Omega_{1}|}^{f} \\ \forall f \in \{1, \dots, S\} \quad (10)$$

The objective function as shown in (1) is to minimize the starting time of all jobs at each step and to minimize the occurrence of queue time violation. $\alpha$ is a weight value, how much the price must be paid if there is a situation that exceeds the queue time limit. The denominator $S-f$ is used to indicate that the downstream site does not want to exceed the queue time limit.

Constraint (2) shows that every job must be processed to one of the machines at each step. Constraint (3) determines the ending time of job $i$, by adding the starting time of job $i$ with processing time of machine $j$ that processes job $i$. Starting time of job $i$ processed by machine $j$ must be greater than or equal to the allowable time as described in constraint (4). Constraint (5) means job $i$ starts to be processed at step $f$ if job $i$ has been completed in the previous step. Starting time of the first step must be larger than or equal the time when the decision is made as shown in constraint (6).

Constraint (7) is set as inequality. When the value calculated on the left is negative, variable $e_{q,i}^f$ can be any positive number. But with the goal of minimum variable $e_{q,i}^f$, this variable automatically controls zero as the best solution. When the value calculated on the left is positive, variable $e_{q,i}^f$ is also controlled to be equal to this positive number.

This study discusses flow shop scheduling problem with parallel machines. Constraints (8) and (9) indicate that when two jobs are allocated to the same machines at the same time, successive relations must be considered. This is the most complicated to modeling the Big M method. When $y_{q,m,j}^f$ and $y_{q',n,j}^f$ are both 1, the job $m$ and $n$ are assigned to the machine $j$ at step $f$ at the same time. At this point, we have to use the decision variable $k_{q,m,q',n}^f$ to control the sequence. If $k_{q,m,q',n}^f$ is 1, job $m$ has priority than job $n$ to be processed. Constraint (8) will be a redundant constraint. Constraint
(9) will restrict the starting time of job *n* after the completion time of job *m*. On the contrary, if $k_{q,m,q',n}^f$ is 0, job *n* has priority to be processed. The last constraints means all job in this model follow FIFO rules as shown in (10).

## 3 Solution approach and numerical results

We apply the CBC to solve the proposed MILP model, where the model is decomposed into two sub problems: the binary variables $y_{q,i,j}^f$, $k_{q,m,q',n}^f$ as master problem and the continuous variables $s_{q,i}^f$, $c_{q,i}^f$, $e_{q,i}^f$ as slave problem. The first phase is to solve the master problem and to find a set of feasible solution $Y^*$. The master problem is integer programming, so the variables are binary variables. The result simply involves every set of feasible solutions. Furthermore, we take the result from the first phase into the slave problem. All constraints in the slave problem are continuous variables. Consequently, the slave problem turns into a linear programming. Now, we can promptly obtain the solution to the problem. The master problem and slave problem is stated as follows:

Master problem:

$$ \min Y^* $$

s.t. constraints (2), (8), and (9)

Slave problem:

$$ \min_{s,e} \sum_{q=1}^{S} \sum_{i=1}^{|\Omega_q|} \sum_{f=q}^{S} \left( s_{q,i}^{f} + \frac{\alpha}{S-f} \cdot e_{q,i}^{f} \right) $$

s.t. constraints (3), (4), (5), (6), (7), and (10)

We compare the CBC on our proposed model for a six-step flow shop production system with queue time constraints with the results obtained from the CPLEX. The columns of MILP and CBC in Table 2 summarizes the returned objective function values within 180 seconds obtained from the CPLEX and CBC, respectively for the various problem sizes.

<table><caption>Table 2 The comparison of CBC and CPLEX results</caption><thead><tr><th rowspan="2">Number of jobs</th><th colspan="2">Return solution</th><th>Performance improvement (%)</th></tr><tr><th>MILP</th><th>CBC</th><th>MILP - CBC<br>MILP</th></tr></thead><tbody><tr><td>20</td><td>35,340</td><td>35,340</td><td>0.00</td></tr><tr><td>40</td><td>150,467,395</td><td>4,436,735</td><td>97.05</td></tr><tr><td>60</td><td>No Solution</td><td>3,315,546,045</td><td>N/A</td></tr><tr><td>80</td><td>No Solution</td><td>12,972,160,360</td><td>N/A</td></tr><tr><td>100</td><td>No Solution</td><td>26,535,369,685</td><td>N/A</td></tr></tbody></table>
As the number of jobs in the system remains in 20, the CPLEX and CBC return the same quality solution. However, the CBC outperforms the CPLEX when the number of jobs in the system increases to 40. The CPLEX even cannot obtain the initial feasible solution within 180 seconds when the problem size reaches 60, 80, and 100. The numerical results demonstrate that the CBC indeed effectively and efficiently reaches the good feasible solution within a reasonable timeframe in the context of timely updating scheduling problem.

## 4 Conclusions

In this paper, we propose the Mixed Integer Linear Programming (MILP) based model to approach flow shop scheduling problems with queue time constraints. We devise the model with queue time constraints by the big-M method. The model updates the machine failures and recoveries, and job arrival processes in each step at each decision time.

The model is decomposed into two independent parts, the binary variables as a master problem and the continuous variables as a slave problem in order to create the combinatorial Benders' cut. The numerical results of the CBC are compared with the results obtained from the CPLEX. The algorithms is tested on a six-step flow shop production system with queue time constraints. The results show that the CBC has an effectively and efficiently the good feasible solution. The CPLEX even has no solution when the problem size reaches 60, 80 and 100 jobs within 180 seconds.

## References

1. Scholl, W., Domaschke, J.: Implementation of modeling and simulation in semiconductor wafer fabrication with time constraints between wet etch and furnace operations. IEEE Transactions on Semiconductor Manufacturing 13(3), 273-277 (2000).

2. Robinson, J. K., Giglio, R.: Capacity planning for semiconductor wafer fabrication with time constraints between operations. In: Proceedings of the 31st Conference on Winter Simulation, pp. 880-887. ACM, Arizona, USA (1999).

3. Akkerman, R., Van Donk, D. P., Gaalman, G.: Influence of capacity and time-constrained intermediate storage in two-stage food production systems. International Journal of Production Research 45(13), 2955-2973 (2007).

4. Harjunkoski, I., Grossmann, I. E.: A decomposition approach for the scheduling of a steel plant production. Computers & Chemical Engineering 25(11-12), 1647-1660 (2001).

5. Su, L. H.: A hybrid two-stage flow shop with limited waiting time constraints. Computer and Industrial Engineering 44, 409-424 (2003).

6. Wu, C. H., Lin, J. T., Chien, W. C.: Dynamic production control in a serial line with process queue time constraint. International Journal of Production Research 48(13), 3823-3843 (2010).

7. Wu, C. H., Lin, J. T., Chien, W. C.: Dynamic production control in parallel processing systems under process queue time constraints. Computers & Industrial Engineering 63(1), 192-203 (2012).
8. Wu, C. H., Chien, W. C., Chuang, Y. T., Cheng, Y. C.: Multiple product admission control in semiconductor manufacturing systems with process queue time (PQT) constraints. Computers & Industrial Engineering 99, 347-363 (2016).

9. Bellman, R.: Dynamic Programming. Courier Dover Publications, New York (2003).

10. Guo, C., Zhibin, J., Zhang, H., Li, N.: Decomposition-based classified ant colony optimization algorithm for scheduling semiconductor wafer fabrication system. Computers & Industrial Engineering 62(1), 141-151 (2012).

11. Wu, K., Zhao, N., Gao, L., Lee, C. K. M.: Production control policy for tandem workstations with constant service times and queue time constraints. International Journal of Production Research 54(21), 6302-6316 (2016).

12. Kim, Y. D., Joo, B. J., Choi, S. Y.: Scheduling wafer lots on diffusion machines in a semiconductor wafer fabrication facility. IEEE Transactions on Semiconductor Manufacturing 23(2), 246-254 (2010).

13. Codato, G., Fischetti, M.: Combinatorial Benders' cuts for mixed-integer linear programming. Operations Research 54(4), 756-766 (2006).

14. Chen, J. H., Lee, D. H., Cao, J. X.: A combinatorial benders' cuts algorithm for the quayside operation problem at container terminals. Transportation Research Part E: Logistics and Transportation Review 48(1), 266-275 (2012).

15. Akpinar, S., Elmi, A., Bektaş, T.: Combinatorial Benders cuts for assembly line balancing problems with setups. European Journal of Operational Research 259(2), 527-537 (2017).

16. Tanner, M.W., Ntaimo, L.: IIS branch-and-cut for joint chance-constrained stochastic programs and application to optimal vaccine allocation. European Journal of Operational research 207(1), 290-296 (2010).