• Previous Article
    Performance analysis of an infinite-buffer batch-size-dependent bulk service queue with server breakdown and multiple vacation
  • JIMO Home
  • This Issue
  • Next Article
    Equity-based incentive to coordinate shareholder-manager interests under information asymmetry
doi: 10.3934/jimo.2021151
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Lagrangian relaxation algorithm for the truck scheduling problem with products time window constraint in multi-door cross-dock

Institute of Industrial Engineering, School of Mechanical Engineering, Tongji University, Shanghai 201804, China

* Corresponding author: Binghai Zhou

Received  December 2020 Revised  June 2021 Early access September 2021

Cross-docking is a kind of process that products are unloaded in front of the inbound doors, consolidated based on the downstream demand, and then directly transferred to the outbound doors without a long storage process during the transportation. In this paper, a multi-door cross-dock truck scheduling problem is investigated in which the scheduling and sequencing assignment of trucks need to be considered, with the objectives of minimizing the inner transportation cost in the cross-dock and the total truck waiting cost. The major contribution of this paper is that a novel product-related time window constraint and the temporary storage area are firstly introduced to adapt to different physical conditions of goods considering real-world requirements. Then, a Lagrangian relaxation algorithm is proposed which aims to decompose the relaxed problem into several easy-to-be-solved sub-problems. Besides, a subgradient algorithm is used at each iteration to further deal with these sub-problems. Finally, theory analysis and simulation experiments of different problem scales are carried out during the comparison with a Greedy algorithm to evaluate the performance of the proposed algorithm. Results indicate that the Lagrangian relaxation algorithm is able to achieve more satisfactory near-optimal solutions within an acceptable time.

Citation: Binghai Zhou, Yuanrui Lei, Shi Zong. Lagrangian relaxation algorithm for the truck scheduling problem with products time window constraint in multi-door cross-dock. Journal of Industrial and Management Optimization, doi: 10.3934/jimo.2021151
References:
[1]

A. Amini and R. Tavakkoli-Moghaddam, A bi-objective truck scheduling problem in a cross-docking center with probability of breakdown for trucks, Computers & Industrial Engineering, 96 (2016), 180-191.  doi: 10.1016/j.cie.2016.03.023.

[2]

H. ArbabiM. M. Nasiri and A. Bozorgi-Amiri, A hub-and-spoke architecture for a parcel delivery system using the cross-docking distribution strategy, Eng. Optim., 53 (2021), 1593-1612.  doi: 10.1080/0305215X.2020.1808973.

[3]

M. T. Assadi and M. Bagheri, Differential evolution and Population-based simulated annealing for truck scheduling problem in multiple door cross-docking systems, Computers & Industrial Engineering, 96 (2016), 149-161.  doi: 10.1016/j.cie.2016.03.021.

[4]

P. BodnarR. de Koster and K. Azadeh, Scheduling trucks in a cross-dock with mixed service mode dock doors, Transportation Science, 51 (2017), 112-131.  doi: 10.1287/trsc.2015.0612.

[5]

N. Boysen and M. Fliedner, Cross dock scheduling: Classification, literature review and research agenda, Omega, 38 (2010), 413-422.  doi: 10.1016/j.omega.2009.10.008.

[6]

A. ChiarelloM. Gaudioso and M. Sammarra, Truck synchronization at single door cross-docking terminals, OR Spectrum, 40 (2018), 395-447.  doi: 10.1007/s00291-018-0510-x.

[7]

H. ChenC. Chu and J. M. Proth, An improvement of the Lagrangean relaxation approach for job shop scheduling: A dynamic programming method, IEEE Transactions on Robotics and Atomation, 14 (1998), 786-795.  doi: 10.1109/70.720354.

[8]

J. Chen, K. Wang and Y. Huang, An integrated inbound logistics mode with intelligent scheduling of milk-run collection, drop and pull delivery and LNG vehicles, Journal of Intelligent Manufacturing, (2020), 1–9. doi: 10.1007/s10845-020-01637-3.

[9]

L. ChenY. Liu and A. Langevin, A multi-compartment vehicle routing problem in cold-chain distribution, Comput. Oper. Res., 111 (2019), 58-66.  doi: 10.1016/j.cor.2019.06.001.

[10]

U. ClausenD. DiekmannM. Pöting and C. Schumacher, Operating parcel transshipment terminals: A combined simulation and optimization approach, Journal of Simulation, 11 (2017), 2-10.  doi: 10.1057/s41273-016-0032-y.

[11]

H. CorstenF. Becker and H. Salewski, Integrating truck and workforce scheduling in a cross-dock: Analysis of different workforce coordination policies, Journal of Business Economics, 90 (2020), 207-237. 

[12]

C. DongQ. LiB. Shen and X. Tong, Sustainability in supply chains with behavioral concerns, Sustainability, 11 (2019), 4051.  doi: 10.3390/su11154051.

[13]

G. B. FonsecaT. H. Nogueira and M. G. Ravetti, A hybrid Lagrangian metaheuristic for the cross-docking flow shop scheduling problem, European J. Oper. Res., 275 (2019), 139-154.  doi: 10.1016/j.ejor.2018.11.033.

