Article Contents
Article Contents

# Coordination of production and transportation in supply chain scheduling

• This paper investigates a three-stage supply chain scheduling problem in the application area of aluminium production. Particularly, the first and the third stages involve two factories, i.e., the extrusion factory of the supplier and the aging factory of the manufacturer, where serial batching machine and parallel batching machine respectively process jobs in different ways. In the second stage, a single vehicle transports jobs between the two factories. In our research, both setup time and capacity constraints are explicitly considered. For the problem of minimizing the makespan, we formalize it as a mixed integer programming model and prove it to be strongly NP-hard. Considering the computational complexity, we develop two heuristic algorithms applied in two different cases of this problem. Accordingly, two lower bounds are derived, based on which the worst case performance is analyzed. Finally, different scales of random instances are generated to test the performance of the proposed algorithms. The computational results show the effectiveness of the proposed algorithms, especially for large-scale instances.
Mathematics Subject Classification: Primary: 90B35, 90C27; Secondary: 90C59.

 Citation:

•  [1] A. Agnetis, N. G. Hall and D. Pacciarellir, Supply chain scheduling: Sequence coordination, Discrete Applied Mathematics, 154 (2006), 2044-2063.doi: 10.1016/j.dam.2005.04.019. [2] H. Allaoui and A. Artiba, Integrating simulation and optimization to schedule a hybrid flow shop with maintenance constraints, Computers & Industrial Engineering, 47 (2004), 431-450.doi: 10.1016/j.cie.2004.09.002. [3] I. Averbakh and Z. Xue, On-line supply chain scheduling problems with pre-emption, European Journal of Operational Research, 181 (2007), 500-504. [4] J. F. Bard and N. Nananukul, A branch-and-price algorithm for an integrated production and inventory routing problem, Computers & Operations Research, 37 (2010), 2202-2217.doi: 10.1016/j.cor.2010.03.010. [5] J. Behnamian, S. M. T. Fatemi Ghomi, F. Jolai and O. Amirtaheri, Realistic two-stage flowshop batch scheduling problems with transportation capacity and times, Applied Mathematical Modelling, 36 (2012), 723-735.doi: 10.1016/j.apm.2011.07.011. [6] E. Cakici, S. J. Mason and M. E. Kurz, Multi-objective analysis of an integrated supply chain scheduling problem, International Journal of Production Research, 50 (2012), 2624-2638.doi: 10.1080/00207543.2011.578162. [7] F. T. S. Chan, S. H. Chung and P. L. Y. Chan, An adaptive genetic algorithm with dominated genes for distributed scheduling problems, Expert Systems with Applications, 29 (2005), 364-371.doi: 10.1016/j.eswa.2005.04.009. [8] Y. C. Chang, K. H. Chang and T. K. Chang, Applied column generation-based approach to solve supply chain scheduling problems, International Journal of Production Research, 51 (2013), 4070-4086.doi: 10.1080/00207543.2013.774476. [9] Y. C. Chang and Y. C. Lee, Machine scheduling with job delivery coordination, European Journal of Operation Research, 158 (2004), 470-487.doi: 10.1016/S0377-2217(03)00364-3. [10] T. C. E. Cheng and X. Wang, Machine scheduling with job class setup and delivery considerations, Computers & Operations Research, 37 (2010), 1123-1128.doi: 10.1016/j.cor.2009.10.001. [11] P. Chretienne, O. Hazir and S. Kedad-Sidhoum, Integrated batch sizing and scheduling on a single machine, Journal of Scheduling, 14 (2011), 541-555.doi: 10.1007/s10951-011-0229-x. [12] V. S. Gordon and V. A. Strusevich, Single machine scheduling and due date assignment with positionally dependent processing times, European Journal of Operation Research, 198 (2009), 57-62.doi: 10.1016/j.ejor.2008.07.044. [13] R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic machine scheduling: A survey, Annals of Discrete Mathematics, 5 (1979), 287-326.doi: 10.1016/S0167-5060(08)70356-X. [14] O. Grunder, Lot sizing, delivery and scheduling of identical jobs in a single-stage supply chain, International Journal of Innovative Computing Information and Control, 6 (2010), 3657-3668. [15] 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. [16] J. Hurink and S. Knust, Makespan minimization flow-shop problems with transportation times and a single robot, Discrete Applied Mathematics, 112 (2001), 199-216.doi: 10.1016/S0166-218X(00)00316-4. [17] A. S. Jetlund and I. A. Karimi, Improving the logistics of multi-compartment chemical tankers, Computers & Chemical Engineering, 28 (2004), 1267-1283.doi: 10.1016/j.compchemeng.2003.08.009. [18] M. Khalili and R. Tavakoli-Moghadam, A multi-objective electromagnetism algorithm for a bi-objective flowshop scheduling problem, Journal of Manufacturing Systems, 31 (2012), 232-239.doi: 10.1016/j.jmsy.2011.08.002. [19] C. H. Lee, C. J. Liao and C. W. Chao, Scheduling with multi-attribute setup times, Computers & Industrial Engineering, 63 (2012), 494-502.doi: 10.1016/j.cie.2012.04.012. [20] B. M. T. Lin, T. C. E. Cheng and A. S. C. Chou, Scheduling in an assembly-type production chain with batch transfer, Omega-International Journal of Management Science, 35 (2007), 143-151.doi: 10.1016/j.omega.2005.04.004. [21] S. C. Liu and A. Z. Chen, Variable neighborhood search for the inventory routing and scheduling problem in a supply chain, Expert Systems with Applications, 39 (2012), 4149-4159.doi: 10.1016/j.eswa.2011.09.120. [22] M. M. Mazdeh, M. Sarhadi and K. S. Hindi, A branch-and-bound algorithm for single-machine scheduling with batch delivery and job release times, Computers & Operations Research, 35 (2008), 1099-1111.doi: 10.1016/j.cor.2006.07.006. [23] Y. Mehravaran and R. Logendran, Non-permutation flowshop scheduling in a supply chain with sequence-dependent setup times, International Journal of Production Economics, 135 (2012), 953-963.doi: 10.1016/j.ijpe.2011.11.011. [24] C. Moon, Y. H. Lee, C. S. Jeong and Y. Yun, Integrated process planning and scheduling in a supply chain, Computers & Industrial Engineering, 54 (2008), 1048-1061.doi: 10.1016/j.cie.2007.06.018. [25] B. Naderi, A. Ahmadi Javid and F. Jolai, Permutation flowshops with transportation times: Mathematical models and solution methods, International Journal of Advanced Manufacturing Technology, 46 (2010), 631-647.doi: 10.1007/s00170-009-2122-8. [26] B. Naderi, M. Zandieh, A. Khaleghi Ghoshe Balagh and V. Roshanaei, An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness, Expert Systems with Applications, 36 (2009), 9625-9633.doi: 10.1016/j.eswa.2008.09.063. [27] D. Naso, M. Surico, B. Turchiano and U. Kaymak, Genetic algorithms for supply-chain scheduling: A case study in the distribution of ready-mixed concrete, European Journal of Operational Research, 177 (2007), 2069-2099.doi: 10.1016/j.ejor.2005.12.019. [28] P. M. Pardalos and G. C. R. Mauricio (Eds), Handbook of Applied Optimization, Oxford University Press, 2002.doi: 10.1007/978-1-4757-5362-2. [29] P. M. Pardalos, O. V. Shylo and A. Vazacopoulos, Solving job shop scheduling problems utilizing the properties of backbone and "big valley", Computational Optimization and Applications, 47 (2010), 61-76.doi: 10.1007/s10589-008-9206-5. [30] M. Rasti-Barzoki and S. R. Hejazi, Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries for multiple customers in supply chains, European Journal of Operational Research, 228 (2013), 345-357.doi: 10.1016/j.ejor.2013.01.002. [31] M. Rasti-Barzoki, S. R. Hejazi and M. M. Mazdeh, A branch and bound algorithm to minimize the total weighed number of tardy jobs and delivery costs, Applied Mathematical Modelling, 37 (2013), 4924-4937.doi: 10.1016/j.apm.2012.10.001. [32] E. Selvarajah and G. Steiner, Batch scheduling in a two-level supply chain - A focus on the supplier, European Journal of Operational Research, 173 (2006), 226-240.doi: 10.1016/j.ejor.2004.12.007. [33] S. A. Torabi, S. M. T. Fatemi Ghomi and B. Karimi, A hybrid genetic algorithm for the finite horizon economic lot and delivery scheduling in supply chains, European Journal of Operational Research, 173 (2006), 173-189.doi: 10.1016/j.ejor.2004.11.012. [34] H. Xuan and L. Tang, Scheduling a hybrid flowshop with batch production at the last stage, Computers & Operations Research, 34 (2007), 2718-2733.doi: 10.1016/j.cor.2005.10.014. [35] W. K. Yeung, T. M. Choi and T. C. E. Cheng, Supply chain scheduling and coordination with dual delivery modes and inventory storage cost, International Journal of Production Economics, 132 (2011), 223-229.doi: 10.1016/j.ijpe.2011.04.012. [36] A. D. Yimer and K. Demirli, A genetic approach to two-phase optimization of dynamic supply chain scheduling, Computers & Industrial Engineering, 58 (2010), 411-422.doi: 10.1016/j.cie.2009.01.010. [37] S. H. Zegordi, I. N. Kamal Abadi and M. A. Beheshti Nia, A novel genetic algorithm for solving production and transportation scheduling in a two-stage supply chain, Computers & Industrial Engineering, 58 (2010), 373-381.doi: 10.1016/j.cie.2009.06.012. [38] T. Zhang, Y. J. Zhang, Q. P. Zheng and P. M. Pardalos, A hybrid particle swarm optimization and tabu search algorithm for order planning problems of steel factories based on the make-to-stock and make-to-order management architecture, Journal of Industrial and Management Optimization, 7 (2011), 31-51.doi: 10.3934/jimo.2011.7.31.