# American Institute of Mathematical Sciences

• Previous Article
An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information
• JIMO Home
• This Issue
• Next Article
Open-loop equilibrium strategy for mean-variance portfolio selection: A log-return model
March  2021, 17(2): 779-803. doi: 10.3934/jimo.2019134

## Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems

 1 School Economics and Management, Nanjing University of Science and Technology, Nanjing 210094, China 2 Graduate School of Business, Doshisha University, Karasuma-Imadegawa, Kamigyo-ku, Kyoto, 602-8580, Japan

* Corresponding author: Zhe Zhang

Received  April 2019 Revised  July 2019 Published  October 2019

Fund Project: This research was sponsored by Natural Science Foundation of China (NSFC Grant no. 71401075). We thank Professor Xiuli Wang and Ding Zhang for their valuable discussions and comments, and we would like to express our appreciation to all the reviewers and editors who contributed to this research

Seru production is one of the latest manufacturing modes arising from Japanese production practice. Seru can achieve efficiency, flexibility, and responsiveness simultaneously. To accommodate the current business environment with volatile demands and fierce competitions, seru has attracted more and more attention both from researchers and practitioners. A new planning management system, just-in-time organization system (JIT-OS), is used to manage and control a seru production system. The JIT-OS contains two decisions: seru formation and seru loading. By seru formation, a seru system with one or multiple appropriate serus is configured; by seru loading, customer ordered products are allocated to serus to implement production plans. In the process of seru formation, workers have to be assigned to serus. In this paper, a seru loading problem with worker assignment is constructed as a bi-level programming model, and the worker assignment on the upper level is to minimize total idle time while the lower level is to minimize the makespan by finding out optimal product allocation. A product lot can be splitted and allocated to different serus. The problem of this paper is shown to be NP-hard. Therefore, a simulated annealing and genetic algorithm (SA-GA) is developed. The SA is for the upper level programming and the GA is for the lower level programming. The practicality and effectiveness of the model and algorithm are verified by two numerical examples, and the results show that the SA-GA algorithm has good scalability.

Citation: Lan Luo, Zhe Zhang, Yong Yin. Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial & Management Optimization, 2021, 17 (2) : 779-803. doi: 10.3934/jimo.2019134
##### References:

show all references

##### References:
Three types seru
Whole bi-level decision procedure
The outline of SA-GA algorithm
An example of SA encoding
The genetic encoding based on allocation ratios
The flowchart of SA-GA algorithm
The minimum idle time in each iteration of SA
Idle time and makespan
The worker assignment decision
The worker assignment decision
The parameter setting of SA-GA algorithm
 Level Algorithm Parameters Upper SA $T\_max=10000$ $T\_min=0.1$ $II=20$ $\alpha=0.9$ Lower GA $pop\_size=300$ $GEN=500$ $p\_zero1=0.75$ $p\_zero2=0.25$ $p\_cross=0.9$ $p\_muta=0.1$
 Level Algorithm Parameters Upper SA $T\_max=10000$ $T\_min=0.1$ $II=20$ $\alpha=0.9$ Lower GA $pop\_size=300$ $GEN=500$ $p\_zero1=0.75$ $p\_zero2=0.25$ $p\_cross=0.9$ $p\_muta=0.1$
 Product Worker's processing time (min) Demand Setup(min) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 23 23 21 22 21 24 22 – 21 24 22 – 24 24 23 95 4 2 – 32 37 32 – 34 37 31 34 31 – 31 36 36 37 100 9 3 41 43 – – 44 47 42 42 – 41 47 45 44 42 – 130 8 4 29 28 29 28 26 27 26 27 27 28 26 31 31 – 28 105 6 5 17 – 17 16 19 17 – 18 16 16 20 20 18 16 17 120 5 6 42 23 20 33 38 33 27 29 – 34 33 29 30 36 19 145 6 7 – 68 48 63 43 71 49 21 66 59 53 – – 70 83 50 4 8 14 15 14 20 – 19 19 17 22 19 17 18 – 15 10 115 1 1 The '-' means that the worker cannot produce the product.
 Product Worker's processing time (min) Demand Setup(min) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 23 23 21 22 21 24 22 – 21 24 22 – 24 24 23 95 4 2 – 32 37 32 – 34 37 31 34 31 – 31 36 36 37 100 9 3 41 43 – – 44 47 42 42 – 41 47 45 44 42 – 130 8 4 29 28 29 28 26 27 26 27 27 28 26 31 31 – 28 105 6 5 17 – 17 16 19 17 – 18 16 16 20 20 18 16 17 120 5 6 42 23 20 33 38 33 27 29 – 34 33 29 30 36 19 145 6 7 – 68 48 63 43 71 49 21 66 59 53 – – 70 83 50 4 8 14 15 14 20 – 19 19 17 22 19 17 18 – 15 10 115 1 1 The '-' means that the worker cannot produce the product.
 1 2 3 4 5 6 7 8 1 – 100 – – 80 – 50 115 2 – – 130 – – 116 – – 3 95 – – 105 40 29 – –
 1 2 3 4 5 6 7 8 1 – 100 – – 80 – 50 115 2 – – 130 – – 116 – – 3 95 – – 105 40 29 – –