[14]

T. Garai and H. Garg, Multi-objective linear fractional inventory model with possibility and necessity constraints under generalised intuitionistic fuzzy set environment, CAAI Transactions on Intelligence Technology, 4 (2019), 175-181. 

[15]

M. GaudiosoM. F. Monaco and M. Sammarra, A Lagrangian heuristics for the truck scheduling problem in multi-door, multi-product Cross-Docking with constant processing time, Omega, 101 (2021), 102255.  doi: 10.1016/j.omega.2020.102255.

[16]

A. Golshahi-RoudbanehM. Hajiaghaei-Keshteli and M. M. Paydar, Developing a lower bound and strong heuristics for a truck scheduling problem in a cross-docking center, Knowledge-Based Systems, 129 (2017), 17-38.  doi: 10.1016/j.knosys.2017.05.006.

[17]

O. Guemri, P. Nduwayo, R. Todosijević, S. Hanafi and F. Glover, Probabilistic tabu search for the cross-docking assignment problem, European J. Oper. Res., 277 (2019), 875–885., doi: 10.1016/j.ejor.2019.03.030.

[18]

A. Gunawan, A. T. Widjaja, P. Vansteenwegen and V. F. Yu, A matheuristic algorithm for solving the vehicle routing problem with cross-docking, International Conference on Learning and Intelligent Optimization Springer, (2020), 9–15. doi: 10.1007/978-3-030-53552-0_2.

[19]

A. GutierrezL. DieulleN. Labadie and N. Velasco, A hybrid metaheuristic algorithm for the vehicle routing problem with stochastic demands, Comput. Oper. Res., 99 (2018), 135-147.  doi: 10.1016/j.cor.2018.06.012.

[20]

A. L. Ladier and G. Alpan, Robust cross-dock scheduling with time windows, Computers & Industrial Engineering, 99 (2016), 16-28.  doi: 10.1016/j.cie.2016.07.003.

[21]

A. L. Ladier and G. Alpan, Crossdock truck scheduling with time windows: Earliness, tardiness and storage policies, J. Intell. Manufacturing, 29 (2018), 569-583. 

[22]

S. M. Mousavi and B. Vahdani, Cross-docking location selection in distribution systems: A new intuitionistic fuzzy hierarchical decision model, International J. Computational Intelligence Systems, 9 (2016), 91-109.  doi: 10.1080/18756891.2016.1144156.

[23]

W. NassiefI. Contreras and R. As'ad, A mixed-integer programming formulation and Lagrangean relaxation for the cross-dock door assignment problem, International Journal of Production Research, 54 (2016), 494-508.  doi: 10.1080/00207543.2014.1003664.

[24]

W. Nassief, I. Contreras and B. Jaumard, A comparison of formulations and relaxations for cross-dock door assignment problems, Comput. Oper. Res., 94 (2018), 76–88., doi: 10.1016/j.cor.2018.01.022.

[25]

S. NiroomandH. Garg and A. Mahmoodirad, An intuitionistic fuzzy two stage supply chain network design problem with multi-mode demand and multi-mode transportation, ISA transactions, 107 (2020), 117-133.  doi: 10.1016/j.isatra.2020.07.033.

[26]

C. SerranoX. Delorme and A. Dolgui, Scheduling of truck arrivals, truck departures and shop-floor operation in a cross-dock platform, based on trucks loading plans, International Journal of Production Economics, 194 (2017), 102-112.  doi: 10.1016/j.ijpe.2017.09.008.

[27]

I. SeyediM. Hamedi and R. Tavakkoli-Moghaddam, Truck Scheduling in a Cross-Docking Terminal by Using Novel Robust Heuristics, International Journal of Engineering, 32 (2019), 296-305. 

[28]

M. ShakeriM. Y. H. LowS. J. Turner and E. W. Lee, An efficient incremental evaluation function for optimizing truck scheduling in a resource-constrained crossdock using metaheuristics,, Expert Systems with Applications, 45 (2016), 172-184.  doi: 10.1016/j.eswa.2015.09.041.

[29]

J. G. Urzúa-MoralesJ. P. Sepulveda-RojasM. AlfaroG. FuertesR. Ternero and M. Vargas, Logistic modeling of the last mile: Case study santiago, chile,, Sustainability, 12 (2020), 648.  doi: 10.3390/su12020648.

[30]

B. Vahdani and S. Shahramfard, A truck scheduling problem at a cross-docking facility with mixed service mode dock doors, Engineering Computations, 12 (2019), 648. 

[31]

R. H. WalivU. MishraH. Garg and H. P. Umap, A nonlinear programming approach to solve the stochastic multi-objective inventory model using the uncertain information, Arabian Journal for Science and Engineering, 45 (2020), 6963-6973.  doi: 10.1007/s13369-020-04618-z.

[32]

Z. Yong-wu, A Quantity discount model for two-echelon supply chain coordination under stochastic demand, Systems Engineering-Theory & Practice, 7 (2006), 25-32. 

