A Hybrid Bee Algorithm for Two-Machine Flow-Shop Scheduling Problems with Batch Delivery

Document Type : Research Paper

Authors

1 Industrial engineering and management, Shahrood University of Technology

2 Master graduated of industrial engineering, Iran university of science and technology

10.22070/jqepo.2020.5317.1143

Abstract

Because of the high costs for the delivery, manufacturers are generally needed to dispatch their products in a batch delivery system. However, using such a system leads to some adverse effects, such as increasing the number of tardy jobs. The current paper investigates the two-machine flow-shop scheduling problem where jobs are processed in series on two stages and then dispatched to customers in batches. The objective is to minimize the batch delivery cost and tardiness cost related to the number of tardy jobs. First, a mixed-integer linear programming model (MILP) is proposed to explain this problem. Because the problem under consideration is NP-hard, the MILP model cannot solve large-size instances in a reasonable running time. Some metaheuristic algorithms are provided to solve the large-size instances, including BA, PSO, GA, and a novel Hybrid Bees Algorithm (HBA). Using Friedman and Wilcoxon signed-ranks tests, these intelligent algorithms are compared, and the results are analyzed. The results indicate that the HBA provides the best performance for large-size problems.

Keywords

References

Ahmadizar, F., & Farhadi, S. (2015). Single-machine batch delivery scheduling with job release dates, due windows and earliness, tardiness, holding and delivery costs. Computers & Operations Research, 53, 194-205.
Akbari, R., Mohammadi, M., & Ziarati, K. (2010). A novel bee swarm optimization algorithm for numerical function optimization. Journal of Communications in Nonlinear Science and Numerical Simulation, 15, 3142–3155.
Assarzadegan, P., & Rasti-Barzoki, M. (2016). Minimizing sum of the due date assignment costs, maximum tardiness and distribution costs in a supply chain scheduling problem. Applied Soft Computing, 47, 343-356.
Basir, S. A., Mazdeh, M. M., & Namakshenas, M. (2018). Bi-level genetic algorithms for a two-stage assembly flow-shop scheduling problem with batch delivery system. Computers & Industrial Engineering, 126, 217-231.
Bulfin, R. L., & M'Hallah, R. (2003). Minimizing the weighted number of tardy jobs on a two-machine  ow shop. Computers & Operations Research, 30, 1887–1900.
Chamnanlor, C., Sethanan, K., Chien, C.-F., & Gen, M. (2014). Re-entrant flow shop scheduling problem with time windows using hybrid genetic algorithm based on auto-tuning strategy. International Journal of Production Research, 52(9), 2612-2629.
Chen, D., Batson, R., & Dang, Y. (2011). Applied integer programming: modeling and solution. 2011. In: John Wiley & Sons.
Cheng, B. Y., Leung, J. T., Li, K., & Yang, S. L. (2015). Single batch machine scheduling with deliveries. Naval Research Logistics (NRL), 62(6), 470-482.
Cheng, T. C. E., Gordon, V. S., & Kovalyov, M. Y. (1996). Single machine scheduling with batch deliveries. European Journal of Operational Research, 94(2), 277-283.
Chun-Feng, W., Kui, L., & Pei-Ping, S. (2014). Hybrid artificial bee colony algorithm and particle swarm search for global optimization. Mathematical Problems in Engineering, 2014.
Ding, J.-Y., Song, S., Gupta, J. N., Zhang, R., Chiong, R., & Wu, C. (2015). An improved iterated greedy algorithm with a Tabu-based reconstruction strategy for the no-wait flowshop scheduling problem. Applied Soft Computing, 30, 604-613.
Duan, H.-b., Xu, C.-f., & Xing, Z.-h. (2010). A hybrid artificial bee colony optimization and quantum evolutionary algorithm for continuous optimization problems. International Journal of Neural Systems, 20(01), 39-50.
Ganji, M., Kazemipoor, H., Molana, S. M. H., & Sajadi, S. M. (2020). A green multi-objective integrated scheduling of production and distribution with heterogeneous fleet vehicle routing and time windows. Journal of Cleaner Production, 120824.
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey. Annals of Discrete Mathematics, 287-326.
Guanlong, D., Zhenhao, X., & Xingsheng, G. (2012). A discrete artificial bee colony algorithm for minimizing the total flow time in the blocking flow shop scheduling. Chinese Journal of Chemical Engineering, 20(6), 1067-1073.
Gupta, J., & Hariri, A. (1997). Two machine  ow shop to minimize number of tardy jobs. Journal of the Operational Research Society, 48, 212–220.
Gupta, J. N., & Stafford Jr, E. F. (2006). Flowshop scheduling research after five decades. European Journal of Operational Research, 169(3), 699-711.
Hall, N., & Potts, C. (2005). The coordination of scheduling and batch deliveries. Annals of Operations Research, 135(1), 41-64.
Hall, N. G., & Potts, C. N. (2003). Supply chain scheduling: Batching and delivery. Operations Research, 51(4), 566-584.
Hamidinia, A., Khakabimamaghani, S., Mahdavi Mazdeh, M., & Jafari, M. (2011). A genetic algorithm for minimizing total tardiness/earliness of weighted jobs in a batched delivery system. Computers & Industrial Engineering, doi:10.1016/j.cie.2011.1008.1014.
Han, Y.-Y., Gong, D., & Sun, X. (2015). A discrete artificial bee colony algorithm incorporating differential evolution for the flow-shop scheduling problem with blocking. Engineering Optimization, 47(7), 927-946.
Hariri, A., & Potts, C. (1989). A branch and bound algorithm to minimize number of late jobs in a permutation  ow shop. European Journal of Operational Research, 38, 228–237.
Herrmann, J. W., & Lee, C.-Y. (1993). On scheduling to minimize earliness-tardiness and batch delivery costs with a common due date European Journal of Operational Research, 70(3), 272-288.
Ji, M., He, Y., & Cheng, T. C. E. (2007). Batch delivery scheduling with batch delivery cost on a single machine. European Journal of Operational Research, 176, 745–755.
Jia, Z.-h., Zhuo, X.-x., Leung, J. Y., & Li, K. (2019). Integrated production and transportation on parallel batch machines to minimize total weighted delivery time. Computers & Operations Research, 102, 39-51.
Johnson, S. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1), 61-68.
Jolai, F., Asefi, H., Rabiee, M., & Ramezani, P. (2013). Bi-objective simulated annealing approaches for no-wait two-stage flexible flow shop scheduling problem. Scientia Iranica, 20(3), 861-872.
Joo, C. M., & Kim, B. S. (2019). Variable Neighborhood Search Algorithms for an Integrated Manufacturing and Batch Delivery Scheduling Minimizing Total Tardiness. Applied Sciences, 9(21), 4702.
Karaboga, D. (2005). An  idea  based  on  honey  bee  swarm  for  numerical optimization. Erciyes  University.
Karaboga, D., Gorkemli, B., Ozturk, C., & Karaboga, N. (2014). A comprehensive survey: artificial bee colony (ABC) algorithm and applications. Artificial Intelligence Review, 42(1), 21-57.
Karaboga, D., & Kaya, E. (2016). An adaptive and hybrid artificial bee colony algorithm (aABC) for ANFIS training. Applied Soft Computing, 49, 423-436.
Kazemi, H., Mazdeh, M. M., & Rostami, M. (2017). The two stage assembly flow-shop scheduling problem with batching and delivery. Engineering Applications of Artificial Intelligence, 63, 98-107.
Kefayat, M., Ara, A. L., & Niaki, S. N. (2015). A hybrid of ant colony optimization and artificial bee colony algorithm for probabilistic optimal placement and sizing of distributed energy resources. Energy Conversion and Management, 92, 149-161.
Kennedy, J., & Eberhart, R. C. (1995). Particle swarm optimization. Paper presented at the IEEE International Conference, Neural Networks.
Kennedy, J., & Eberhart, R. C. (1997). A discrete binary version of the particle swarm algorithm. Paper presented at the the World Multiconference on Systemics, NJ.
Lee, C.-Y., & Chen, Z.-L. (2001). Machine scheduling with transportation considerations. JOURNAL OF SCHEDULING, 4, 3-24.
Lenstra, J. K., Karl, A. H. G. R., & Brucker, P. (1977). Complexity of machine scheduling problems. Ann.  of Discrete Math, 343-351.
Li, J.-q., Xie, S.-x., Pan, Q.-k., & Wang, S. (2011). A hybrid artificial bee colony algorithm for flexible job shop scheduling problems. International Journal of Computers Communications & Control, 6(2), 286-296.
Low, C., Hsu, C.-J., & Su, C.-T. (2010). A modified particle swarm optimization algorithm for a single-machine scheduling problem with periodic maintenance. Expert Systems with Applications, 37, 6429–6434.
Mahadevan, B. (2015). Operations management: Theory and practice: Pearson Education India.
Marichelvam, M., Prabaharan, T., & Yang, X.-S. (2014a). Improved cuckoo search algorithm for hybrid flow shop scheduling problems to minimize makespan. Applied Soft Computing, 19, 93-101.
Marichelvam, M. K., Prabaharan, T., & Yang, X. S. (2014b). A discrete firefly algorithm for the multi-objective hybrid flowshop scheduling problems. IEEE transactions on evolutionary computation, 18(2), 301-305.
Marinakis, Y., Marinaki, M., & Matsatsinis, N. (2009). A hybrid discrete artificial bee colony-GRASP algorithm for clustering. Paper presented at the Computers & Industrial Engineering, 2009. CIE 2009. International Conference on.
Mazdeh, M. M., & Rostami, M. (2014). A branch-and-bound algorithm for two-machine flow-shop scheduling problems with batch delivery costs. International Journal of Systems Science: Operations & Logistics, 1(2), 94-104.
Mazdeh, M. M., Rostami, M., & Namaki, M. H. (2013). Minimizing maximum tardiness and delivery costs in a batched delivery system. Computers & Industrial Engineering, 66, 675–682.
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, 74–86.
Mazdeh, M. M., Sarhadi, M., & Hindi, K. S. (2008). A branch-and-bound algorithm for single-machine scheduling with batch delivery and job release times. Computers & Operations Research, 35, 1099–1111.
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, 563–570.
Moore, J. M. (1968). Sequencing n jobs on one machine to minimize the number of late jobs. Management Science, 15(1), 102–109.
Moumene, K., & Ferland, J. A. (2009). Activity list representation for a generalization of the resource-constrained project scheduling problem. European Journal of Operational Research, 199(1), 46-54.
Osman, I. (2003). Meta-heuristics: Models, analysis, and directions. Paper presented at the A tutorial paper presented at the joint EURO/INFORMS Meeting, Istanbul, July.
Panwalkar, S., Smith, M. L., & Koulamas, C. (2013). Review of the ordered and proportionate flow shop scheduling research. Naval Research Logistics (NRL), 60(1), 46-55.
Pham, D., Ghanbarzadeh, A., Koc, E., Otri, S., Rahim, S., & Zaidi, M. (2005). The Bees Algorithm. Technical Note. Cardiff University.
Preux, P., & Talbi, E. G. (1999). Towards hybrid evolutionary algorithms. International Transactions in Operational Research, 6(6), 557-570. doi:10.1111/j.1475-3995.1999.tb00173.x.
Pundoor, G., & Chen, Z.-L. (2005). Scheduling a Production–Distribution System To Optimize the Tradeoff between Delivery Tardiness and Distribution Cost. Wiley InterScience.
Rasti-Barzoki, M., & Hejazi, S. R. (2013). 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(2), 345-357. doi:http://dx.doi.org/10.1016/j.ejor.2013.01.002.
Rasti-Barzoki, M., Hejazi, S. R., & Mazdeh, M. M. (2013). A branch and bound algorithm to minimize the total weighed number of tardy jobs and delivery costs. Applied Mathematical Modelling, 37(7), 4924-4937.
Riahi, V., & Kazemi, M. (2016). A new hybrid ant colony algorithm for scheduling of no-wait flowshop. Operational Research, 1-20.
Rostami, M., Kheirandish, O., & Ansari, N. (2015). Minimizing maximum tardiness and delivery costs with batch delivery and job release times. Applied Mathematical Modelling, 39(16), 4909-4927.
Rostami, M., Nikravesh, S., & Shahin, M. (2018). Minimizing total weighted completion and batch delivery times with machine deterioration and learning effect: a case study from wax production. Operational Research. doi:10.1007/s12351-018-0373-6.
Shabtay, D. (2010). Scheduling and due date assignment to minimize earliness, tardiness, holding, due date assignment and batch delivery costs. Int. J. Production Economics, 123, 235–242.
Soukhal, A., Oulamara, A., & Martineau, P. (2005). Complexity of flow shop scheduling problems with transportation constraints. European Journal of Operational Research, 161, 32-41.
Steiner, G., & Zhang, R. (2011). Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries. Annals of Operations Research, 191(1), 171-181.
Tasgetiren, M. F., Pan, Q.-K., Suganthan, P. N., & Chen, A. H. (2011). A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops. Information Sciences, 181(16), 3459-3475.
Thakare, A. D., & Chaudhari, M. S. M. (2012). Introducing a Hybrid Swarm Intelligence Based Technique for Document Clustering. International Journal of Engineering Research and Applications, 1455-1459.
Wang, K., Luo, H., Liu, F., & Yue, X. (2017). Permutation flow shop scheduling with batch delivery to multiple customers in supply chains. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 48(10), 1826-1837.
Wu, B., Qian, C., Ni, W., & Fan, S. (2012). Hybrid harmony search and artificial bee colony algorithm for global optimization problems. Computers & Mathematics with Applications, 64(8), 2621-2634.
Yenisey, M. M., & Yagmahan, B. (2014). Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends. Omega, 45, 119-135.
Yildiz, A. R. (2013). A new hybrid artificial bee colony algorithm for robust optimal design and manufacturing. Applied Soft Computing, 13(5), 2906-2912.
Yin, Y., Cheng, T., Hsu, C.-J., & Wu, C.-C. (2013). Single-machine batch delivery scheduling with an assignable common due window. Omega, 41(2), 216-225.
Zhao, H., Pei, Z., Jiang, J., Guan, R., Wang, C., & Shi, X. (2010). A hybrid swarm intelligent method based on genetic algorithm and artificial bee colony. Advances in Swarm Intelligence, 558-565.
Journal of Quality Engineering and Production Optimization
Volume 5, Issue 1
June 2020
Pages 137-164

Files

Share

How to cite

Statistics