Production timetable
 Product 1 2 3 4 5 Seru 3 1 2 3 1 Starting time Monday 8:00 Monday 8:00 Monday 8:00 Tuesday 9:13 Tuesday10:22 Finishing time Tuesday 9:07 Tuesday 10:17 Wednesday 11:30 Wednesday 15:54 Tuesday 16:09 Product 5 6 6 7 8 Seru 3 2 3 1 1 Starting time Wednesday 15:59 Wednesday 11:36 Thursday 9:25 Tuesday 16:13 Thursday 8:05 Finishing time Thursday 9:19 Thursday 17:12 Thursday 16:29 Thursday 8:04 Thursday 17:07
 Product 1 2 3 4 5 Seru 3 1 2 3 1 Starting time Monday 8:00 Monday 8:00 Monday 8:00 Tuesday 9:13 Tuesday10:22 Finishing time Tuesday 9:07 Tuesday 10:17 Wednesday 11:30 Wednesday 15:54 Tuesday 16:09 Product 5 6 6 7 8 Seru 3 2 3 1 1 Starting time Wednesday 15:59 Wednesday 11:36 Thursday 9:25 Tuesday 16:13 Thursday 8:05 Finishing time Thursday 9:19 Thursday 17:12 Thursday 16:29 Thursday 8:04 Thursday 17:07
Results of the small case
 No. Idle time (min) Makespan (min) CPU time (s) 1 2381.7 1910 8242.5 2 2629.4 1907.8 8193.5 3 2438.6 1932.3 8222.2 4 2446 1936 8228 5 2723.1 1933 8228.6 6 2022.3 1893 8064.8 7 2461.2 1895 8095.2 8 2300 1906.3 8098.5 9 2819 1859.5 8051.9 10 2566.8 1874.1 8135 Average 2478.81 1904.7 8156.02 SD 214.16 24.07 70.94
 No. Idle time (min) Makespan (min) CPU time (s) 1 2381.7 1910 8242.5 2 2629.4 1907.8 8193.5 3 2438.6 1932.3 8222.2 4 2446 1936 8228 5 2723.1 1933 8228.6 6 2022.3 1893 8064.8 7 2461.2 1895 8095.2 8 2300 1906.3 8098.5 9 2819 1859.5 8051.9 10 2566.8 1874.1 8135 Average 2478.81 1904.7 8156.02 SD 214.16 24.07 70.94
Results of GA-GA algorithm for small case
 No. Idle time (min) Makespan (min) CPU time (s) 1 2519.5 1913.8 8220.8 2 nonconvergent 3 2384.4 1851.8 8278.8 4 2375.6 1898.3 8230.3 5 nonconvergent 6 2409.5 1829 8284.8 7 2882 1894.2 9085.2 8 2213.2 1941.3 8244.5 9 2526 1941 8190.9 10 2526.9 1918 8289.3 Average 2479.64 1898.43 8353.08 SD 181.55 37.55 278.59
 No. Idle time (min) Makespan (min) CPU time (s) 1 2519.5 1913.8 8220.8 2 nonconvergent 3 2384.4 1851.8 8278.8 4 2375.6 1898.3 8230.3 5 nonconvergent 6 2409.5 1829 8284.8 7 2882 1894.2 9085.2 8 2213.2 1941.3 8244.5 9 2526 1941 8190.9 10 2526.9 1918 8289.3 Average 2479.64 1898.43 8353.08 SD 181.55 37.55 278.59
Workers' processing time for each product
 Worker Workers' processing time for each product (min) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 22 39 47 29 - 34 64 23 50 71 20 21 11 32 39 15 20 27 29 24 2 23 37 47 29 20 35 54 21 55 77 24 20 12 30 38 19 21 21 26 20 3 22 38 46 - 22 35 50 26 56 77 24 15 11 34 43 - 17 23 29 21 4 - 37 46 32 - 35 56 - 50 78 22 19 12 34 42 17 21 21 25 23 5 23 40 47 27 - 34 59 20 50 81 - 17 10 34 42 15 17 22 28 - 6 22 38 47 29 23 33 61 25 - - 21 20 10 32 39 18 17 27 28 21 7 21 37 - 28 19 32 59 - 52 73 23 21 11 30 35 16 22 22 25 19 8 23 38 49 27 18 - - 22 48 78 21 20 10 31 44 18 - 23 26 22 9 21 40 50 - 21 33 56 26 53 87 - 18 10 32 40 17 22 21 27 20 10 24 - 49 28 19 38 58 26 52 - 24 18 10 37 41 - 17 25 26 23 11 22 38 47 30 18 33 61 27 53 77 21 19 - 33 41 - 19 21 29 23 12 23 36 49 29 21 34 57 22 53 86 21 20 10 33 36 17 21 21 27 24 13 23 39 47 29 22 - 65 21 53 86 22 19 12 30 38 15 19 22 27 21 14 23 39 - 31 18 30 50 29 57 85 24 - 10 37 36 19 21 27 27 21 15 21 36 49 30 - 36 59 24 50 81 24 17 11 37 35 18 19 26 26 22 16 25 36 49 31 19 37 58 22 54 82 24 19 12 39 39 17 18 23 29 22 17 - 37 45 30 22 38 60 23 55 - 21 18 - 37 44 - 21 22 27 - 18 23 37 49 31 21 37 61 - 48 - 21 21 12 34 - 17 17 - 26 20 19 21 35 48 - 19 37 61 28 48 69 20 19 10 33 36 18 22 25 25 20 20 21 38 - 30 23 32 55 29 53 72 22 16 10 - 35 16 17 21 29 23 21 21 36 50 30 22 35 64 29 53 86 22 17 11 39 - 17 18 24 26 23 22 22 38 50 29 - 33 61 22 48 69 23 17 11 40 - 15 - 22 28 21 23 25 39 47 29 19 37 59 26 - - 24 16 12 39 - 17 22 25 25 23 24 20 37 49 29 22 30 62 22 47 71 21 18 12 40 42 19 21 27 25 21 25 23 39 47 30 21 38 63 - 55 - 23 15 11 31 38 19 22 27 27 24 26 - 37 - 32 23 32 58 28 50 72 24 16 11 32 44 17 19 22 25 - 27 24 37 49 30 22 - 56 30 51 78 24 19 11 34 40 - 19 - 29 21 28 24 39 47 - 18 37 - 24 47 85 23 16 10 39 35 17 22 20 26 20 29 25 - 47 29 19 36 54 20 49 79 24 16 11 35 41 18 - 23 25 - 30 20 37 47 28 22 40 51 22 51 78 - 21 11 37 39 16 18 - 25 - 31 23 38 48 29 19 35 53 20 56 72 22 16 11 - 37 16 20 25 25 20 32 23 36 45 29 - 37 63 29 50 79 20 16 11 37 - 18 21 27 29 25 33 23 38 47 30 23 40 59 26 56 78 23 18 11 41 40 - 21 22 - 23 34 21 35 50 27 23 38 65 22 47 71 24 16 10 38 36 16 20 27 27 24 35 20 35 48 32 21 33 61 25 - - 21 21 10 38 - 19 18 24 29 19 36 - 38 45 30 19 31 63 24 56 85 23 - 10 41 37 19 19 24 26 21 37 24 36 - 30 22 38 55 24 50 87 23 19 12 - 39 17 20 26 - 25 38 24 39 49 32 21 37 52 - - 71 24 19 12 35 38 15 19 23 25 22 39 21 39 49 31 19 35 57 29 55 77 21 19 11 40 43 15 19 - 28 19 40 25 35 47 30 20 34 59 25 48 72 23 - 10 41 35 18 20 20 26 18 41 22 36 48 32 20 - 55 25 49 71 23 19 12 31 43 17 19 22 26 24 42 23 39 47 27 19 39 64 24 53 74 24 21 12 32 - 19 18 - 29 22 43 23 36 46 32 20 35 - 21 55 80 21 16 12 32 40 18 20 23 26 22 44 - - 45 31 22 37 52 - 57 72 22 16 11 37 - 18 22 20 27 24 45 20 40 47 29 21 32 52 29 55 82 21 15 10 33 - 16 20 27 - 19 46 20 40 - 30 20 38 58 23 50 82 23 20 11 31 38 19 - - 25 19 47 23 39 49 - 21 39 61 25 - 78 24 19 11 38 39 17 22 27 27 25 48 22 38 49 28 18 33 - 25 49 74 23 18 12 30 43 16 20 21 29 - 49 20 39 47 29 21 - 60 22 52 81 23 21 12 30 40 16 20 24 25 19 50 22 - 47 28 20 32 64 27 49 77 - 18 10 33 37 17 20 20 25 24
 Worker Workers' processing time for each product (min) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 22 39 47 29 - 34 64 23 50 71 20 21 11 32 39 15 20 27 29 24 2 23 37 47 29 20 35 54 21 55 77 24 20 12 30 38 19 21 21 26 20 3 22 38 46 - 22 35 50 26 56 77 24 15 11 34 43 - 17 23 29 21 4 - 37 46 32 - 35 56 - 50 78 22 19 12 34 42 17 21 21 25 23 5 23 40 47 27 - 34 59 20 50 81 - 17 10 34 42 15 17 22 28 - 6 22 38 47 29 23 33 61 25 - - 21 20 10 32 39 18 17 27 28 21 7 21 37 - 28 19 32 59 - 52 73 23 21 11 30 35 16 22 22 25 19 8 23 38 49 27 18 - - 22 48 78 21 20 10 31 44 18 - 23 26 22 9 21 40 50 - 21 33 56 26 53 87 - 18 10 32 40 17 22 21 27 20 10 24 - 49 28 19 38 58 26 52 - 24 18 10 37 41 - 17 25 26 23 11 22 38 47 30 18 33 61 27 53 77 21 19 - 33 41 - 19 21 29 23 12 23 36 49 29 21 34 57 22 53 86 21 20 10 33 36 17 21 21 27 24 13 23 39 47 29 22 - 65 21 53 86 22 19 12 30 38 15 19 22 27 21 14 23 39 - 31 18 30 50 29 57 85 24 - 10 37 36 19 21 27 27 21 15 21 36 49 30 - 36 59 24 50 81 24 17 11 37 35 18 19 26 26 22 16 25 36 49 31 19 37 58 22 54 82 24 19 12 39 39 17 18 23 29 22 17 - 37 45 30 22 38 60 23 55 - 21 18 - 37 44 - 21 22 27 - 18 23 37 49 31 21 37 61 - 48 - 21 21 12 34 - 17 17 - 26 20 19 21 35 48 - 19 37 61 28 48 69 20 19 10 33 36 18 22 25 25 20 20 21 38 - 30 23 32 55 29 53 72 22 16 10 - 35 16 17 21 29 23 21 21 36 50 30 22 35 64 29 53 86 22 17 11 39 - 17 18 24 26 23 22 22 38 50 29 - 33 61 22 48 69 23 17 11 40 - 15 - 22 28 21 23 25 39 47 29 19 37 59 26 - - 24 16 12 39 - 17 22 25 25 23 24 20 37 49 29 22 30 62 22 47 71 21 18 12 40 42 19 21 27 25 21 25 23 39 47 30 21 38 63 - 55 - 23 15 11 31 38 19 22 27 27 24 26 - 37 - 32 23 32 58 28 50 72 24 16 11 32 44 17 19 22 25 - 27 24 37 49 30 22 - 56 30 51 78 24 19 11 34 40 - 19 - 29 21 28 24 39 47 - 18 37 - 24 47 85 23 16 10 39 35 17 22 20 26 20 29 25 - 47 29 19 36 54 20 49 79 24 16 11 35 41 18 - 23 25 - 30 20 37 47 28 22 40 51 22 51 78 - 21 11 37 39 16 18 - 25 - 31 23 38 48 29 19 35 53 20 56 72 22 16 11 - 37 16 20 25 25 20 32 23 36 45 29 - 37 63 29 50 79 20 16 11 37 - 18 21 27 29 25 33 23 38 47 30 23 40 59 26 56 78 23 18 11 41 40 - 21 22 - 23 34 21 35 50 27 23 38 65 22 47 71 24 16 10 38 36 16 20 27 27 24 35 20 35 48 32 21 33 61 25 - - 21 21 10 38 - 19 18 24 29 19 36 - 38 45 30 19 31 63 24 56 85 23 - 10 41 37 19 19 24 26 21 37 24 36 - 30 22 38 55 24 50 87 23 19 12 - 39 17 20 26 - 25 38 24 39 49 32 21 37 52 - - 71 24 19 12 35 38 15 19 23 25 22 39 21 39 49 31 19 35 57 29 55 77 21 19 11 40 43 15 19 - 28 19 40 25 35 47 30 20 34 59 25 48 72 23 - 10 41 35 18 20 20 26 18 41 22 36 48 32 20 - 55 25 49 71 23 19 12 31 43 17 19 22 26 24 42 23 39 47 27 19 39 64 24 53 74 24 21 12 32 - 19 18 - 29 22 43 23 36 46 32 20 35 - 21 55 80 21 16 12 32 40 18 20 23 26 22 44 - - 45 31 22 37 52 - 57 72 22 16 11 37 - 18 22 20 27 24 45 20 40 47 29 21 32 52 29 55 82 21 15 10 33 - 16 20 27 - 19 46 20 40 - 30 20 38 58 23 50 82 23 20 11 31 38 19 - - 25 19 47 23 39 49 - 21 39 61 25 - 78 24 19 11 38 39 17 22 27 27 25 48 22 38 49 28 18 33 - 25 49 74 23 18 12 30 43 16 20 21 29 - 49 20 39 47 29 21 - 60 22 52 81 23 21 12 30 40 16 20 24 25 19 50 22 - 47 28 20 32 64 27 49 77 - 18 10 33 37 17 20 20 25 24