[33]

B. H. Zhou and W. L. Liu, A modified column generation heuristic for hybrid flow shop multiple orders per job scheduling problem, International Journal of Manufacturing Technology and Management, 33 (2019), 88-113.  doi: 10.1504/IJMTM.2019.100166.

[34]

B. H. ZhouM. Yin and Z. Q. Lu, An improved Lagrangian relaxation heuristic for the scheduling problem of operating theatres, Computers & Industrial Engineering, 101 (2016), 490-503.  doi: 10.1016/j.cie.2016.09.003.

[35]

W. Zhou and Y. H. JIN, Fuzzy subgradient algorithm for solving Lagrangian relaxation dual problem, Control Decis., 11 (2004), 1213-1217. 

[36]

L. ZhuX. RenC. Lee and Y. Zhang, Coordination contracts in a dual-channel supply chain with a risk-averse retailer, Sustainability, 9 (2017), 2148.  doi: 10.3390/su9112148.

show all references

References:
[1]

A. Amini and R. Tavakkoli-Moghaddam, A bi-objective truck scheduling problem in a cross-docking center with probability of breakdown for trucks, Computers & Industrial Engineering, 96 (2016), 180-191.  doi: 10.1016/j.cie.2016.03.023.

[2]

H. ArbabiM. M. Nasiri and A. Bozorgi-Amiri, A hub-and-spoke architecture for a parcel delivery system using the cross-docking distribution strategy, Eng. Optim., 53 (2021), 1593-1612.  doi: 10.1080/0305215X.2020.1808973.

[3]

M. T. Assadi and M. Bagheri, Differential evolution and Population-based simulated annealing for truck scheduling problem in multiple door cross-docking systems, Computers & Industrial Engineering, 96 (2016), 149-161.  doi: 10.1016/j.cie.2016.03.021.

[4]

P. BodnarR. de Koster and K. Azadeh, Scheduling trucks in a cross-dock with mixed service mode dock doors, Transportation Science, 51 (2017), 112-131.  doi: 10.1287/trsc.2015.0612.

[5]

N. Boysen and M. Fliedner, Cross dock scheduling: Classification, literature review and research agenda, Omega, 38 (2010), 413-422.  doi: 10.1016/j.omega.2009.10.008.

[6]

A. ChiarelloM. Gaudioso and M. Sammarra, Truck synchronization at single door cross-docking terminals, OR Spectrum, 40 (2018), 395-447.  doi: 10.1007/s00291-018-0510-x.

[7]

H. ChenC. Chu and J. M. Proth, An improvement of the Lagrangean relaxation approach for job shop scheduling: A dynamic programming method, IEEE Transactions on Robotics and Atomation, 14 (1998), 786-795.  doi: 10.1109/70.720354.

[8]

J. Chen, K. Wang and Y. Huang, An integrated inbound logistics mode with intelligent scheduling of milk-run collection, drop and pull delivery and LNG vehicles, Journal of Intelligent Manufacturing, (2020), 1–9. doi: 10.1007/s10845-020-01637-3.

[9]

L. ChenY. Liu and A. Langevin, A multi-compartment vehicle routing problem in cold-chain distribution, Comput. Oper. Res., 111 (2019), 58-66.  doi: 10.1016/j.cor.2019.06.001.

[10]

U. ClausenD. DiekmannM. Pöting and C. Schumacher, Operating parcel transshipment terminals: A combined simulation and optimization approach, Journal of Simulation, 11 (2017), 2-10.  doi: 10.1057/s41273-016-0032-y.

[11]

H. CorstenF. Becker and H. Salewski, Integrating truck and workforce scheduling in a cross-dock: Analysis of different workforce coordination policies, Journal of Business Economics, 90 (2020), 207-237. 

[12]

C. DongQ. LiB. Shen and X. Tong, Sustainability in supply chains with behavioral concerns, Sustainability, 11 (2019), 4051.  doi: 10.3390/su11154051.

[13]

G. B. FonsecaT. H. Nogueira and M. G. Ravetti, A hybrid Lagrangian metaheuristic for the cross-docking flow shop scheduling problem, European J. Oper. Res., 275 (2019), 139-154.  doi: 10.1016/j.ejor.2018.11.033.

[14]

T. Garai and H. Garg, Multi-objective linear fractional inventory model with possibility and necessity constraints under generalised intuitionistic fuzzy set environment, CAAI Transactions on Intelligence Technology, 4 (2019), 175-181. 

[15]

M. GaudiosoM. F. Monaco and M. Sammarra, A Lagrangian heuristics for the truck scheduling problem in multi-door, multi-product Cross-Docking with constant processing time, Omega, 101 (2021), 102255.  doi: 10.1016/j.omega.2020.102255.

[16]

A. Golshahi-RoudbanehM. Hajiaghaei-Keshteli and M. M. Paydar, Developing a lower bound and strong heuristics for a truck scheduling problem in a cross-docking center, Knowledge-Based Systems, 129 (2017), 17-38.  doi: 10.1016/j.knosys.2017.05.006.

[17]

