Article Contents
Article Contents

# Two-agent integrated scheduling of production and distribution operations with fixed departure times

• * Corresponding author: Dongya Han

Cheng was supported in part by The Hong Kong Polytechnic University under the Fung Yiu King-Wing Hang Bank Endowed Professorship in Business Administration. Wu was supported by the Ministry of Science and Technology of Taiwan under grant number MOST 109-2410-H-035-019

• We consider integrated scheduling of production and distribution operations associated with two customers (agents). Each customer has a set of orders to be processed on the single production line at a supplier on a competitive basis. The finished orders of the same customer are then packed and delivered to the customer by a third-party logistics (3PL) provider with a limited number of delivery transporters. The number of orders carried in a delivery transporter cannot exceed its delivery capacity. Each transporter incurs a fixed delivery cost regardless of the number of orders it carries, and departs from the 3PL provider to a customer at fixed times. Each customer desires to minimise a certain optimality criterion involving simultaneously the customer service level and the total delivery cost for its orders only. The customer service level for a customer is related to the times when its orders are delivered to it. The problem is to determine a joint schedule of production and distribution to minimise the objective of one customer, while keeping the objective of the other customer at or below a predefined level. Using several optimality criteria to measure the customer service level, we obtain different scenarios that depend on optimality criterion of each customer. For each scenario, we either devise an efficient solution procedure to solve it or demonstrate that such a solution procedure is impossible to exist.

Mathematics Subject Classification: Primary: 90B35; Secondary: 68M20.

 Citation:

• Table 1.  Computational complexity results

 Problem Complexity $(\sum w_j^AD_j^A+TC^A, \gamma^B\leq V^B)$ SNP, even if there is no capacity constraint on the delivery transporters, Theorems 5.1 and 7.2 $(\sum D_j^A+TC^A, f_{\max}^B+TC^B\leq V^B)$ PS, $O({{s}^{2}}{{n}_{A}}n_{B}^{2}n_{\max d}^{A}n_{\max d}^{B}\min \{{{v}^{B}},{{n}_{B}}\})$, Theorem 4.4 $(f_{\max}^B+TC^B, \sum D_j^A+TC^A\leq V^A)$ PS, $O(s^2n_An_B^2n^A_{\max d}n^B_{\max d}$ $\min \{{{v}^{B}},{{n}_{B}}\}\log (Q_{u}^{B}-Q_{l}^{B}))$, Theorem 4.5 $(\sum w_j^AD_j^A+TC^A, f_{\max}^B+TC^B\leq V^B)_{s=\overline{s}}$ ONP, $O({{n}_{A}}n_{B}^{2}{{(n_{\max d}^{A})}^{\bar{s}-1}}n_{\max d}^{B}{{P}^{\bar{s}-1}}\min \{{{v}^{B}},{{n}_{B}}\})$, Theorem 7.2 $(f_{\max}^B+TC^B, \sum w_j^AD_j^A+TC^A\leq V^A)_{s=\overline{s}}$ ONP, $O({{n}_{A}}n_{B}^{2}{{(n_{\max d}^{A})}^{\bar{s}-1}}n_{\max d}^{B}{{P}^{\bar{s}-1}}\min \{{{v}^{B}},{{n}_{B}}\}\log (Q_{u}^{B}-Q_{l}^{B}))$, Theorem 7.2 $(\sum w_j^AD_j^A+TC^A, \sum D_k^B+TC^B\leq V^B)_{s=\overline{s}}$ ONP, $O(n_An_B(n^A_{\max d})^{\overline{s}-1}$ $n^B_{\max d}P^{\overline{s}-1}V^B)$, Theorem 5.6 $(\sum w_j^AD_j^A+TC^A, \sum w_k^BU_k^B+TC^B\leq V^B)_{s=\overline{s}}$ ONP, $O({n_A}{n_B}{(n_{\max d}^A)^{\bar s - 1}}$ $n_{\max d}^B{P^{\bar s - 1}}{P^B}{V^B})$, Theorem 7.2 $(\sum D_j^A+TC^A, \sum D_k^B+TC^B\leq V^B)$ Open, $O(s^2n_An_B(n^A_{\max d})n^B_{\max d}V^B)$, Theorem 7.2 $(\sum D_j^A+TC^A, \sum w_k^BU_k^B+TC^B\leq V^B)$ ONP, $O(s^2n_An_B(n^A_{\max d})n^B_{\max d}P^BV^B)$, Theorem 6.5 $(\sum w_j^AU_j^A+TC^A, \sum w_k^BU_k^B+TC^B\leq V^B)$ ONP, $O(s^2n_An_B(n^A_{\max d})n^B_{\max d}PV^B)$, Theorem 7.1

