
-
Previous Article
Valuing equity-linked death benefits with a threshold expense structure under a regime-switching Lévy model
- JIMO Home
- This Issue
-
Next Article
Equity-based incentive to coordinate shareholder-manager interests under information asymmetry
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 |
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.
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. 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. |
[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. 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. |
[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. 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. |
[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. |
[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. 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. |
[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. |
[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.
|
[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. |
[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. |
[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. 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. |
[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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. |
[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.
|
[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. |
[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. |
[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. 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. |
[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. 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. |
[35] |
W. Zhou and Y. H. JIN,
Fuzzy subgradient algorithm for solving Lagrangian relaxation dual problem, Control Decis., 11 (2004), 1213-1217.
|
[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. |
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. 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. |
[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. 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. |
[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. 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. |
[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. |
[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. 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. |
[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. |
[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.
|
[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. |
[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. |
[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. 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. |
[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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. |
[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.
|
[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. |
[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. |
[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. 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. |
[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. 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. |
[35] |
W. Zhou and Y. H. JIN,
Fuzzy subgradient algorithm for solving Lagrangian relaxation dual problem, Control Decis., 11 (2004), 1213-1217.
|
[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. |



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 |
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 |
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 |
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 |
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 |
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, 2021 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 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] |
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 |
[12] |
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 |
[13] |
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 |
[14] |
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 |
[15] |
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 |
[16] |
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 |
[17] |
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 |
[18] |
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 |
[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 |
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]