O. Guemri, P. Nduwayo, R. Todosijević, S. Hanafi and F. Glover, Probabilistic tabu search for the cross-docking assignment problem, European J. Oper. Res., 277 (2019), 875–885., doi: 10.1016/j.ejor.2019.03.030.

[18]

A. Gunawan, A. T. Widjaja, P. Vansteenwegen and V. F. Yu, A matheuristic algorithm for solving the vehicle routing problem with cross-docking, International Conference on Learning and Intelligent Optimization Springer, (2020), 9–15. doi: 10.1007/978-3-030-53552-0_2.

[19]

A. GutierrezL. DieulleN. Labadie and N. Velasco, A hybrid metaheuristic algorithm for the vehicle routing problem with stochastic demands, Comput. Oper. Res., 99 (2018), 135-147.  doi: 10.1016/j.cor.2018.06.012.

[20]

A. L. Ladier and G. Alpan, Robust cross-dock scheduling with time windows, Computers & Industrial Engineering, 99 (2016), 16-28.  doi: 10.1016/j.cie.2016.07.003.

[21]

A. L. Ladier and G. Alpan, Crossdock truck scheduling with time windows: Earliness, tardiness and storage policies, J. Intell. Manufacturing, 29 (2018), 569-583. 

[22]

S. M. Mousavi and B. Vahdani, Cross-docking location selection in distribution systems: A new intuitionistic fuzzy hierarchical decision model, International J. Computational Intelligence Systems, 9 (2016), 91-109.  doi: 10.1080/18756891.2016.1144156.

[23]

W. NassiefI. Contreras and R. As'ad, A mixed-integer programming formulation and Lagrangean relaxation for the cross-dock door assignment problem, International Journal of Production Research, 54 (2016), 494-508.  doi: 10.1080/00207543.2014.1003664.

[24]

W. Nassief, I. Contreras and B. Jaumard, A comparison of formulations and relaxations for cross-dock door assignment problems, Comput. Oper. Res., 94 (2018), 76–88., doi: 10.1016/j.cor.2018.01.022.

[25]

S. NiroomandH. Garg and A. Mahmoodirad, An intuitionistic fuzzy two stage supply chain network design problem with multi-mode demand and multi-mode transportation, ISA transactions, 107 (2020), 117-133.  doi: 10.1016/j.isatra.2020.07.033.

[26]

C. SerranoX. Delorme and A. Dolgui, Scheduling of truck arrivals, truck departures and shop-floor operation in a cross-dock platform, based on trucks loading plans, International Journal of Production Economics, 194 (2017), 102-112.  doi: 10.1016/j.ijpe.2017.09.008.

[27]

I. SeyediM. Hamedi and R. Tavakkoli-Moghaddam, Truck Scheduling in a Cross-Docking Terminal by Using Novel Robust Heuristics, International Journal of Engineering, 32 (2019), 296-305. 

[28]

M. ShakeriM. Y. H. LowS. J. Turner and E. W. Lee, An efficient incremental evaluation function for optimizing truck scheduling in a resource-constrained crossdock using metaheuristics,, Expert Systems with Applications, 45 (2016), 172-184.  doi: 10.1016/j.eswa.2015.09.041.

[29]

J. G. Urzúa-MoralesJ. P. Sepulveda-RojasM. AlfaroG. FuertesR. Ternero and M. Vargas, Logistic modeling of the last mile: Case study santiago, chile,, Sustainability, 12 (2020), 648.  doi: 10.3390/su12020648.

[30]

B. Vahdani and S. Shahramfard, A truck scheduling problem at a cross-docking facility with mixed service mode dock doors, Engineering Computations, 12 (2019), 648. 

[31]

R. H. WalivU. MishraH. Garg and H. P. Umap, A nonlinear programming approach to solve the stochastic multi-objective inventory model using the uncertain information, Arabian Journal for Science and Engineering, 45 (2020), 6963-6973.  doi: 10.1007/s13369-020-04618-z.

[32]

Z. Yong-wu, A Quantity discount model for two-echelon supply chain coordination under stochastic demand, Systems Engineering-Theory & Practice, 7 (2006), 25-32. 

[33]

B. H. Zhou and W. L. Liu, A modified column generation heuristic for hybrid flow shop multiple orders per job scheduling problem, International Journal of Manufacturing Technology and Management, 33 (2019), 88-113.  doi: 10.1504/IJMTM.2019.100166.

[34]

B. H. ZhouM. Yin and Z. Q. Lu, An improved Lagrangian relaxation heuristic for the scheduling problem of operating theatres, Computers & Industrial Engineering, 101 (2016), 490-503.  doi: 10.1016/j.cie.2016.09.003.

[35]

W. Zhou and Y. H. JIN, Fuzzy subgradient algorithm for solving Lagrangian relaxation dual problem, Control Decis., 11 (2004), 1213-1217. 

[36]

L. ZhuX. RenC. Lee and Y. Zhang, Coordination contracts in a dual-channel supply chain with a risk-averse retailer, Sustainability, 9 (2017), 2148.  doi: 10.3390/su9112148.