Setup time and demand of products
 Product 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Setup time (min) 4 9 8 6 5 6 4 1 10 12 24 2 5 7 11 3 15 4 2 7 Demand 145 107 134 105 140 145 115 87 145 126 125 150 118 106 75 80 132 83 65 89
 Product 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Setup time (min) 4 9 8 6 5 6 4 1 10 12 24 2 5 7 11 3 15 4 2 7 Demand 145 107 134 105 140 145 115 87 145 126 125 150 118 106 75 80 132 83 65 89
Results of large case
 No. Idle time (min) Makespan (min) CPU time (s) 1 5587.3 1932 16236 2 5457.4 1848.30 16376 3 5164.9 1865.4 16221 4 5258.9 1919 15754 5 5757.2 1806 15743 Average 5445.14 1874.14 16066 SD 214.92 46.36 264.84
 No. Idle time (min) Makespan (min) CPU time (s) 1 5587.3 1932 16236 2 5457.4 1848.30 16376 3 5164.9 1865.4 16221 4 5258.9 1919 15754 5 5757.2 1806 15743 Average 5445.14 1874.14 16066 SD 214.92 46.36 264.84
 [1] David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002 [2] V. Kumar Murty, Ying Zong. Splitting of abelian varieties. Advances in Mathematics of Communications, 2014, 8 (4) : 511-519. doi: 10.3934/amc.2014.8.511 [3] J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008 [4] Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023 [5] Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002 [6] Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 [7] Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781 [8] Rabiaa Ouahabi, Nasr-Eddine Hamri. Design of new scheme adaptive generalized hybrid projective synchronization for two different chaotic systems with uncertain parameters. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2361-2370. doi: 10.3934/dcdsb.2020182

2019 Impact Factor: 1.366