Table 2.  Overview of the problem characteristics in recent recent studies on integrate production and distribution

 Article Number of agents Delivery capacity Delivery cost Delivery mode Departure times Agnetis et al. [1] One Bounded Yes Non-splittable Fixed Hall et al. [7] One Unbounded No Non-splittable Fixed Han et al. [9] One Bounded Yes Non-splittable Fixed Kovalyov et al. [12] Two Unbounded No Non-splittable Fixed Leung and Chen [14] One Bounded No Non-splittable Fixed Li et al. [15] One Bounded No Splittable or Non-splittable Fixed Melo and Wolsey [18] One Bounded Yes Non-splittable Fixed Mor and Mosheiov [19] Two Unbounded No Non-splittable Fixed Seddik et al. [23] One Not involve No Not involve Fixed Stecke and Zhao [24] One Bounded Yes Splittable or Non-splittable Fixed Yin et al. [35] Two Unbounded Yes Non-splittable Fixed Yin et al. [37,34] Two Unbounded Yes Non-splittable No Our paper Multiple Bounded Yes Non-splittable Yes

Table 3.  Computational complexity results

 Problem Complexity $(\sum w_j^AD_j^A+TC^A, \gamma^B\leq V^B)$ SNP, even if there is no capacity constraint on the delivery transporters, Theorems 5.1 and 7.2 $(\sum D_j^A+TC^A, f_{\max}^B+TC^B\leq V^B)$ PS, $O(s^2n_An_B^2n^A_{\max d}n^B_{\max d}\min v^B, n_B )$, Theorem 4.4 $(f_{\max}^B+TC^B, \sum D_j^A+TC^A\leq V^A)$ PS, $O(s^2n_An_B^2n^A_{\max d}n^B_{\max d}$ $\min v^B, n_B \log(Q_u^B-Q_l^B))$, Theorem 4.5 $(\sum w_j^AD_j^A+TC^A, f_{\max}^B+TC^B\leq V^B)_{s=\overline{s}}$ ONP, $O(n_An_B^2(n^A_{\max d})^{\overline{s}-1}n^B_{\max d}P^{\overline{s}-1}\min v^B, n_B )$, Theorem 7.2 $(f_{\max}^B+TC^B, \sum w_j^AD_j^A+TC^A\leq V^A)_{s=\overline{s}}$ ONP, $O(n_An_B^2(n^A_{\max d})^{\overline{s}-1}n^B_{\max d}P^{\overline{s}-1}\min v^B, n_B \log(Q_u^B-Q_l^B))$, Theorem 7.2 $(\sum w_j^AD_j^A+TC^A, \sum D_k^B+TC^B\leq V^B)_{s=\overline{s}}$ ONP, $O(n_An_B(n^A_{\max d})^{\overline{s}-1}$ $n^B_{\max d}P^{\overline{s}-1}V^B)$, Theorem 5.6 $(\sum w_j^AD_j^A+TC^A, \sum w_k^BU_k^B+TC^B\leq V^B)_{s=\overline{s}}$ ONP, $O(n_An_B(n^A_{\max d})^{\overline{s}-1}$ $n^B_{\max d}P^{\overline{s}-1}P^BV^B)$, Theorem 7.2 $(\sum D_j^A+TC^A, \sum D_k^B+TC^B\leq V^B)$ Open, $O(s^2n_An_B(n^A_{\max d})n^B_{\max d}V^B)$, Theorem 7.2 $(\sum D_j^A+TC^A, \sum w_k^BU_k^B+TC^B\leq V^B)$ ONP, $O(s^2n_An_B(n^A_{\max d})n^B_{\max d}P^BV^B)$, Theorem 6.5 $(\sum w_j^AU_j^A+TC^A, \sum w_k^BU_k^B+TC^B\leq V^B)$ ONP, $O(s^2n_An_B(n^A_{\max d})n^B_{\max d}PV^B)$, Theorem 7.1