Figure 1.  The scheduling process at cross-dock
Figure 2.  Several values of %gap (group2) based on the different value of slackness
Figure 3.  Values of %gap and %dev in group 2
Table 1.  Computer results for problems in group 1, b = 0.98, 0.95, and 0.90
p=0.98 p=0.95 p=0.90
L G L G L G
I #t×#d s IP LR %gap CPU UB %dev IP LR %gap CPU UB %dev IP LR %gap CPU UB %dev
1 15 1.683 1.683 5.32 0.55 1.815 10.43 1.98 1.98 4.97 0.56 2.187 10.43 1.643 1.643 5.27 0.46 1.99 11.99
2 20 1.701 1.701 4.82 0.5 1.89 8.37 2.1 2.1 4.38 0.33 2.278 8.45 1.785 1.785 5.39 0.42 1.754 8.03
3 4×2 30 1.729 1.729 3.44 0.53 2.004 15.27 2.059 2.059 3.55 0.42 2.358 14.54 1.997 1.997 3.59 0.51 1.769 14.69
4 15 2.56 2.56 9.55 0.66 2.45 14.81 2.56 2.56 9.27 0.68 2.816 14.52 2.765 2.765 9.83 0.84 3.013 14.96
5 20 2.26 2.26 8.15 0.8 3.064 13.02 2.659 2.659 7.03 0.8 3.225 12.76 2.872 2.872 6.89 0.8 2.838 13.4
6 5×3 30 2.498 2.498 10.55 0.65 2.648 12.76 2.602 2.602 9.02 0.8 3.152 12.76 2.862 2.862 11 0.96 3.089 12.89
7 15 2.709 2.709 6.58 1.59 3.954 26.35 3.078 3.078 6.33 1.61 4.163 26.62 2.924 2.924 6.46 1.07 3.83 27.95
8 20 3.108 3.108 4.32 1.64 3.533 25 3.205 3.205 4.32 1.06 4.257 24.27 2.66 2.66 4.62 1.33 4.087 23.06
9 6×3 30 2.495 2.495 7.55 1.6 3.735 26.32 3.08 3.08 6.29 1.02 4.016 26.06 2.957 2.957 6.54 1.27 4.257 27.1
10 15 3.31 3.31 4.76 1.92 4.153 13.37 3.755 3.988 4.21 2.35 4.72 13.37 4.068 4.068 4.04 1.88 4.153 12.84
11 20 3.425 3.624 6.35 1.93 4.337 14.81 3.89 3.897 4.96 1.91 4.518 15.11 4.155 4.17 6.05 2.38 3.433 15.87
12 7×3 30 3.257 3.471 3.69 3.13 3.747 21.32 3.572 3.732 3.55 2.66 4.625 21.98 3.375 3.471 3.41 3.19 4.163 22.2
13 15 3.18 3.381 7.79 5.86 4.848 29.61 3.58 3.636 6.04 7.1 5.051 30.53 3.09 3.09 7.61 7.1 3.788 30.84
14 20 3.155 3.301 6.23 4.89 4.847 29.92 3.42 3.628 6.23 7.41 5.049 30.53 3.171 3.301 6.17 4.94 3.786 29
15 7×4 30 3.178 3.204 6.83 5.38 4.262 32.8 3.595 3.641 5.38 8.41 5.014 31.24 3.285 3.386 6.62 8.41 4.061 32.49
16 15 3.65 3.826 5.76 4.4 5.089 24.08 4.058 4.159 5.7 4.27 5.472 24.08 3.588 3.701 5.81 5.34 5.472 25.28
17 20 3.425 3.425 5.58 5.79 5.329 21.76 4.117 4.228 5.03 4.45 5.438 22.91 4.489 4.608 5.53 5.57 4.894 23.14
18 8×3 30 3.785 3.85 6.41 8.54 4.745 22.79 4.095 4.184 5.57 10.05 5.214 23.49 4.258 4.435 7.19 8.37 4.432 24.19
19 15 3.455 3.485 4.57 8.09 5.375 35.21 3.986 4.1 4.76 7.03 5.973 36.3 3.698 3.772 4.57 7.03 5.973 35.94
20 20 3.576 3.678 5.81 6.36 4.802 34.09 4.168 4.18 4.76 7.64 5.856 33.42 3.259 3.344 5.09 9.17 6.09 33.09
21 8×4 30 3.385 3.428 6.14 9.16 5.446 32.42 4.15 4.18 4.76 11.33 5.856 33.42 3.857 3.929 4.52 11.33 5.739 33.09
Instance is short for $i$, $t$ for trucks, $d$ for doors, $s$ for the slackness of temporary storage capacity (%), $L$ for the Lagrangian relaxation algorithm, $G$ for the Greedy algorithm. The value of $IP, LP$ and $UB$ is in $10^5$.
p=0.98 p=0.95 p=0.90
L G L G L G
I #t×#d s IP LR %gap CPU UB %dev IP LR %gap CPU UB %dev IP LR %gap CPU UB %dev
1 15 1.683 1.683 5.32 0.55 1.815 10.43 1.98 1.98 4.97 0.56 2.187 10.43 1.643 1.643 5.27 0.46 1.99 11.99
2 20 1.701 1.701 4.82 0.5 1.89 8.37 2.1 2.1 4.38 0.33 2.278 8.45 1.785 1.785 5.39 0.42 1.754 8.03
3 4×2 30 1.729 1.729 3.44 0.53 2.004 15.27 2.059 2.059 3.55 0.42 2.358 14.54 1.997 1.997 3.59 0.51 1.769 14.69
4 15 2.56 2.56 9.55 0.66 2.45 14.81 2.56 2.56 9.27 0.68 2.816 14.52 2.765 2.765 9.83 0.84 3.013 14.96
5 20 2.26 2.26 8.15 0.8 3.064 13.02 2.659 2.659 7.03 0.8 3.225 12.76 2.872 2.872 6.89 0.8 2.838 13.4
6 5×3 30 2.498 2.498 10.55 0.65 2.648 12.76 2.602 2.602 9.02 0.8 3.152 12.76 2.862 2.862 11 0.96 3.089 12.89
7 15 2.709 2.709 6.58 1.59 3.954 26.35 3.078 3.078 6.33 1.61 4.163 26.62 2.924 2.924 6.46 1.07 3.83 27.95
8 20 3.108 3.108 4.32 1.64 3.533 25 3.205 3.205 4.32 1.06 4.257 24.27 2.66 2.66 4.62 1.33 4.087 23.06
9 6×3 30 2.495 2.495 7.55 1.6 3.735 26.32 3.08 3.08 6.29 1.02 4.016 26.06 2.957 2.957 6.54 1.27 4.257 27.1
10 15 3.31 3.31 4.76 1.92 4.153 13.37 3.755 3.988 4.21 2.35 4.72 13.37 4.068 4.068 4.04 1.88 4.153 12.84
11 20 3.425 3.624 6.35 1.93 4.337 14.81 3.89 3.897 4.96 1.91 4.518 15.11 4.155 4.17 6.05 2.38 3.433 15.87
12 7×3 30 3.257 3.471 3.69 3.13 3.747 21.32 3.572 3.732 3.55 2.66 4.625 21.98 3.375 3.471 3.41 3.19 4.163 22.2
13 15 3.18 3.381 7.79 5.86 4.848 29.61 3.58 3.636 6.04 7.1 5.051 30.53 3.09 3.09 7.61 7.1 3.788 30.84
14 20 3.155 3.301 6.23 4.89 4.847 29.92 3.42 3.628 6.23 7.41 5.049 30.53 3.171 3.301 6.17 4.94 3.786 29
15 7×4 30 3.178 3.204 6.83 5.38 4.262 32.8 3.595 3.641 5.38 8.41 5.014 31.24 3.285 3.386 6.62 8.41 4.061 32.49
16 15 3.65 3.826 5.76 4.4 5.089 24.08 4.058 4.159 5.7 4.27 5.472 24.08 3.588 3.701 5.81 5.34 5.472 25.28
17 20 3.425 3.425 5.58 5.79 5.329 21.76 4.117 4.228 5.03 4.45 5.438 22.91 4.489 4.608 5.53 5.57 4.894 23.14
18 8×3 30 3.785 3.85 6.41 8.54 4.745 22.79 4.095 4.184 5.57 10.05 5.214 23.49 4.258 4.435 7.19 8.37 4.432 24.19
19 15 3.455 3.485 4.57 8.09 5.375 35.21 3.986 4.1 4.76 7.03 5.973 36.3 3.698 3.772 4.57 7.03 5.973 35.94
20 20 3.576 3.678 5.81 6.36 4.802 34.09 4.168 4.18 4.76 7.64 5.856 33.42 3.259 3.344 5.09 9.17 6.09 33.09
21 8×4 30 3.385 3.428 6.14 9.16 5.446 32.42 4.15 4.18 4.76 11.33 5.856 33.42 3.857 3.929 4.52 11.33 5.739 33.09
Instance is short for $i$, $t$ for trucks, $d$ for doors, $s$ for the slackness of temporary storage capacity (%), $L$ for the Lagrangian relaxation algorithm, $G$ for the Greedy algorithm. The value of $IP, LP$ and $UB$ is in $10^5$.
Table 2.  Computer results for problems in group 2 (slackness = 10)
Instances #trucks×#doors Lagrangian relaxation algorithm Greedy algorithm
LR %gap CPU time UB %dev
1 9×3 4.759 5.21 18 5.965 18.8
2 9×4 4.856 5.28 19.76 6.382 24.5
3 9×5 4.661 4.38 30.13 6.8 39.5
4 10×3 5.527 5.25 42.36 6.876 14.43
5 10×4 5.595 4.76 15.57 7.014 21.56
6 10×5 5.055 5.75 44.57 7.609 43.35
7 11×5 6.017 7.86 77.65 8.618 31.41
8 11×6 5.997 9.09 80.49 9.149 38.69
9 15×6 8.223 9.09 177.84 12.43 37.39
10 15×7 8.21 7.42 124.02 13.09 47.64
11 20×10 10.89 9.91 265.06 20.73 71.41
Instances #trucks×#doors Lagrangian relaxation algorithm Greedy algorithm
LR %gap CPU time UB %dev
1 9×3 4.759 5.21 18 5.965 18.8
2 9×4 4.856 5.28 19.76 6.382 24.5
3 9×5 4.661 4.38 30.13 6.8 39.5
4 10×3 5.527 5.25 42.36 6.876 14.43
5 10×4 5.595 4.76 15.57 7.014 21.56
6 10×5 5.055 5.75 44.57 7.609 43.35
7 11×5 6.017 7.86 77.65 8.618 31.41
8 11×6 5.997 9.09 80.49 9.149 38.69
9 15×6 8.223 9.09 177.84 12.43 37.39
10 15×7 8.21 7.42 124.02 13.09 47.64
11 20×10 10.89 9.91 265.06 20.73 71.41
Table 3.  Computer results for problems in group 2 (slackness = 15)
Instances #trucks×#doors Lagrangian relaxation algorithm Greedy algorithm
LR %gap CPU time UB %dev
1 9×3 4.742 5.17 24.5 5.892 19.3
2 9×4 4.813 4.97 22.69 6.382 24.5
3 9×5 4.559 5.65 36.25 6.66 40.72
4 10×3 5.456 5.09 40.71 6.674 16.1
5 10×4 5.195 4.76 31.97 7.142 30.92
6 10×5 5.355 5.3 42.97 7.609 35.32
7 11×5 6.017 6.54 55.32 8.618 33.86
8 11×6 5.6 7.45 91.46 9.149 41.4
9 15×6 8.403 8.26 125.77 12.43 35.68
10 15×7 8.237 6.65 81.64 13.18 49.35
11 20×10 10.64 8.26 164.22 20.69 68.47
Instances #trucks×#doors Lagrangian relaxation algorithm Greedy algorithm
LR %gap CPU time UB %dev
1 9×3 4.742 5.17 24.5 5.892 19.3
2 9×4 4.813 4.97 22.69 6.382 24.5
3 9×5 4.559 5.65 36.25 6.66 40.72
4 10×3 5.456 5.09 40.71 6.674 16.1
5 10×4 5.195 4.76 31.97 7.142 30.92
6 10×5 5.355 5.3 42.97 7.609 35.32
7 11×5 6.017 6.54 55.32 8.618 33.86
8 11×6 5.6 7.45 91.46 9.149 41.4
9 15×6 8.403 8.26 125.77 12.43 35.68
10 15×7 8.237 6.65 81.64 13.18 49.35
11 20×10 10.64 8.26 164.22 20.69 68.47
Table 4.  Computer results for problems in group 2 (slackness = 20)
Instances #trucks×#doors Lagrangian relaxation algorithm Greedy algorithm
LR %gap CPU time UB %dev
1 9×3 5.035 4.53 18.16 6.003 13.12
2 9×4 4.764 5.32 27.23 6.173 29.83
3 9×5 4.758 6.02 26.69 6.899 34.3
4 10×3 5.466 4.92 29.03 6.674 16.1
5 10×4 5.087 5.56 27.07 7.142 32.45
6 10×5 5.075 4.9 40.41 7.609 42.79
7 11×5 6.037 7.41 62.67 8.618 32.18
8 11×6 5.777 7.41 62.09 9.139 46.64
9 15×6 8.012 7.41 133.29 12.4 36.94
10 15×7 8.045 5.82 159.65 13.22 45.71
11 20×10 10.85 7.41 226.27 20.73 66.9
Instances #trucks×#doors Lagrangian relaxation algorithm Greedy algorithm
LR %gap CPU time UB %dev
1 9×3 5.035 4.53 18.16 6.003 13.12
2 9×4 4.764 5.32 27.23 6.173 29.83
3 9×5 4.758 6.02 26.69 6.899 34.3
4 10×3 5.466 4.92 29.03 6.674 16.1
5 10×4 5.087 5.56 27.07 7.142 32.45
6 10×5 5.075 4.9 40.41 7.609 42.79
7 11×5 6.037 7.41 62.67 8.618 32.18
8 11×6 5.777 7.41 62.09 9.139 46.64
9 15×6 8.012 7.41 133.29 12.4 36.94
10 15×7 8.045 5.82 159.65 13.22 45.71
11 20×10 10.85 7.41 226.27 20.73 66.9
Table 5.  Computer results for problems in group 2 (slackness = 30)
Instances #trucks×#doors Lagrangian relaxation algorithm Greedy algorithm
LR %gap CPU time UB %dev
1 9×3 4.76 4.8 17.01 5.965 19.3
2 9×4 4.647 5.08 22.76 6.108 30.38
3 9×5 4.684 3.9 22.59 6.8 39.5
4 10×3 5.943 4.9 35.42 6.344 6.74
5 10×4 5.375 4.76 42.1 7.082 26.54
6 10×5 5.315 4.76 47.71 7.609 36.34
7 11×5 6.057 4.76 50.29 8.618 35.51
8 11×6 5.817 6.54 77.44 9.149 46.99
9 15×6 8.221 6.54 114.18 12.37 40.67
10 15×7 8.527 4.29 148.43 13.3 47.33
11 20×10 10.79 5.66 302.54 23.68 70.76
Instances #trucks×#doors Lagrangian relaxation algorithm Greedy algorithm
LR %gap CPU time UB %dev
1 9×3 4.76 4.8 17.01 5.965 19.3
2 9×4 4.647 5.08 22.76 6.108 30.38
3 9×5 4.684 3.9 22.59 6.8 39.5
4 10×3 5.943 4.9 35.42 6.344 6.74
5 10×4 5.375 4.76 42.1 7.082 26.54
6 10×5 5.315 4.76 47.71 7.609 36.34
7 11×5 6.057 4.76 50.29 8.618 35.51
8 11×6 5.817 6.54 77.44 9.149 46.99
9 15×6 8.221 6.54 114.18 12.37 40.67
10 15×7 8.527 4.29 148.43 13.3 47.33
11 20×10 10.79 5.66 302.54 23.68 70.76
[1]

