Document Type : Research Paper
Authors
1 Ph.D. Student, Department of Industrial Engineering, Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran
2 Assistant Prof., Department of Industrial Engineering, Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran
3 Associate Prof., Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Tehran, Iran
4 Assistant Prof., Department of Industrial Engineering, Golpayegan University of Technology, Golpayegan, Iran
Abstract
In the real world, firms with hybrid flow-shop manufacturing environment generally face
the human resource constraint, salary cost increasment and efforts to make better use of
labor, in addition to machine constraint. Given the limitations of these resources, product
delivery requierements to customers have made the job rejection essential in order to meet
distinct customer requirements. Therefore, this research has studied the dual resource
constrained hybrid flow-shop scheduling problem with job rejection in order to minimize
the total net cost (the sum of the total rejection cost and the total tardiness cost of jobs)
which is widely used in many industries. In this article, a mixed integer linear programming
model has developed for the research problem. In addition, an improved sooty tern
optimization algorithm (ISTOA) has proposed to solve the large-sized problems as well as
a decoding method due to the NP-hardness of the problem. In order to evaluate the
proposed optimization algorithm, five well-known algorithms in the literature including
(immunoglobulin-based artificial immune system (IAIS), genetic algorithm (GA), discrete
artificial bee colony (DABC), improved fruit fly optimization (IFFO), effective modified
migrating birds optimization (EMBO)) have adapted with the proposed problem. Finally,
the performance of the proposed optimization algorithm has investigated against the
adapted algorithms. Results and evaluations show the good performance of the improved
sooty tern optimization algorithm.
Keywords
یزدانی، مهدی؛ زندیه، مصطفی؛ توکلی مقدم؛ رضا (1393). «یک الگوریتم فرا ابتکاری ترکیبی برای مسئله زمانبندی کار کارگاهی منعطف با منابع دوگانه محدود انسان و ماشین». فصلنامه مطالعات مدیریت صنعتی، 12(33)، 74-43.
Asgari, T. M., & Zandieh, M. (2014). A cloud-based simulated annealing algorithm for order acceptance problem with weighted tardiness penalties in permutation flow shop scheduling. Journal of industrial engineering and management studies (JIEMS), 1(1): 1-19.
Andrade-Pineda, J. L., Canca, D., Gonzalez-R, P. L., & Calle, M. Scheduling a dual-resource flexible job shop with makespan and due date-related criteria. Annals of Operations Research, 1-31.
Bartal, Y., Leonardi, S., Marchetti-Spaccamela, A., Sgall, J., & Stougie, L. (2000). Multiprocessor scheduling with rejection. SIAM Journal on Discrete Mathematics, 13(1), 64-78.
Cordone, R., & Hosteins, P. (2019). A bi-objective model for the single-machine scheduling problem with rejection cost and total tardiness minimization. Computers & Operations Research, 102, 130-140.
Dabiri, M., Darestani, S. A., & Naderi, B. (2019). Multi-machine flow shop scheduling problems with rejection using genetic algorithm. International Journal of Services and Operations Management, 32(2), 158-172.
Dudek, R. A., Panwalkar, S. S., & Smith, M. L. (1992). The lessons of flowshop scheduling research. Operations Research, 40(1), 7-13.
Dhiman, G., & Kaur, A. (2019). STOA: A bio-inspired based optimization algorithm for industrial engineering problems. Engineering Applications of Artificial Intelligence, 82, 148-174.
Emami, S., Sabbagh, M., & Moslehi, G. (2016). A Lagrangian relaxation algorithm for order acceptance and scheduling problem: a globalised robust optimisation approach. International Journal of Computer Integrated Manufacturing, 29(5), 535-560.
Esmaeilbeigi, R., Charkhgard, P., & Charkhgard, H. (2016). Order acceptance and scheduling problems in two-machine flow shops: new mixed integer programming formulations. European Journal of Operational Research, 251(2), 419-431.
Framinan, J. M., Leisten, R., & García, R. R. (2014). Manufacturing scheduling systems. An integrated view on Models, Methods and Tools, 51-63.
Figielska, E. (2018). Scheduling in a two-stage flowshop with parallel unrelated machines at each stage and shared resources. Computers & Industrial Engineering, 126, 435-450.
Geramipour, S., Moslehi, G., & Reisi-Nafchi, M. (2017). Maximizing the profit in customer’s order acceptance and scheduling problem with weighted tardiness penalty. Journal of the Operational Research Society, 68(1), 89-101.
Gupta, J. N. (1988). Two-stage, hybrid flowshop scheduling problem. Journal of the operational Research Society, 39(4), 359-364.
Gao, L., & Pan, Q. K. (2016). A shuffled multi-swarm micro-migrating birds optimizer for a multi-resource-constrained flexible job shop scheduling problem. Information Sciences, 372, 655-676.
Gong, G., Chiong, R., Deng, Q., Han, W., Zhang, L., Lin, W., & Li, K. (2019). Energy-efficient flexible flow shop scheduling with worker flexibility. Expert Systems with Applications, 112902.
Gong, X., Deng, Q., Gong, G., Liu, W., & Ren, Q. (2018). A memetic algorithm for multi-objective flexible job-shop problem with worker flexibility. International Journal of Production Research, 56(7), 2506-2522.
Johnson, S. M. (1954). Optimal two‐and three‐stage production schedules with setup times included. Naval research logistics quarterly, 1(1), 61-68.
Jan, D., & W Patrick, N. (2009). Ergonomics contributions to company strategies. Applied Ergonomics, 40, 745-752.
Lin, S. W., & Ying, K. C. (2015). Order acceptance and scheduling to maximize total net revenue in permutation flowshops with weighted tardiness. Applied Soft Computing, 30, 462-474.
Lei, D., & Guo, X. (2015). A parallel neighborhood search for order acceptance and scheduling in flow shop environment. International Journal of Production Economics, 165, 12-18.
Li, J., Huang, Y., & Niu, X. (2016). A branch population genetic algorithm for dual-resource constrained job shop scheduling problem. Computers & Industrial Engineering, 102, 113-131.
Lin, H. T., & Liao, C. J. (2003). A case study in a two-stage hybrid flow shop with setup time and dedicated machines. International Journal of Production Economics, 86(2), 133-143.
Lei, D., & Guo, X. (2014). Variable neighbourhood search for dual-resource constrained flexible job shop scheduling. International Journal of Production Research, 52(9), 2519-2529.
Montgomery, D. C. (2005). Design and Analysis of Experiments, Six Edition, John Wiley&Sons.
Mehravaran, Y., & Logendran, R. (2013). Non-permutation flowshop scheduling with dual resources. Expert Systems with Applications, 40(13), 5061-5076.
Meng, L., Zhang, C., Zhang, B., & Ren, Y. (2019). Mathematical Modeling and Optimization of Energy-Conscious Flexible Job Shop Scheduling Problem With Worker Flexibility. IEEE Access.
Naderi, B., Gohari, S., & Yazdani, M. (2014). Hybrid flexible flowshop problems: Models and solution methods. Applied Mathematical Modelling, 38(24), 5767-5780.
Nguyen S, Zhang M, Johnston M (2014) Enhancing branch-and-bound algorithms for order acceptance and scheduling with genetic programming. In: Nicolau M, Krawiec K, Heywood MI, Castelli M, Garcia-Sanchez P, Merelo JJ, Rivas Santos VM, Sim K (eds) Genetic programming, 1st edn. Springer, Berlin, pp 124–136
Nguyen, S., Zhang, M., Johnston, M. (2014) A sequential genetic programming method to learn forward construction heuristics for order acceptance and scheduling. In: 2014 IEEE Congress on Evolutionary Computation (CEC). IEEE, pp. 1824–1831.
- Mohsen, M. Iraj, Multi-job lot streaming to minimize the weighted completion time in a hybrid flow shop scheduling problem with work shift constraint, International Journal of Advanced Manufacturing Technology, 70 (2014) 501-514.
Pan, Q. K., Gao, L., Li, X. Y., & Gao, K. Z. (2017). Effective metaheuristics for scheduling a hybrid flowshop with sequence-dependent setup times. Applied Mathematics and Computation, 303, 89-112.
Pan, Q. K., Ruiz, R., & Alfaro-Fernández, P. (2017). Iterated search methods for earliness and tardiness minimization in hybrid flowshops with due windows. Computers & Operations Research, 80, 50-60.
Pan, Q. K., Wang, L., Li, J. Q., & Duan, J. H. (2014). A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation. Omega, 45, 42-56.
Pan, Q. K., Wang, L., Mao, K., Zhao, J. H., & Zhang, M. (2012). An effective artificial bee colony algorithm for a real-world hybrid flowshop problem in steelmaking process. IEEE Transactions on Automation Science and Engineering, 10(2), 307-322.
Quadt, D., & Kuhn, H. (2005). Conceptual framework for lot-sizing and scheduling of flexible flow lines. International Journal of Production Research, 43(11), 2291-2308.
Ruiz, R., & Vázquez-Rodríguez, J. A. (2010). The hybrid flow shop scheduling problem. European journal of operational research, 205(1), 1-18.
Ruiz, R., & Maroto, C. (2006). A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility. European Journal of Operational Research, 169(3), 781-800.
Silva, Y. L. T., Subramanian, A., & Pessoa, A. A. (2018). Exact and heuristic algorithms for order acceptance and scheduling with sequence-dependent setup times. Computers & Operations Research, 90, 142-160.
Shabtay, D., & Gasper, N. (2012). Two-machine flow-shop scheduling with rejection. Computers & Operations Research, 39(5), 1087-1096.
Shahvari, O., & Logendran, R. (2017). A bi-objective batch processing problem with dual-resources on unrelated-parallel machines. Applied Soft Computing, 61, 174-192.
Silva, Y. L. T., Subramanian, A., & Pessoa, A. A. (2018). Exact and heuristic algorithms for order acceptance and scheduling with sequence-dependent setup times. Computers & Operations Research, 90, 142-160.
Thevenin, S., Zufferey, N., & Widmer, M. (2015). Metaheuristics for a scheduling problem with rejection and tardiness penalties. Journal of Scheduling, 18(1), 89-105.
Thevenin, S., Zufferey, N., & Widmer, M. (2016). Order acceptance and scheduling with earliness and tardiness penalties. Journal of Heuristics, 22(6), 849-890.
Thevenin, S., & Zufferey, N. (2019). Learning Variable Neighborhood Search for a scheduling problem with time windows and rejections. Discrete Applied Mathematics, 261, 344-353.
Udo, G. G., & Ebiefung, A. A. (1999). Human factors affecting the success of advanced manufacturing systems. Computers & Industrial Engineering, 37, 297-300.
Wang J., Zhuang X., Wu B. (2017) A New Model and Method for Order Selection Problems in Flow-Shop Production. In: Choi TM., Gao J., Lambert J., Ng CK., Wang J. (eds) Optimization and Control for Systems in the Big-Data Era. International Series in Operations Research & Management Science, vol 252. Springer, Cham
Wang, S., & Ye, B. (2019). Exact methods for order acceptance and scheduling on unrelated parallel machines. Computers & Operations Research, 104, 159-173.
Wang, S., & Ye, B. (2019). Exact methods for order acceptance and scheduling on unrelated parallel machines. Computers & Operations Research, 104, 159-173.
Waldherr, S., & Knust, S. (2017). Decomposition algorithms for synchronous flow shop problems with additional resources and setup times. European Journal of Operational Research, 259(3), 847-863.
Xu, L., Wang, Q., & Huang, S. (2015). Dynamic order acceptance and scheduling problem with sequence-dependent setup time. International Journal of Production Research, 53(19), 5797-5808.
Xiao, Y., Yuan, Y., Zhang, R. Q., & Konak, A. (2015). Non-permutation flow shop scheduling with order acceptance and weighted tardiness. Applied Mathematics and Computation, 270, 312-333.
Xie, X., & Wang, X. (2016). An enhanced ABC algorithm for single machine order acceptance and scheduling with class setups. Applied Soft Computing, 44, 255-266.
Xiao, Y., Yuan, Y., Zhang, R. Q., & Konak, A. (2015). Non-permutation flow shop scheduling with order acceptance and weighted tardiness. Applied Mathematics and Computation, 270, 312-333.
Yavari, M., Marvi, M. & Akbari, A.H. (2019). Semi-permutation-based genetic algorithm for order acceptance and scheduling in two-stage assembly problem. Neural Comput & Applic doi:10.1007/s00521-019-04027-w
Yazdani, M., Zandieh, M., & Tavakkoli-Moghaddam, R. (2019). Evolutionary algorithms for multi-objective dual-resource constrained flexible job-shop scheduling problem. OPSEARCH, 1-24.
Yu, C., Semeraro, Q., & Matta, A. (2018). A genetic algorithm for the hybrid flow shop scheduling with unrelated machines and machine eligibility. Computers & Operations Research, 100, 211-229.
Zhang, B., Pan, Q. K., Gao, L., Zhang, X. L., Sang, H. Y., & Li, J. Q. (2017). An effective modified migrating birds optimization for hybrid flowshop scheduling problem with lot streaming. Applied Soft Computing, 52, 14-27.
Zohali, H., Naderi, B., & Mohammadi, M. (2019). The economic lot scheduling problem in limited-buffer flexible flow shops: Mathematical models and a discrete fruit fly algorithm. Applied Soft Computing, 80, 904-919.
Zhang, J., Wang, W., & Xu, X. (2017). A hybrid discrete particle swarm optimization for dual-resource constrained job shop scheduling with resource flexibility. Journal of Intelligent Manufacturing, 28(8), 1961-1972.
Zheng, X. L., & Wang, L. (2016). A knowledge-guided fruit fly optimization algorithm for dual resource constrained flexible job-shop scheduling problem. International Journal of Production Research, 54(18), 5554-5566.
)