Document Type : Research Paper
Authors
Department of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran.
Abstract
The Flexible Job shop Scheduling Problem (FJSP), as a Production Scheduling Problem (PSP), is generally an extension of the Job shop Scheduling Problem (JSP). In this paper, the FJSP with reverse flow consisting of two flows of jobs (direct and reverse) at each stage is studied; the first flow initiates in Stage 1 and goes to Stage C (the last stage), and the second flow starts with Stage c and ends up in Stage 1. The aim is to minimize the makespan of the jobs (the maximum completion time). A Mixed Integer Programming (MIP) is presented to model the problem and the Branch and Bound (B&B) method is used to solve the problem. A numerical small-size problem is presented to demonstrate the applicability, for which the Lingo16 software is employed for a solution. Due to the NP-hardness of the problem, a meta-heuristic, namely the Vibration Damping Optimization (VDO) algorithm with tuned parameters using the Taguchi method, is utilized to solve large-scale problems. To validate the results obtained using the proposed solution algorithm in terms of the solution quality and the required computational time, they are compared with those obtained by the Lingo 16 software for small-size problems. Finally, the performance of the proposed algorithm is compared with a Genetic Algorithm (GA) by solving some randomly generated larger-size test problems, based on which the results are analyzed statistically. Computational results confirm the efficiency and effectiveness of the proposed algorithm and show that the VDO algorithm performs well.
Keywords
- Vibration damping optimization
- Scheduling
- Flexible job shop
- Reverse flow
- Mathematical programming
- Genetic algorithm
Main Subjects
[1] Pinedo, M. (1995). Scheduling: theory, algorithms and applications. Prentice-Hall.
[2] Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of operations research, 1(2), 117–129.
[3] Mati, Y., & Xie, X. (2004). The complexity of two-job shop problems with multi-purpose unrelated machines. European journal of operational research, 152(1), 159–169. DOI:10.1016/S0377-2217(02)00675-6
[4] Salema, M. I. G., Barbosa-Povoa, A. P., & Novais, A. Q. (2010). Simultaneous design and planning of supply chains with reverse flows: A generic modelling framework. European journal of operational research, 203(2), 336–349.
[5] Kim, H. J., Lee, D. H., & Xirouchakis, P. (2007). Disassembly scheduling: Literature review and future research directions. International journal of production research, 45(18–19), 4465–4484.
[6] Ilgin, M. A., & Gupta, S. M. (2011). Recovery of sensor embedded washing machines using a multi-kanban controlled disassembly line. Robotics and computer-integrated manufacturing, 27(2), 318–334.
[7] McGovern, S. M., & Gupta, S. M. (2007). A balancing method and genetic algorithm for disassembly line balancing. European journal of operational research, 179(3), 692–708. DOI:10.1016/j.ejor.2005.03.055
[8] Gao, K. Z., Suganthan, P. N., Pan, Q. K., Tasgetiren, M. F., & Sadollah, A. (2016). Artificial bee colony algorithm for scheduling and rescheduling fuzzy flexible job shop problem with new job insertion. Knowledge-based systems, 109, 1–16.
[9] Giglio, D., Paolucci, M., & Roshani, A. (2017). Integrated lot sizing and energy-efficient job shop scheduling problem in manufacturing/remanufacturing systems. Journal of cleaner production, 148, 624–641.
[10] Wu, X., & Sun, Y. (2018). A green scheduling algorithm for flexible job shop with energy-saving measures. Journal of cleaner production, 172, 3249–3264.
[11] Gao, K., Yang, F., Zhou, M., Pan, Q., & Suganthan, P. N. (2018). Flexible job-shop rescheduling for new job insertion by using discrete Jaya algorithm. IEEE transactions on cybernetics, 49(5), 1944–1955.
[12] Gong, G., Deng, Q., Gong, X., Liu, W., & Ren, Q. (2018). A new double flexible job-shop scheduling problem integrating processing time, green production, and human factor indicators. Journal of cleaner production, 174(c), 560–576. DOI:10.1016/j.jclepro.2017.10.188
[13] Meng, L., Zhang, C., Shao, X., & Ren, Y. (2019). MILP models for energy-aware flexible job shop scheduling problem. Journal of cleaner production, 210, 710–723. DOI:10.1016/j.jclepro.2018.11.021
[14] Gong, X., De Pessemier, T., Martens, L., & Joseph, W. (2019). Energy- and labor-aware flexible job shop scheduling under dynamic electricity pricing: A many-objective optimization investigation. Journal of cleaner production, 209, 1078–1094. DOI:10.1016/j.jclepro.2018.10.289
[15] Dondo, R. G., & Méndez, C. A. (2016). Operational planning of forward and reverse logistic activities on multi-echelon supply-chain networks. Computers & chemical engineering, 88, 170–184.
[16] Osmani, A., & Zhang, J. (2017). Multi-period stochastic optimization of a sustainable multi-feedstock second generation bioethanol supply chain − A logistic case study in Midwestern United States. Land use policy, 61, 420–450. DOI:10.1016/j.landusepol.2016.10.028
[17] Giri, B. C., Chakraborty, A., & Maiti, T. (2017). Pricing and return product collection decisions in a closed-loop supply chain with dual-channel in both forward and reverse logistics. Journal of manufacturing systems, 42, 104–123. https://doi.org/10.1016/j.jmsy.2016.11.007
[18] Adenso-Díaz, B., García-Carbajal, S., & Gupta, S. M. (2008). A path-relinking approach for a bi-criteria disassembly sequencing problem. Computers and operations research, 35(12), 3989–3997.
[19] Duta, L., Filip, F. G., & Popescu, C. (2008). Evolutionary programming in disassembly decision making. International journal of computers, communications & control, 3(3), 282–286.
[20] Kim, H. J., Lee, D. H., Xirouchakis, P., & Kwon, O. K. (2009). A branch and bound algorithm for disassembly scheduling with assembly product structure. Journal of the operational research society, 60(3), 419–430. DOI:10.1057/palgrave.jors.2602568
[21] Wan, H. Da, & Gonnuru, V. K. (2013). Disassembly planning and sequencing for end-of-life products with RFID enriched information. Robotics and computer-integrated manufacturing, 29(3), 112–118. DOI:10.1016/j.rcim.2012.05.001
[22] Abdeljaouad, M. A., Bahroun, Z., Omrane, A., & Fondrevelle, J. (2015). Job-shop production scheduling with reverse flows. European journal of operational research, 244(1), 117–128. DOI:10.1016/j.ejor.2015.01.013
[23] Tanimizu, Y., Sakamoto, M., & Nonomiya, H. (2017). A co-evolutionary algorithm for open-shop scheduling with disassembly operations. Procedia cirp, 63, 289–294. DOI:10.1016/j.procir.2017.03.138
[24] Ren, Y., Zhang, C., Zhao, F., Xiao, H., & Tian, G. (2018). An asynchronous parallel disassembly planning based on genetic algorithm. European journal of operational research, 269(2), 647–660.
[25] Aghighi, S., Niaki, S. T. A., Mehdizadeh, E., & Najafi, A. A. (2021). Open-shop production scheduling with reverse flows. Computers and industrial engineering, 153, 107077. DOI:10.1016/j.cie.2020.107077
[26] Mehdizadeh, E., Tavakkoli-Moghaddam, R., & Yazdani, M. (2015). A vibration damping optimization algorithm for a parallel machines scheduling problem with sequence-independent family setup times. Applied mathematical modelling, 39(22), 6845–6859. DOI:10.1016/j.apm.2015.02.027
[27] Aliabadi, M., Jolai, F., Mehdizadeh, E., & Jenabi, M. (2011). A flow shop production planning problem with basic period policy and sequence dependent set up times. Journal of industrial and systems engineering, 5(1), 1–19.
[28] Yazdani, M., Zandieh, M., Tavakkoli-Moghaddam, R., & Jolai, F. (2015). Two meta-heuristic algorithms for the dual-resource constrained flexible job-shop scheduling problem. Scientia iranica, 22(3), 1242–1257.
[29] Alaghebandha, M., Naderi, B., & Mohammadi, M. (2018). Modeling of Scheduling and Economic Lot Sizing In Distributed Permutation Flow Shops with Non-Identical Multi Factory. Modern research in decision making, 3(3), 129–155.
[30] Rashidi Komijan, A., Tavakkoli-Moghaddam, R., & Dalil, S. A. (2021). A mathematical model for an integrated airline eet assignment and crew scheduling problem solved by vibration damping optimization. Scientia iranica, 28(2E), 970–984. DOI:10.24200/sci.2019.51516.2230
[31] Soofi, P., Yazdani, M., Amiri, M., & Adibi, M. A. (2021). Robust fuzzy-stochastic programming model and meta-heuristic algorithms for dual-resource constrained flexible job-shop scheduling problem under machine breakdown. IEEE access, 9, 155740–155762. DOI:10.1109/ACCESS.2021.3126820
[32] Mehdizadeh, E., & Tavakkoli-Moghaddam, R. (2009). Vibration damping optimization algorithm for an identical parallel machine scheduling problem [presentation]. Proceeding of the 2nd international conference of iranian operations research society, babolsar, iran (pp. 20–22).
[33] Mehdizadeh, E., & Nezhad Dadgar, S. (2014). Using vibration damping optimization algorithm for resource constraint project scheduling problem with weighted earliness-tardiness penalties and interval due dates. Economic computation and economic cybernetics studies and research, 48(1). https://www.researchgate.net/profile/Esmaeil-Mehdizadeh/publication/282032450_Using_vibration_damping_optimization_algorithm_for_resource_c
onstraint_project_scheduling_problem_with_weighted_earliness-tardiness_penalties_and_interval_due_dates/links/5601cad408aeb30ba735566e/Using-vibration-damping-optimization-algorithm-for-resource-constraint-project-scheduling-problem-with-weighted-earliness-tardiness-penalties-and-interval-due-dates.pdf
onstraint_project_scheduling_problem_with_weighted_earliness-tardiness_penalties_and_interval_due_dates/links/5601cad408aeb30ba735566e/Using-vibration-damping-optimization-algorithm-for-resource-constraint-project-scheduling-problem-with-weighted-earliness-tardiness-penalties-and-interval-due-dates.pdf
[34] Fattahi, P., Hajipour, V., & Nobari, A. (2015). A bi-objective continuous review inventory control model: Pareto-based meta-heuristic algorithms. Applied soft computing, 32, 211–223.
[35] Holland, J. H. (1992). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. The MIT Press.
[36] Montgomery, D. C. (2017). Design and analysis of experiments. John Wiley & Sons.
[37] Molla-Alizadeh-Zavardehi, S., Hajiaghaei-Keshteli, M., & Tavakkoli-Moghaddam, R. (2011). Solving a capacitated fixed-charge transportation problem by artificial immune and genetic algorithms with a Prüfer number representation. Expert systems with applications, 38(8), 10462–10474. DOI:10.1016/j.eswa.2011.02.093
[38] Molla-Alizadeh-Zavardehi, S., Sadi Nezhad, S., Tavakkoli-Moghaddam, R., & Yazdani, M. (2013). Solving a fuzzy fixed charge solid transportation problem by metaheuristics. Mathematical and computer modelling, 57(5–6), 1543–1558. DOI:10.1016/j.mcm.2012.12.031
)