•  [1] A. Agnetis, M. A. Aloulou and M. Y. Kovalyov, Integrated production scheduling and batch delivery with fixed departure times and inventory holding costs, International Journal of Production Research, 55 (2017), 6193-6206.  doi: 10.1080/00207543.2017.1346323. [2] A. Agnetis, P. B. Mirchandani, D. Pacciarelli and A. Pacifici, Scheduling problems with two competing agents, Operations Research, 52 (2004), 229-242.  doi: 10.1287/opre.1030.0092. [3] K. R. Baker and J. C. Smith, A multiple-criterion model for machine scheduling, Journal of Scheduling, 6 (2003), 7-16.  doi: 10.1023/A:1022231419049. [4] Z.-L. Chen, Integrated production and outbound distribution scheduling: Review and extensions, Operations Research, 58 (2010), 130-148.  doi: 10.1287/opre.1080.0688. [5] E. Gerstl and G. Mosheiov, Single machine just-in-time scheduling problems with two competing agents, Naval Research Logistics, 61 (2014), 1-16.  doi: 10.1002/nav.21562. [6] A. M. Fathollahi-Fard, M. Hajiaghaei-Keshteli, G. Tian and Z. Li, An adaptive Lagrangian relaxation-based algorithm for a coordinated water supply and wastewater collection network design problem, Information Sciences, 512 (2020), 1335-1359.  doi: 10.1016/j.ins.2019.10.062. [7] N. G. Hall, M. Lesaoana and C. N. Potts, Scheduling with fixed delivery dates, Operations Research, 49 (2001), 134-144.  doi: 10.1287/opre.49.1.134.11192. [8] N. G. Hall and C. N. Potts, Supply chain scheduling: Batching and delivery, Operations Research, 51 (2003), 566-584.  doi: 10.1287/opre.51.4.566.16106. [9] D. Han, Y. Yang, D. Wang, T. C. E. Cheng and Y. Yin, Integrated production, inventory, and outbound distribution operations with fixed departure times in a three-stage supply chain, Transportation Research Part E: Logistics and Transportation Review, 125 (2019), 334-347.  doi: 10.1016/j.tre.2019.03.014. [10] D. Hermelina, J.-M. Kubitza, D. Shabtay, N. Talmon and G. J. Woeginger, Scheduling two agents on a single machine: A parameterized analysis of $NP$-hard problems, Omega, 83 (2011), 275-286.  doi: 10.1016/j.omega.2018.08.001. [11] M. E. Johnson, Learning from toys: Lessons in managing supply chain risk from the toy industry, California Management Review, 43 (2001), 106-124.  doi: 10.2307/41166091. [12] M. Y. Kovalyov, A. Oulamara and A. Soukhal, Two-agent scheduling with agent specific batches on an unbounded serial batching machine, Journal of Scheduling, 18 (2015), 423-434.  doi: 10.1007/s10951-014-0410-0. [13] J. Y.-T. Leung and Z.-L. Chen, Integrated production and distribution with fixed delivery departure dates, Operations Research Letters, 41 (2013), 290-293.  doi: 10.1016/j.orl.2013.02.006. [14] J. Y.-T. Leung, M. Pinedo and G. Wan, Competitive two agents scheduling and its applications, Operations Research, 58 (2010), 458-469.  doi: 10.1287/opre.1090.0744. [15] F. Li, Z.-L. Chen and L. Tang, Integrated production, inventory and delivery problems: Complexity and algorithms, INFORMS Journal on Computing, 29 (2017), 232-250.  doi: 10.1287/ijoc.2016.0726. [16] S. Li and J. Yuan, Unbounded parallel-batching scheduling with two competitive agents, Journal of Scheduling, 15 (2012), 629-640.  doi: 10.1007/s10951-011-0253-x. [17] H. Matsuo, The weighted total tardiness problem with fixed shipping times and overtime utilization, Operations Research, 36 (1988), 293-307.  doi: 10.1287/opre.36.2.293. [18] R. A. Melo and L. A. Wolsey, Optimizing production and transportation in a commit-to-delivery business mode, European Journal of Operational Research, 203 (2010), 614-618.  doi: 10.1016/j.ejor.2009.09.011. [19] B. Mor and G. Mosheiov, Single machine batch scheduling with two competing agents to minimize total flowtime, European Journal of Operational Research, 215 (2011), 524-531.  doi: 10.1016/j.ejor.2011.06.037. [20] P. Perez-Gonzalez and J. M. Framinan, A common framework and taxonomy for multicriteria scheduling problem with interfering and competing jobs: Multi-agent scheduling problems, European Journal of Operational Research, 235 (2014), 1-16.  doi: 10.1016/j.ejor.2013.09.017. [21] C. N. Potts and M. Y. Kovalyov, Scheduling with batching: A review, European Journal of Operational Research, 120 (2000), 228-249.  doi: 10.1016/S0377-2217(99)00153-8. [22] M. Safaeian, A. M. Fathollahi-Fard, G. Tian, Z. Li and H. Ke, A multi-objective supplier selection and order allocation through incremental discount in a fuzzy environment, Journal of Intelligent & Fuzzy Systems, 37 (2019), 1435-1455.  doi: 10.3233/JIFS-182843. [23] Y. Seddik, C. Gonzales and S. Kedad-Sidhoum, Single machine scheduling with delivery dates and cumulative payoffs, Journal of Scheduling, 16 (2013), 313-329.  doi: 10.1007/s10951-012-0302-0. [24] K. E. Stecke and X. Zhao, Production and transportation integrationfor a make-to-order manufacturing company with a commit-to-delivery business mode, Manufacturing & Service Operations Management, 9 (2007), 206-224.  doi: 10.1287/msom.1060.0138. [25] G. Tian, X. Liu, M. Zhang, Y. Yang, H. Zhang, Y. Lin, F. Ma, X. Wang, T. Qu and Z. Li, Selection of take-back pattern of vehicle reverse logistics in China via Grey-DEMATEL and Fuzzy-VIKOR combined method, Journal of Cleaner Production, 220 (2019), 1088-1100. doi: 10.1016/j.jclepro.2019.01.086. [26] G. Tian, H. Zhang, Y. Feng, H. Jia, C. Zhang, Z. Jiang, Z. Li and P. Li, Operation patterns analysis of automotive components remanufacturing industry development in China, Journal of Cleaner Production, 64 (2017), 1363-1375.  doi: 10.1016/j.jclepro.2017.07.028. [27] G. Wan, S. R. Vakati, J. Y.-T. Leung and M. Pinedo, Scheduling two agents with controllable processing times, European Journal of Operational Research, 205 (2010), 528-539.  doi: 10.1016/j.ejor.2010.01.005. [28] D.-J. Wang, Y. Yin, J. Xu, W. H. Wu, S.-R. Cheng and C.-C. Wu, Some due date determination scheduling problems with two agents on a single machine, International Journal of Production Economics, 168 (2015), 81-90.  doi: 10.1016/j.ijpe.2015.06.018. [29] D. Wang, Y. Yu, H. Qiu, Y. Yin and T. C. E. Cheng, Two-agent scheduling with linear resource-dependent processing times, Naval Research Logistics, 67 (2020), 573-591.  doi: 10.1002/nav.21936. [30] D.-Y. Wang, O. Grunderand and A. E. Moudni, Integrated scheduling of production and distribution operations: A review, International Journal of Industrial and Systems Engineering, 19 (2015), 94-122.  doi: 10.1504/IJISE.2015.065949. [31] W. Wang, G. Tian, M. Chen, F. Tao, C. Zhang, A. Al-Ahmari, Z. Li and Z. Jiang, Dual-objective program and improved artificial bee colony for the optimization of energy-conscious milling parameters subject to multiple constraints, Journal of Cleaner Production, 245 (2020), 118714. doi: 10.1016/j.jclepro.2019.118714. [32] Y. Yin, S.-R. Cheng, T. C. E. Cheng, D.-J. Wang and C.-C. Wu, Just-in-time scheduling with two competing agents on unrelated parallel machines, Omega, 63 (2016), 41-47. doi: 10.1016/j.omega.2015.09.010. [33] Y. Yin, Y. Chen, K. Qin and D. Wang, Two-agent scheduling on unrelated parallel machines with total completion time and weighted number of tardy jobs criteria, Journal of Scheduling, 22 (2019), 315-333.  doi: 10.1007/s10951-018-0583-z. [34] Y. Yin, D. Li, D. Wang and T. C. E. Cheng, Single-machine serial-batch delivery scheduling with two competing agents and due date assignment, Annals of Operations Research, (2018). doi: 10.1007/s10479-018-2839-6. [35] Y. Yin, Y. Wang, T. C. E. Cheng, D. Wang and C. C. Wu, Two-agent single-machine scheduling to minimize the batch delivery cost, Computers & Industrial Engineering, 92 (2016), 16-30. [36] Y. Yin, W. Wang, D. Wang and T. C. E. Cheng, Multi-agent single-machine scheduling and unrestricted due date assignment with a fixed machine unavailability interval, Computers & Industrial Engineering, 111 (2017), 202-215.  doi: 10.1016/j.cie.2017.07.013. [37] Y. Yin, Y. Yang, D. Wang, T. C. E. Cheng and C.-C. Wu, Integrated production, inventory, and batch delivery scheduling with due date assignment and two competing agents, Naval Research Logistics, 65 (2018), 393-409.  doi: 10.1002/nav.21813.

Tables(3)