نوع مقاله : مقاله پژوهشی
نویسندگان
1 دانشجوی دکترای، گروه مهندسی صنایع دانشکده مهندسی صنایع و مکانیک، واحد قزوین، دانشگاه آزاد اسلامی، قزوین، ایران
2 استاد یار، گروه مهندسی صنایع، دانشکده مهندسی صنایع و مکانیک، واحد قزوین، دانشگاه آزاد اسلامی، قزوین، ایران
3 دانشیار، گروه مهندسی صنایع، دانشکده فنی و مهندسی، دانشگاه خوارزمی، تهران، ایران
4 استادیار، گروه مهندسی صنایع، دانشکده فنی و مهندسی گلپایگان، گلپایگان، ایران
چکیده
در دنیای واقعی، بنگاه های اقتصادی با محیط تولیدی جریان کارگاهی ترکیبی عموماً علاوه بر محدودیت در ماشین آلات با محدودیت نیروی انسانی و افزایش هزینه حقوق و دستمزد و تلاش برای استفاده بهتر از نیروی کار روبه‌رو هستند. از جهتی نیازمندی های تحویل مشتریان با توجه به محدودیت های منابع مزبور، استفاده از رد کارها را به منظور اقناع نیازمندی‌های متمایز مشتریان ضروری می‌کند. لذا این تحقیق منابع دوگانه محدود انسان و ماشین را با در نظر گرفتن رد کارها در مساله زمانبندی جریان کارگاهی ترکیبی جهت کمینه سازی هزینه خالص کل (جمع مجموع هزینه های به دست آمده از رد کارها و هزینه جریمه کل) مورد مطالعه قرار داده است که کاربرد گسترده ای در بسیاری از مسائل صنعتی دارد. در این تحقیق یک مدل برنامه‌ریزی‌خطی عدد صحیح مختلط جدید برای این مساله توسعه داده می‌شود. علاوه بر این به علت NP-hard بودن مساله مورد بررسی، یک الگوریتم بهینه‌سازی پرنده استوایی دریایی بهبود یافته جدید با یک روش رمزگشایی جدید برای حل مسائل با اندازه بزرگ ارائه می شود. به منظور ارزیابی الگوریتم بهینه سازی پیشنهادی، 5 الگوریتم شناخته شده در ادبیات تحقیق (الگوریتم سیستم ایمنی بدن مصنوعی مبتنی بر ایمونوگلوبولین، الگوریتم ژنتیک، الگوریتم زنبور عسل مصنوعی گسسته، الگوریتم توسعه یافته کرم میوه و الگوریتم بهینه سازی توسعه یافته پرندگان مهاجر) با مساله پیشنهادی تطبیق داده شده است و در نهایت عملکرد الگوریتم بهینه سازی پیشنهادی در مقایسه با الگوریتم های تطبیق یافته، مورد بررسی قرار گرفته است.
کلیدواژه‌ها
عنوان مقاله [English]
Mathematical Model and Meta-Heuristic Algorithm for Dual Resource Constrained Hybrid Flow-Shop Scheduling Problem with Job Rejection
نویسندگان [English]
- Mohammadreza Dabiri 1
- Mehdi Yazdani 2
- bahman naderi 3
- Hasan Haleh 4
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
چکیده [English]
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.
کلیدواژه‌ها [English]
- Keywords: Hybrid Flow-Shop Scheduling
- Meta-Heuristic Algorithm
- Job Rejection
- Sooty Tern Optimization Algorithm
- Dual Resource Constrained
یزدانی، مهدی؛ زندیه، مصطفی؛ توکلی مقدم؛ رضا (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.
)