Achieving an Optimal Lower Bound for Two Stage Supply Chain Scheduling with Regard to the Different Setup Time

Document Type: Research Paper



In this paper, a two-stage supply-chain scheduling problem including manufacturers and distributors will be investigated and modeled. The objective function is to minimize the makespan, which is equivalent to the completion time of the last job to leave the system. A minimum makespan usually implies a good utilization of the machine(s). In this research, serial batching machines do jobs processing and then the jobs will deliver to customers (in the next stage) for further processing. The capacity of each batch is limited. Delivery unit cost of each batch is fixed and independent of the number of jobs in the batch. Processing and setup time of jobs are varying according to jobs types. The setup time is determined according to jobs type within each batch. The problem has been formulated as a mixed integer-programming model. Finally, a lower bound will be provided. Computational experiments demonstrate the performance of new lower band.


1. Agnetis, A., Hall, N. G., and Pacciarelli, D. (2006). “Supply Chain Scheduling: Sequence Coordination”, Discrete Applied Mathematics, Vol. 154, No. 15. PP. 2044-2063.  

2. Omrani, H., and Adabi, F. (2016). “A Multiple Objective Programming Model for Designing of Supply Chain Network with Efficient Manufacturers and Distributers”, Journal of Industrial Engineering, Vol. 50, No. 2, PP. 261-278.

3. Rahimi, Y. et al. (2015). “Design Model Innovative Performance Evaluation of Suppliers and Contractors in Construction Supply Chain Management”, Journal of Industrial Engineering, Vol. 49, No. 2, PP. 199-210.

4. Tavakoli Moghaddam, R. et al. (2012). “Scheduling an Integrated Production and Air Transportation in Supply Chain with Sequence-Dependent Setup Times”, International Journal of Industrial Engineering and Production Management, Vol. 23, No. 3, PP. 351-362.

5. Potts, C. N., and Kovalyov, M. Y. (2000). “Scheduling with Batching: A Review”, European Journal of Operational Research, Vol. 20. No. 120. PP. 228-249.

6. Xu, R., Chen, H., and Li, X. (2012). “Makespan Minimization on Single Batch-Processing Machine Via Ant Colony Optimization”, Computers and Operations Research, Vol. 39, No. 3, PP. 582-593.

7. Al Salamah, M. (2015). “Constrained Binary Artificial Bee Colony to Minimize the Makespan for Single Machine Batch Processing with Non-Identical Job Sizes”, Applied Soft Computing, Vol. 29, No. 29, PP. 379-385.

8. Cheng, T., and Kahlbacher, H. (1993). “Scheduling with Delivery and Earliness Penalties. Asia-Pacific”, Journal of Operational Research, Vol. 10, No. 2, PP. 145-152.

9. Karimi, N., and Davoudpour, H. (2017). “Integrated Production and Delivery Scheduling for Multi-Factory Supply Chain with Stage-Dependent Inventory Holding Cost”, Computational and Applied Mathematics, Vol. 36, No. 4, PP. 1529-1544.

10. Hall, N. G. and Potts, C. N. (2003). “Supply Chain Scheduling: Batching and Delivery”, Operations Research, Vol. 51, No. 4. PP. 566-584.

11. Yeung, W. K., Choi, T. M., and Cheng, T. (2011). “Supply Chain Scheduling and Coordination with Dual Delivery Modes and Inventory Storage Cost”, International Journal of Production Economics, Vol. 2, No. 132,  PP. 223-229.

12. Hwang, F., Kovalyov, M. Y., and Lin, B. M. (2012). “Total Completion Time Minimization in Two-Machine Flow Shop Scheduling Problems with a Fixed Job Sequence”, Discrete Optimization, Vol. 9, No. 1, PP. 29-39.

13. Hwang, F., and Lin, B. M. (2012). “Two-Stage Assembly-Type Flowshop Batch Scheduling Problem Subject to a Fixed Job Sequence”, Journal of the Operational Research Society, Vol. 6, No. 63, PP. 839-845.

14. Kim, H., Jeong, H. I., and Park, J. (2008). “Integrated Model for Production Planning and Scheduling in a Supply Chain Using Benchmarked Genetic Algorithm”, The International Journal of Advanced Manufacturing Technology, Vol. 39, No. 11 and 12, PP. 1207-1226.

15. Mehravaran, Y., and Logendran, R. (2012). “Non-Permutation Flowshop Scheduling in a Supply Chain with Sequence-Dependent Setup Times”, International Journal of Production Economics, Vol. 2, No. 135, PP. 953-963.

16. Pei, J. et al. (2014). “A Novel Hybrid Dynamic Programming Algorithm for a Two-Stage Supply Chain Scheduling Problem”, In Learning and Intelligent Optimization, Vol. 8426, No.27 , PP. 242-257.

17. Graham, R. L. et al. (1979). “Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey”, Annals of Discrete Mathematics, Vol. ???, No. 5, PP. 287-326.