Wan Nor Ashikin Wan Ahmad Fatthi, Adibah Shuib, Rosma Mohd Dom. A mixed integer programming model for solving real-time truck-to-door assignment and scheduling problem at cross docking warehouse. Journal of Industrial and Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431

[2]

Fatemeh Kangi, Seyed Hamid Reza Pasandideh, Esmaeil Mehdizadeh, Hamed Soleimani. The optimization of a multi-period multi-product closed-loop supply chain network with cross-docking delivery strategy. Journal of Industrial and Management Optimization, 2022, 18 (5) : 3393-3431. doi: 10.3934/jimo.2021118

[3]

Shankar C. Venkataramani. An SBV relaxation of the Cross-Newell energy for modeling stripe patterns and their defects. Discrete and Continuous Dynamical Systems - S, 2022, 15 (9) : 2719-2746. doi: 10.3934/dcdss.2022101

[4]

Jiping Tao, Ronghuan Huang, Tundong Liu. A $2.28$-competitive algorithm for online scheduling on identical machines. Journal of Industrial and Management Optimization, 2015, 11 (1) : 185-198. doi: 10.3934/jimo.2015.11.185

[5]

Artyom Nahapetyan, Panos M. Pardalos. A bilinear relaxation based algorithm for concave piecewise linear network flow problems. Journal of Industrial and Management Optimization, 2007, 3 (1) : 71-85. doi: 10.3934/jimo.2007.3.71

