1 Introduction
2 Balancing of assembly lines with collaborative robots
2.1 Problem setting
2.2 Illustrative example
3 Review of relevant research
4 Model formulation
Sets and parameters | |
---|---|
\(I\) | Set of tasks \(I = \left\{ {i,j = 1, \ldots ,n} \right\}\) |
\(K\) | Set of stations \(K = \left\{ {k = 1, \ldots ,m} \right\}\) |
\(P\) | Set of process alternatives \(P = \left\{ {p = p_{\text{H}} ,p_{\text{R}} ,p_{\text{C}} } \right\}\), in which tasks are processed by human (\(p_{\text{H}}\)), robot (\(p_{\text{R}}\)) or in collaboration (\(p_{\text{C}}\)), respectively |
\(E\) | Set of direct precedence relations (\(i,j\)) |
\(t_{ip}\) | Execution time of task \(i \in I\) with processing alternative \(p \in P\) |
\(\bar{c}\) | Upper bound on cycle time \(\bar{c} = \hbox{max} \left\{ {t_{\hbox{max} } ,2 \cdot \lfloor t_{\text{sum}} /m\rfloor } \right\}\), where \(t_{\hbox{max} } = \hbox{max} \{ t_{ip} |i \in I, p \in P\}\) and \(t_{\text{sum}} = \mathop \sum \limits_{i \in I} \hbox{max} \{ t_{ip} |p \in P\}\) |
\(q\) | Maximum number of robots to be allocated |
Decision and auxiliary variables | |
---|---|
\(x_{ikp}\) | Binary variable with value 1, if task \(i \in I\) is assigned to station \(k \in K\) with processing alternative \(p \in P\) |
\(z_{i}\) | Continuous variable for encoding the station number a task \(i \in I\) is assigned to |
\(s_{i}\) | Continuous variable for encoding the start time of task \(i \in I\) in the station it is assigned to |
\(r_{k}\) | Binary variable with value 1, if a robot is assigned to station \(k \in K\) |
\(c\) | Non-negative variable for encoding the cycle time |
\(y_{ij}\) | Binary variable with value 1, if task \(i \in I\) starts before task \(j \in I\) (\(s_{i} \le s_{j} )\) |
5 Hybrid genetic algorithm with MIP-based scheduling
5.1 Overview
5.2 Encoding
5.3 Initial population (Step 1)
5.4 Fitness estimation and improvement procedures (Steps 2 and 5)
5.5 Fitness evaluation (Steps 3 and 6)
5.6 Selection, crossover, and mutation procedures (Step 4)
5.7 Replacement procedure (Step 7)
6 Computational experiments
6.1 Instance generation
Scenario | RF | CF | Small instances (\(n = 20\,{\text{tasks}}\)) | Medium instances (\(n = 50\,{\text{tasks}}\)) | Large instances (\(n = 100\,{\text{tasks}}\)) | |||
---|---|---|---|---|---|---|---|---|
Stations | Robots | Stations | Robots | Stations | Robots | |||
1 | – | – | 5 | 0 | 13 | 0 | 25 | 0 |
2 | 0.2 | 0.2 | 5 | 1 | 13 | 3 | 25 | 5 |
3 | 0.4 | 0.4 | 5 | 1 | 13 | 3 | 25 | 5 |
4 | 0.2 | 0.2 | 5 | 2 | 13 | 5 | 25 | 10 |
5 | 0.4 | 0.4 | 5 | 2 | 13 | 5 | 25 | 10 |
6 | – | – | 10 | 0 | 25 | 0 | 50 | 0 |
7 | 0.2 | 0.2 | 10 | 2 | 25 | 5 | 50 | 10 |
8 | 0.4 | 0.4 | 10 | 2 | 25 | 5 | 50 | 10 |
9 | 0.2 | 0.2 | 10 | 4 | 25 | 10 | 50 | 20 |
10 | 0.4 | 0.4 | 10 | 4 | 25 | 10 | 50 | 20 |
6.2 Analysis of MIP results
F-ratio | Small instances (\(n = 20\,{\text{tasks}}\)) | Medium instances (\(n = 50\,{\text{tasks}}\)) | Large instances (\(n = 100\,{\text{tasks}}\)) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Feasible (optimal) (# of 200) | Gap \(\emptyset \left( \sigma \right)\) | CPU 1st \(\emptyset \left( \sigma \right)\) (s) | CPU \(\emptyset \left( \sigma \right)\) (s) | Feasible (optimal) (# of 200) | Gap \(\emptyset \left( \sigma \right)\) | CPU 1st \(\emptyset \left( \sigma \right)\) (s) | CPU \(\emptyset \left( \sigma \right)\) (s) | Feasible (optimal) (# of 200) | Gap \(\emptyset \left( \sigma \right)\) | CPU 1st \(\emptyset \left( \sigma \right)\) (s) | CPU \(\emptyset \left( \sigma \right)\) (s) | |
0.2 | 200 (200) | 0 (0) | 3 (1) | 40 (106) | 200 (59) | 0.18 (0.15) | 265 (112) | 5337 (2913) | 106 (7) | 0.4 (0.22) | 8695 (9747) | 28,786 (147) |
0.8 | 200 (53) | 0.17 (0.15) | 2 (1) | 5320 (3118) | 200 (60) | 0.25 (0.21) | 106 (69) | 5085 (3232) | 98 (8) | 0.35 (0.17) | 4216 (5467) | 28,073 (2826) |
West ratio | Small instances (\(n = 20\,{\text{tasks}}\)) | Medium instances (\(n = 50\,{\text{tasks}}\)) | Large instances (\(n = 100\,{\text{tasks}}\)) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Feasible (optimal) (# of 200) | Gap \(\emptyset \left( \sigma \right)\) | CPU 1st \(\emptyset \left( \sigma \right)\) (s) | CPU \(\emptyset \left( \sigma \right)\) (s) | Feasible (optimal) (# of 200) | Gap \(\emptyset \left( \sigma \right)\) | CPU 1st \(\emptyset \left( \sigma \right)\) (s) | CPU \(\emptyset \left( \sigma \right)\) (s) | Feasible (optimal) (# of 200) | Gap \(\emptyset \left( \sigma \right)\) | CPU 1st \(\emptyset \left( \sigma \right)\) (s) | CPU \(\emptyset \left( \sigma \right)\) (s) | |
2 | 200 (154) | 0.04 (0.10) | 3 (1) | 1747 (3031) | 200 (116) | 0.09 (0.12) | 239 (145) | 3287 (3346) | 29 (15) | 0.31 (0.42) | 24,032 (6547) | 26,290 (4749) |
4 | 200 (99) | 0.12 (0.16) | 2 (0) | 3613 (3570) | 200 (3) | 0.35 (0.15) | 132 (55) | 7134 (602) | 175 (0) | 0.39 (0.13) | 3645 (3733) | 28,800 (0) |
6.3 Parameters and convergence of the hybrid genetic algorithm
Parameter | Value |
---|---|
Population size small/medium/large instances | 100/225/400 |
Workload distribution factor | 0.15 |
Iterations of improvement procedure per individual | 3 |
Robot mutation probability | 0.1 |
Offspring mutation probability | 1.0 |
Number of swaps during offspring mutation | 3 |
6.4 Computational results
Small instances (\(n = 20\,{\text{tasks}}\)) | Medium instances (\(n = 50\,{\text{tasks}}\)) | Large instances (\(n = 100\,{\text{tasks}}\)) | |||||||
---|---|---|---|---|---|---|---|---|---|
GA | Tie | MIP | GA | Tie | MIP | GA | Tie | MIP | |
# (of 400) | 21 | 265 | 114 | 140 | 138 | 122 | 348 | 22 | 30 |
\(\emptyset \left(\varvec{\sigma}\right)\) CPU GA (s) | 114 (45) | 99 (46) | 114 (48) | 666 (264) | 588 (612) | 786 (366) | 2994 (1413) | 2720 (992) | 2734 (1185) |
\(\emptyset \left(\varvec{\sigma}\right)\) CPU MIP (s) | 7200 (0) | 1349 (2762) | 4941 (3311) | 7200 (0) | 1640 (2625) | 6967 (1142) | 28,800 (0) | 25,491 (5327) | 28,800 (0) |
6.5 Managerial insights
RD | West ratio | F-ratio | ||
---|---|---|---|---|
2 | 4 | 0.2 | 0.8 | |
0.0 | 0.00 (0.00) | 0.00 (0.00) | 0.00 (0.00) | 0.00 (0.00) |
0.2 | 0.03 (0.04) | 0.07 (0.01) | 0.05 (0.04) | 0.05 (0.04) |
0.4 | 0.03 (0.05) | 0.12 (0.02) | 0.07 (0.05) | 0.08 (0.06) |
RF, CF | West ratio | F-ratio | ||
---|---|---|---|---|
2 | 4 | 0.2 | 0.8 | |
0.0 | 0.00 (0.00) | 0.00 (0.00) | 0.00 (0.00) | 0.00 (0.00) |
0.2 | 0.02 (0.03) | 0.09 (0.03) | 0.05 (0.04) | 0.06 (0.05) |
0.4 | 0.04 (0.06) | 0.10 (0.03) | 0.07 (0.05) | 0.07 (0.06) |