Introduction
Literature review
Parallel machine scheduling problems with step-deteriorating jobs
Energy-efficient parallel machine scheduling problems
Problem description and formulation
Problem description
Mathematical formulation
Indices | |
i, j | Indexes of jobs, \(i,j \in N\) |
k | Index of a machine, \(k \in M\) |
Parameters | |
N | Set of all jobs |
M | Set of all machines |
\(a_j\) | Base processing time of job j |
\(h_j\) | Deteriorating threshold of job j |
\(b_j\) | Extra penalty processing time of job j |
\(d_{j}\) | Due date of job j |
\(e_0\) | Energy consumption (per time unit) of the holding equipment for a job |
\(q_{j}\) | Energy consumption (per time unit) when reheating job j |
\(\alpha _{j}\) | Tardiness penalty cost for job j |
\(\beta \) | unit energy cost, such as hourly electricity price |
\(\varDelta \) | Large positive number |
\(\epsilon \) | Very small positive number |
Decision variables | |
\(x_{ij}\) | Equals to 1 if and only if job i is completed before job j starts, and to 0 otherwise |
\(y_{jk}\) | Equals to 1 if and only if job j is processed on machine k |
\(z_{j}\) | Equals to 1 if and only if job j is started no later than its deteriorating threshold, and to 0 otherwise. |
When \(z_j=1\), \(b_j=u_j=0\). | |
\(u_{j}\) | Equals to 1 if and only if the status of job j is maintained by a holding equipment, and to 0 otherwise. |
When \(u_j=1\), \(z_j=b_j=0\). | |
Dependent variables | |
\(p_j\) | Actual processing time of job j. In our models, it can be replaced by \(a_j+b_j\times (1-u_j-z_j)\). |
\(e_j\) | Extra energy consumed by job j during the waiting phase in a holding machine |
\(E_j\) | Total extra energy consumption for completing job j |
\(T_j\) | Tardiness of job j |
\(s_{j}\) | Starting time of job j |
Example of a schedule
Job(j) | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
Base processing time \(a_j\) | 9 | 10 | 8 | 7 | 15 |
Deteriorating threshold \(h_j\) | 6 | 5 | 8 | 9 | 10 |
Penalty time \(b_j\) | 3 | 5 | 8 | 7 | 1 |
Due date \(d_j\) | 11 | 13 | 15 | 14 | 20 |
unit processing energy consumption \(q_j\) | 2 | 2 | 3 | 4 | 2 |
tardiness penalty cost \(\alpha _j\) | 1 | 2 | 2.5 | 2 | 0.5 |
Logic-based Benders decomposition approach
The master problem
Sub-problems
Mixed integer programming model
Tabu search
Benders cut
Instance | MIP | LBBD-MIP-OC | LBBD-MIP-GC | LBBD-TS-OC | LBBD-TS-GC | |
---|---|---|---|---|---|---|
Size | Group | |||||
8\(\times \)2 | 1 | 0/5/0.90 | 0/5/3.74 | 0/5/1.83 | 0/5/0.12 | 0/5/0.05 |
2 | 0/5/0.45 | 0/5/3.72 | 0/5/2.09 | 0/5/0.11 | 0/5/0.06 | |
3 | 0/5/0.47 | 0/5/4.24 | 0.22/4/2.54 | 1.25/2/0.10 | 1.47/1/0.06 | |
4 | 0/5/0.30 | 0/5/3.43 | 0/5/1.89 | 0/5/0.09 | 0/5/0.06 | |
5 | 0/5/0.42 | 0/5/3.66 | 0.14/4/2.34 | 1.60/2/0.11 | 1.72/2/0.05 | |
6 | 0/5/0.54 | 0/5/5.54 | 0.64/4/3.61 | 8.55/2/0.11 | 9.37/2/0.05 | |
7 | 0/5/0.24 | 0/5/3.67 | 0/5/2.75 | 12.07/4/0.08 | 12.07/4/0.06 | |
8 | 0/5/0.47 | 0/5/4.76 | 0.45/4/3.03 | 0.26/4/0.10 | 0.71/3/0.06 | |
9 | 0/5/0.32 | 0/5/3.80 | 0/5/2.74 | 0/5/0.09 | 0/5/0.05 | |
10 | 0/5/0.40 | 0/5/2.94 | 0/5/2.49 | 6.73/4/0.08 | 6.73/4/0.05 | |
8\(\times \)3 | 1 | 0/5/0.26 | 0/5/11.64 | 0.02/4/1.20 | 0/5/1.32 | 0.02/4/0.10 |
2 | 0/5/0.25 | 0/5/9.39 | 4.57/3/1.47 | 0/5/0.53 | 4.57/3/0.10 | |
3 | 0/5/0.09 | 0/5/3.02 | 0.88/4/1.48 | 0/5/0.25 | 0.88/4/0.09 | |
4 | 0/5/0.06 | 0/5/1.28 | 0/5/1.58 | 0/5/0.10 | 0/5/0.11 | |
5 | 0/5/0.41 | 0/5/12.23 | 3.51/1/2.33 | 3.81/4/0.57 | 7.01/1/0.12 | |
6 | 0/5/0.15 | 0/5/3.99 | 5.14/3/1.83 | 0/5/0.26 | 3.65/3/0.12 | |
7 | 0/5/0.05 | 0/5/1.07 | 0/5/1.19 | 0/5/0.09 | 0/5/0.08 | |
8 | 0/5/0.09 | 0/5/2.29 | 0/5/1.26 | 13.96/4/0.16 | 13.96/4/0.09 | |
9 | 0/5/0.10 | 0/5/2.53 | 0/5/1.29 | 0/5/0.19 | 0/5/0.09 | |
10 | 0/5/0.05 | 0/5/1.11 | 0/5/1.56 | 0/5/0.08 | 0/5/0.08 | |
Avg/Sum/Avg | 0/100/0.30 | 0/100/4.40 | 0.78/86/2.02 | 2.41/86/0.23 | 3.11/75/0.08 |
Instance | MIP | LBBD-MIP-OC | LBBD-MIP-GC | LBBD-TS-OC | LBBD-TS-GC | |||
---|---|---|---|---|---|---|---|---|
Size | Group | Index | Optimal | Gap (%) | Gap (%) | Gap (%) | Gap (%) | Gap (%) |
8\(\times \)2 | 3 | 1 | 239.18 | 0 | 0 | 1.10 | 0 | 1.10 |
3 | 2 | 219.52 | 0 | 0 | 0 | 3.38 | 3.38 | |
3 | 3 | 22.9 | 0 | 0 | 0 | 2.27 | 2.27 | |
3 | 4 | 160.51 | 0 | 0 | 0 | 0.60 | 0.60 | |
5 | 1 | 369.68 | 0 | 0 | 0 | 1.54 | 1.54 | |
5 | 3 | 35.58 | 0 | 0 | 0 | 4.83 | 4.83 | |
5 | 5 | 113.58 | 0 | 0 | 0.70 | 1.64 | 2.23 | |
6 | 3 | 228.58 | 0 | 0 | 0 | 3.85 | 3.85 | |
6 | 4 | 25.3 | 0 | 0 | 0 | 37.67 | 37.67 | |
6 | 5 | 133.24 | 0 | 0 | 3.22 | 1.22 | 5.34 | |
7 | 4 | 2.37 | 0 | 0 | 0 | 60.34 | 60.34 | |
8 | 1 | 251.54 | 0 | 0 | 0 | 1.29 | 1.29 | |
8 | 3 | 23.49 | 0 | 0 | 2.26 | 0 | 2.26 | |
10 | 1 | 74.38 | 0 | 0 | 0 | 33.66 | 33.66 | |
8\(\times \)3 | 1 | 5 | 324.8 | 0 | 0 | 0.11 | 0 | 0.11 |
2 | 2 | 96.2 | 0 | 0 | 22.22 | 0 | 22.22 | |
2 | 3 | 368.47 | 0 | 0 | 0.65 | 0 | 0.65 | |
3 | 3 | 38.04 | 0 | 0 | 4.42 | 0 | 4.42 | |
5 | 1 | 107.81 | 0 | 0 | 1.96 | 0 | 0.97 | |
5 | 2 | 100.5 | 0 | 0 | 3.84 | 0 | 3.84 | |
5 | 3 | 125.7 | 0 | 0 | 3.20 | 0 | 3.20 | |
5 | 5 | 30.99 | 0 | 0 | 8.55 | 19.04 | 27.04 | |
6 | 4 | 37.83 | 0 | 0 | 9.99 | 0 | 9.99 | |
6 | 5 | 91.36 | 0 | 0 | 15.70 | 0 | 8.27 | |
8 | 1 | 3.84 | 0 | 0 | 0 | 69.79 | 69.79 | |
Average | – | 0.00 | 0.00 | 3.12 | 9.64 | 12.43 |
Instance | MIP | LBBD-MIP-OC | LBBD-MIP-GC | LBBD-TS-OC | LBBD-TS-GC | |
---|---|---|---|---|---|---|
Size | Group | |||||
40\(\times \)2 | 1 | 3.68/0 | 0.58/1 | 0.40/2 | 0.34/2 | 0.73/0 |
2 | 7.57/0 | 0.62/0 | 0.54/1 | 0.41/2 | 0.38/2 | |
3 | 30.10/0 | 1.35/0 | 1.59/2 | 0.42/3 | 2.35/0 | |
4 | 49.03/0 | 2.91/1 | 4.19/0 | 0.60/3 | 1.72/1 | |
5 | 9.85/0 | 0.43/2 | 0.62/2 | 0.77/1 | 0.89/1 | |
6 | 27.86/0 | 3.13/0 | 2.22/0 | 0.33/4 | 1.78/1 | |
7 | 77.58/0 | 10.41/0 | 4.37/1 | 0.58/3 | 3.57/1 | |
8 | 28.19/0 | 1.68/1 | 1.24/1 | 0.10/3 | 0.74/1 | |
9 | 118.10/0 | 22.74/0 | 21.88/0 | 1.55/3 | 5.96/2 | |
10 | 106.03/0 | 28.24/0 | 27.76/0 | 1.25/2 | 1.30/3 | |
40\(\times \)6 | 1 | 1.02/1 | 3.12/0 | 0.97/2 | 3.36/0 | 0.24/2 |
2 | 1.02/4 | 12.42/0 | 6.52/0 | 8.56/0 | 1.97/1 | |
3 | 4.52/3 | 28.97/0 | 17.24/1 | 18.71/0 | 5.83/1 | |
4 | 21.01/2 | 103.02/0 | 61.81/0 | 74.87/0 | 2.49/3 | |
5 | 3.96/0 | 7.55/0 | 5.28/0 | 4.55/0 | 0/5 | |
6 | 7.01/1 | 24.30/0 | 10.57/0 | 14.16/0 | 1.26/4 | |
7 | 103.37/1 | 514.27/0 | 224.16/0 | 245.52/0 | 3.17/4 | |
8 | 4.54/3 | 33.98/0 | 19.15/0 | 12.57/0 | 3.10/2 | |
9 | 12.49/2 | 1352.76/0 | 36.02/0 | 57.57/1 | 4.04/2 | |
10 | 134.63/0 | 6666.04/0 | 1096.58/0 | 43.75/1 | 0.94/4 | |
Avg/Sum | 37.58/17 | 441/5 | 77.15/12 | 24.50/28 | 2.12/40 |
Initial solution for LBBD
Computational study
Instance generation
Computational results
Small-sized instances
Medium-sized instances
Large-sized instances
Instance | MIP | LBBD-TS-OC | LBBD-TS-GC | |
---|---|---|---|---|
Size | Group | |||
100\(\times \)2 | 1 | 79.59/0 | 0.07/1 | 0.00/4 |
2 | 94.29/0 | 0.23/2 | 0.18/4 | |
3 | 177.74/0 | 0.75/3 | 0.31/2 | |
4 | 434.46/0 | 0.35/4 | 2.29/1 | |
5 | 107.48/0 | 0.14/3 | 0.25/2 | |
6 | 189.22/0 | 0/5 | 0.16/2 | |
7 | 780.72/0 | 1.28/3 | 1.72/2 | |
8 | 270.58/0 | 0.41/1 | 0.26/4 | |
9 | 765.92/0 | 0.37/4 | 1.89/1 | |
10 | 573.69/0 | 0.18/3 | 0.32/2 | |
100\(\times \)8 | 1 | 23.68/0 | 0.61/1 | 0.29/4 |
2 | 47.17/0 | 0.77/4 | 0.40/1 | |
3 | 59.82/0 | 2.47/1 | 0.27/4 | |
4 | 92.62/0 | 2.50/2 | 0.61/4 | |
5 | 70.73/0 | 1.37/2 | 0.25/3 | |
6 | 94.91/0 | 4.93/2 | 0/5 | |
7 | 179.10/0 | 8.62/1 | 0.96/4 | |
8 | 135.73/0 | 4.44/1 | 1.45/4 | |
9 | 604.75/0 | 36.58/1 | 4.14/4 | |
10 | 231.82/0 | 29.75/1 | 0.55/4 | |
Avg/Sum | 250.70/0 | 5.00/45 | 0.81/61 |
Instance | F(T) | F(E) | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Size | Group | 0.001 | 0.005 | 0.01 | 0.04 | 0.08 | 0.2 | 0.001 | 0.005 | 0.01 | 0.04 | 0.08 | 0.2 |
40\(\times \)2 | 1 | 14892.5 | 15088.9 | 15222.2 | 15361 | 15335.4 | 15354.2 | 33.257 | 50.23 | 43.52 | 5.92 | 9.76 | 24.4 |
2 | 20711.6 | 21182.1 | 21446.3 | 21312.8 | 21499.6 | 21594.4 | 41.833 | 53.12 | 3.09 | 22.44 | 10.72 | 32 | |
3 | 5273.67 | 5670.05 | 5758.39 | 5784.86 | 5820.88 | 5837.68 | 64.125 | 30.255 | 7.7 | 10.72 | 19.68 | 49.2 | |
4 | 2962.93 | 3306.39 | 3205.01 | 3228.71 | 3315.99 | 3161.33 | 34.6 | 0.79 | 18.63 | 6.72 | 14.08 | 37 | |
5 | 13847.2 | 14246.2 | 14562.9 | 14486.7 | 14486.4 | 14437.7 | 76.248 | 24.075 | 2.88 | 10.56 | 22.8 | 54.4 | |
6 | 5662.6 | 5718.17 | 5730.03 | 5807.06 | 5867.53 | 5805.63 | 15.4 | 21.26 | 25.43 | 3.88 | 7.12 | 17.8 | |
7 | 2527.11 | 2987.9 | 3062.28 | 3244.08 | 3035.99 | 2978.19 | 57.524 | 26.015 | 2.81 | 11.88 | 21.36 | 57.4 | |
8 | 3224.68 | 3259.51 | 3292.75 | 3368.29 | 3423.68 | 3415.45 | 14.485 | 9.995 | 15.23 | 3.68 | 9.6 | 21.2 | |
9 | 1948.14 | 2095.86 | 2095.86 | 2080.88 | 2063.62 | 2081.37 | 32.873 | 8.455 | 16.91 | 11.24 | 10.48 | 29.6 | |
10 | 956.47 | 956.12 | 975.12 | 941.26 | 958.95 | 964.34 | 14.736 | 0.905 | 2.09 | 6.92 | 13.84 | 36.2 | |
40\(\times \)6 | 1 | 4701.98 | 4686.7 | 4738.05 | 4939.58 | 4903.61 | 4883.23 | 21.682 | 37.535 | 55.98 | 5.84 | 14.56 | 24 |
2 | 3306.93 | 3454.96 | 3335.3 | 3436.93 | 3437.58 | 3420.49 | 30.491 | 23.39 | 3.99 | 8.52 | 15.36 | 45.6 | |
3 | 602.72 | 735.6 | 724.11 | 698.8 | 776.14 | 686.76 | 11.78 | 29.15 | 27.39 | 15.04 | 10.88 | 26.4 | |
4 | 263.7 | 476.25 | 331.6 | 393.16 | 433.26 | 454.2 | 18.551 | 17.08 | 18.02 | 11.48 | 36.88 | 52.6 | |
5 | 1867.11 | 1827.69 | 1853.64 | 1877.3 | 1911.97 | 1941.99 | 16.423 | 27.675 | 27.73 | 5.6 | 13.84 | 24 | |
6 | 945.27 | 1084.79 | 1050.23 | 1097.26 | 1090.28 | 1183.93 | 34.262 | 18.98 | 32.41 | 8.44 | 16.08 | 38.6 | |
7 | 0 | 0 | 2.64 | 0 | 3.89 | 0 | 0.105 | 1.615 | 5.14 | 4.48 | 10.08 | 20.2 | |
8 | 911.41 | 860.06 | 951.65 | 989.7 | 906.41 | 966.45 | 22.436 | 15.375 | 0.53 | 2.76 | 5.04 | 15.8 | |
9 | 75.76 | 72.79 | 79.17 | 60.78 | 65.73 | 78.57 | 7.043 | 0.275 | 0.61 | 2.44 | 5.36 | 10.8 | |
10 | 0 | 0 | 0 | 0 | 0 | 0 | 0.069 | 0.255 | 0.51 | 2.24 | 4.72 | 12.4 |