[6]

Anwa Zhou, Jinyan Fan. A semidefinite relaxation algorithm for checking completely positive separable matrices. Journal of Industrial and Management Optimization, 2019, 15 (2) : 893-908. doi: 10.3934/jimo.2018076

[7]

Didem Cinar, José António Oliveira, Y. Ilker Topcu, Panos M. Pardalos. A priority-based genetic algorithm for a flexible job shop scheduling problem. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391

[8]

Jingwen Zhang, Wanjun Liu, Wanlin Liu. An efficient genetic algorithm for decentralized multi-project scheduling with resource transfers. Journal of Industrial and Management Optimization, 2022, 18 (1) : 1-24. doi: 10.3934/jimo.2020140

[9]

Stephane Chretien, Paul Clarkson. A fast algorithm for the semi-definite relaxation of the state estimation problem in power grids. Journal of Industrial and Management Optimization, 2020, 16 (1) : 431-443. doi: 10.3934/jimo.2018161

[10]

Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial and Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117

[11]

Liangliang Sun, Fangjun Luan, Yu Ying, Kun Mao. Rescheduling optimization of steelmaking-continuous casting process based on the Lagrangian heuristic algorithm. Journal of Industrial and Management Optimization, 2017, 13 (3) : 1431-1448. doi: 10.3934/jimo.2016081

[12]

Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial and Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122

[13]

Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial and Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269

[14]

Xuewen Huang, Xiaotong Zhang, Sardar M. N. Islam, Carlos A. Vega-Mejía. An enhanced Genetic Algorithm with an innovative encoding strategy for flexible job-shop scheduling with operation and processing flexibility. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2943-2969. doi: 10.3934/jimo.2019088

[15]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial and Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703

[16]

Ling Lin, Dong He, Zhiyi Tan. Bounds on delay start LPT algorithm for scheduling on two identical machines in the $l_p$ norm. Journal of Industrial and Management Optimization, 2008, 4 (4) : 817-826. doi: 10.3934/jimo.2008.4.817

[17]

Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial and Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243

[18]

Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1801-1834. doi: 10.3934/jimo.2019030

[19]

Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial and Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057

[20]

Xiaoxiao Yuan, Jing Liu, Xingxing Hao. A moving block sequence-based evolutionary algorithm for resource investment project scheduling problems. Big Data & Information Analytics, 2017, 2 (1) : 39-58. doi: 10.3934/bdia.2017007

2021 Impact Factor: 1.411

Article outline

Figures and Tables

[Back to Top]