American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Branching improved Deep Q Networks for solving pursuit-evasion strategy solution of spacecraft
  • 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

Binghai Zhou , , Yuanrui Lei and  Shi Zong

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.

Keywords: truck scheduling, cross-docking, logistics, Lagrangian relaxation algorithm.
Mathematics Subject Classification: Primary: 90B35; Secondary: 90C11.
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 & 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.  Google Scholar

[2]

H. Arbabi, M. 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.  Google Scholar

[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.  Google Scholar

[4]

P. Bodnar, R. 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.  Google Scholar

[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.  Google Scholar

[6]

A. Chiarello, M. 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.  Google Scholar

[7]

H. Chen, C. 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.  Google Scholar

[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.  Google Scholar

[9]

L. Chen, Y. 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.  Google Scholar

[10]

U. Clausen, D. Diekmann, M. 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.  Google Scholar

[11]

H. Corsten, F. 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.   Google Scholar

[12]

C. Dong, Q. Li, B. Shen and X. Tong, Sustainability in supply chains with behavioral concerns, Sustainability, 11 (2019), 4051.  doi: 10.3390/su11154051.  Google Scholar

[13]

G. B. Fonseca, T. 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.  Google Scholar

[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.   Google Scholar

[15]

M. Gaudioso, M. 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.  Google Scholar

[16]

A. Golshahi-Roudbaneh, M. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

A. Gutierrez, L. Dieulle, N. 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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[23]

W. Nassief, I. 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.  Google Scholar

[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.  Google Scholar

[25]

S. Niroomand, H. 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.  Google Scholar

[26]

C. Serrano, X. 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.  Google Scholar

[27]

I. Seyedi, M. 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.   Google Scholar

[28]

M. Shakeri, M. Y. H. Low, S. 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.  Google Scholar

[29]

J. G. Urzúa-Morales, J. P. Sepulveda-Rojas, M. Alfaro, G. Fuertes, R. Ternero and M. Vargas, Logistic modeling of the last mile: Case study santiago, chile,, Sustainability, 12 (2020), 648.  doi: 10.3390/su12020648.  Google Scholar

[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.   Google Scholar

[31]

R. H. Waliv, U. Mishra, H. 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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[34]

B. H. Zhou, M. 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.  Google Scholar

[35]

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

[36]

L. Zhu, X. Ren, C. 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.  Google Scholar

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.  Google Scholar

[2]

H. Arbabi, M. 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.  Google Scholar

[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.  Google Scholar

[4]

P. Bodnar, R. 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.  Google Scholar

[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.  Google Scholar

[6]

A. Chiarello, M. 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.  Google Scholar

[7]

H. Chen, C. 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.  Google Scholar

[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.  Google Scholar

[9]

L. Chen, Y. 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.  Google Scholar

[10]

U. Clausen, D. Diekmann, M. 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.  Google Scholar

[11]

H. Corsten, F. 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.   Google Scholar

[12]

C. Dong, Q. Li, B. Shen and X. Tong, Sustainability in supply chains with behavioral concerns, Sustainability, 11 (2019), 4051.  doi: 10.3390/su11154051.  Google Scholar

[13]

G. B. Fonseca, T. 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.  Google Scholar

[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.   Google Scholar

[15]

M. Gaudioso, M. 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.  Google Scholar

[16]

A. Golshahi-Roudbaneh, M. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

A. Gutierrez, L. Dieulle, N. 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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[23]

W. Nassief, I. 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.  Google Scholar

[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.  Google Scholar

[25]

S. Niroomand, H. 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.  Google Scholar

[26]

C. Serrano, X. 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.  Google Scholar

[27]

I. Seyedi, M. 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.   Google Scholar

[28]

M. Shakeri, M. Y. H. Low, S. 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.  Google Scholar

[29]

J. G. Urzúa-Morales, J. P. Sepulveda-Rojas, M. Alfaro, G. Fuertes, R. Ternero and M. Vargas, Logistic modeling of the last mile: Case study santiago, chile,, Sustainability, 12 (2020), 648.  doi: 10.3390/su12020648.  Google Scholar

[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.   Google Scholar

[31]

R. H. Waliv, U. Mishra, H. 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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[34]

B. H. Zhou, M. 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.  Google Scholar

[35]

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

[36]

L. Zhu, X. Ren, C. 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.  Google Scholar

Figure 1.  The scheduling process at cross-dock
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Several values of %gap (group2) based on the different value of slackness
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Values of %gap and %dev in group 2
Figure Options

Download full-size image

Download as PowerPoint slide

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$.
Table Options

Download as excel

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
Table Options

Download as excel

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
Table Options

Download as excel

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
Table Options

Download as excel

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
Table Options

Download as excel

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 & 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 & Management Optimization, 2021  doi: 10.3934/jimo.2021118
[3]

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

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

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

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 & Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391
[7]

Jingwen Zhang, Wanjun Liu, Wanlin Liu. An efficient genetic algorithm for decentralized multi-project scheduling with resource transfers. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020140
[8]

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

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

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

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 & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269
[12]

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 & Management Optimization, 2020, 16 (6) : 2943-2969. doi: 10.3934/jimo.2019088
[13]

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

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 & Management Optimization, 2008, 4 (4) : 817-826. doi: 10.3934/jimo.2008.4.817
[15]

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 & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243
[16]

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 & Management Optimization, 2020, 16 (4) : 1801-1834. doi: 10.3934/jimo.2019030
[17]

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 & Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057
[18]

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
[19]

Ran Ma, Lu Zhang, Yuzhong Zhang. A best possible algorithm for an online scheduling problem with position-based learning effect. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021144
[20]

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

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (64)
  • HTML views (71)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences