A Branch and Bound for single machine stochastic batch scheduling with delivery costs. A Chance Constraint approach (Case study in Iran)
Subject Areas : Mathematical Engineering
حمیدرضا حداد
1
(Phd of production management, Faculty of Management, University of Tehran)
Keywords: Branch and Bound, single machine, Chance Constraint Programming, batch scheduling,
Abstract :
This paper study a single machine stochastic scheduling problem based on an Iranian real case study in Saipa company in which the objective is to minimize total completion times and delivery costs. According to existence data sets of this company the processing times follows a Normal distribution and based on the managerial decisions two objectives have to be achieved simultaneously including total completion times and controlling tardiness values so that their values are lower than an specified penalty. So, a Chance Constraint Programming (CCP) approach is employed and a mathematical model is presented. In order to solve the problem a Branch and Bound (B&B) method is used to solve the problem optimally and a Particle Swarm Optimization (PSO) metaheuristic is used to find near optimal solutions for large scales. The results show that using the proposed mathematical model and solution approach, could increase the effectiveness and efficiency of production line as 16 to 40 percent. Computational experiments validate the accuracy of proposed method.
Aschauer, A., Roetzer, F., Steinboeck, A., & Kugi, A. (2020). Efficient scheduling of a stochastic no-wait job shop with controllable processing times. Expert Systems with Applications, 162, 113879.
Cheng, T. E., Janiak, A., & Kovalyov, M. Y. (2001). Single machine batch scheduling with resource dependent setup and processing times. European Journal of Operational Research, 135(1), 177-183.
Cheng, T. C. E., & Kovalyov, M. Y. (2001). Single machine batch scheduling with sequential job processing. IIE Transactions, 33(5), 413-420.
Chung, S. H., Yang, M. H., & Kao, C. K. (2012). Analyzing the effects of family-based scheduling rule on reducing capacity loss of single machine with uncertain job arrivals. Expert Systems with Applications, 39(1), 1231-1242.
Lin, H. T. (2010). Personnel selection using analytic network process and fuzzy data envelopment analysis approaches. Computers & Industrial Engineering, 59(4), 937-944.
Ishii, H., Li, X., & Masuda, T. (2010, July). Single machine batch scheduling problem with fuzzy batch size. In The 40th International Conference on Computers & Indutrial Engineering (pp. 1-5). IEEE.
Kennedy, J., & Eberhart, R. (1995, November). Particle swarm optimization. In Proceedings of ICNN'95-international conference on neural networks (Vol. 4, pp. 1942-1948). IEEE.
Mahdavi Mazdeh, M., Hamidinia, A., & Karamouzian, A. (2011). A mathematical model for weighted tardy jobs scheduling problem with a batched delivery system. International Journal of Industrial Engineering Computations, 2(3), 491-498.
Mazdeh, M. M., Sarhadi, M., & Hindi, K. S. (2007). A branch-and-bound algorithm for single-machine scheduling with batch delivery minimizing flow times and delivery costs. European Journal of Operational Research, 183(1), 74-86.
Mazdeh, M. M., Shashaani, S., Ashouri, A., & Hindi, K. S. (2011). Single-machine batch scheduling minimizing weighted flow times and delivery costs. Applied Mathematical Modelling, 35(1), 563-570.
Melouk, S., Damodaran, P., & Chang, P. Y. (2004). Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing. International journal of production economics, 87(2), 141-147.
Ng, C. T., Cheng, T. E., Yuan, J. J., & Liu, Z. H. (2003). On the single machine serial batching scheduling problem to minimize total completion time with precedence constraints, release dates and identical processing times. Operations Research Letters, 31(4), 323-326.
Ng, C. T., Cheng, T. E., & Yuan, J. J. (2002). A note on the single machine serial batching scheduling problem to minimize maximum lateness with precedence constraints. Operations Research Letters, 30(1), 66-68.
Nong, Q. Q., Ng, C. T., & Cheng, T. E. (2008). The bounded single-machine parallel-batching scheduling problem with family jobs and release dates to minimize makespan. Operations Research Letters, 36(1), 61-66.
Novak, A., Sucha, P., & Hanzalek, Z. (2019). Scheduling with uncertain processing times in mixed-criticality systems. European Journal of Operational Research, 279(3), 687-703.
Potts, C. N., & Kovalyov, M. Y. (2000). Scheduling with batching: A review. European journal of operational research, 120(2), 228-249.
Pei, J., Liu, X., Liao, B., Pardalos, P. M., & Kong, M. (2018). Single-machine scheduling with learning effect and resource-dependent processing times in the serial-batching production. Applied Mathematical Modelling, 58, 245-253.
Rostami, M. (2021). Minimizing maximum tardiness subject to collect the EOL products in a single machine scheduling problem with capacitated batch delivery and pickup systems. Computers & Industrial Engineering, 161, 107634.
Shen, J., & Zhu, K. (2018). An uncertain single machine scheduling problem with periodic maintenance. Knowledge-Based Systems, 144, 32-41.
Tang, L., Zhao, X., Liu, J., & Leung, J. Y. T. (2017). Competitive two-agent scheduling with deteriorating jobs on a single parallel-batching machine. European Journal of Operational Research, 263(2), 401-411.
Tian, J., Fu, R., & Yuan, J. (2007). On-line scheduling with delivery time on a single batch machine. Theoretical Computer Science, 374(1-3), 49-57.
Yuan, J. J., Liu, Z. H., Ng, C. T., & Cheng, T. E. (2004). The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan. Theoretical Computer Science, 320(2-3), 199-212.
Zhang, H., Wu, F., & Yang, Z. (2021). Hybrid approach for a single-batch-processing machine scheduling problem with a just-in-time objective and consideration of non-identical due dates of jobs. Computers & Operations Research, 128, 105194.
Zhou, S., Jin, M., & Du, N. (2020). Energy-efficient scheduling of a single batch processing machine with dynamic job arrival times. Energy, 209, 118420.
Hu, Z., & Hu, G. (2020). Hybrid stochastic and robust optimization model for lot-sizing and scheduling problems under uncertainties. European Journal of Operational Research, 284(2), 485-497.
Zheng, S., Xie, N., & Wu, Q. (2021). Single batch machine scheduling with dual setup times for autoclave molding manufacturing. Computers & Operations Research, 133, 105381.
Zhou, X., & Ning, X. (2021). Maintenance gravity window based opportunistic maintenance scheduling for multi-unit serial systems with stochastic production waits. Reliability Engineering & System Safety, 215, 107828.