مدل ریاضی و الگوریتم جدید برای مسئله زما‌ن‌بندی اقتصادی انباشته در محیط جریان کارگاهی انعطاف‌پذیر
نویسنده
گروه مهندسی صنایع، دانشکده فنی مهندسی، دانشگاه خوارزمی، تهران
چکیده
در این مقاله مسئله تعیین اندازه انباشته و زما‌ن‌بندی چند محصول در محیط جریان کارگاهی انعطاف‌پذیر با ماشین‌های موازی یکسان بررسی می‌شود. مراحل تولید به‌صورت سری بوده و بافر محدود بین مراحل متوالی درنظر گرفته شده است. تابع هدف مسئله، کمینه سازی مجموع هزینه‌های راه‌اندازی و نگهداری در واحد زمان است. مدل ریاضی موجود در ادبیات مسئله دارای پیچیدگی اندازه و پیچیدگی محاسباتی زیادی است. در این مقاله، یک مدل ریاضی خطی مختلط عدد صحیح جدید برای مسئله ارائه می‌شود. همچنین یک الگوریتم فرا ابتکاری کارآمد برای حل ابعاد بزرگ مسئله پیشنهاد می‌شود. نتایج حاصل از انجام آزمایشات عددی، بیانگر برتری قابل توجه مدل و الگوریتم پیشنهادی این مقاله در مقایسه با مدل و الگوریتم‌های موجود در ادبیات مسئله است.
کلیدواژه‌ها
عنوان مقاله [English]
New Mathematical Model and Algorithm for Economic Lot Scheduling Problem in Flexible Flow Shop
نویسنده [English]
- H. Zohali
This paper addresses the lot sizing and scheduling problem for a number of products in flexible flow shop with identical parallel machines. The production stages are in series, while separated by finite intermediate buffers. The objective is to minimize the sum of setup and inventory holding costs per unit of time. The available mathematical model of this problem in the literature suffers from huge complexity in terms of size and computation. In this paper, a new mixed integer linear program is developed for delay with the huge dimentions of the problem. Also, a new meta heuristic algorithm is developed for the problem. The results of the numerical experiments represent a significant advantage of the proposed model and algorithm compared with the available models and algorithms in the literature.
کلیدواژه‌ها [English]
- lot sizing
- Scheduling
- hybrid flow shop
- mathematical model
- meta heuristic
1. Karimi, B., Ghomi, S. F., and Wilson, J. M., “The Capacitated Lot Sizing Problem: A Review of Models and Algorithms”, Omega, Vol. 31, pp. 365-378, 2003.
2. Santander-Mercado, A., and Jubiz-Diaz., M., “The Economic Lot Scheduling Problem: A Survey”, International Journal of Production Research, pp. 1-20, 2016.
3. Akrami, B., Karimi, B., and Hosseini, S. M., “Two Metaheuristic Methods for the Common Cycle Economic Lot Sizing and Scheduling in Flexible Flow Shops with Limited Intermediate Buffers: The Finite Horizon Case”, Applied Mathematics and Computation, Vol. 183, pp. 634-645, 2006.
4. Taft, E. W., “The Most Economical Production Lot”, Iron Age, Vol. 101, pp. 1410-1412, 1918.
5. Rogers, J., “A Computational Approach to the Economic Lot Scheduling Problem”, Management Science, Vol. 4, pp. 264-291, 1958.
6. Gallego, G., and Shaw, D. X., “Complexity of the ELSP with General Cyclic Schedules”, IIE Transactions, Vol. 29, pp. 109-113, 1997.
7. Davis, S. G., “Scheduling Economic Lot Size Production Runs”, Management Science, Vol. 36, pp. 985-998, 1990.
8. Moon, I., Silver, E. A., and Choi, S., “Hybrid Genetic Algorithm for the Economic Lot-Scheduling Problem”, International Journal of Production Research, Vol. 40, pp. 809-824, 2002.
9. Holmbom, M., and Segerstedt, A., “Economic Order Quantities in Production: From Harris to Economic Lot Scheduling Problems”, International Journal of Production Economics, Vol. 155, pp. 82-90, 2014.
10. Dobson, G., and Yano, C. A., “Cyclic Scheduling to Minimize Inventory in a Batch Flow Line”, European Journal of Operational Research, Vol. 75, pp. 441-461, 1994.
11. El-Najdawi, M. K., and Kleindorfer, P. R., “Common Cycle Lot-Size Scheduling for Multi-Product, Multi-Stage Production”, Management Science, Vol. 39, pp. 872-885, 1993.
12. El-Najdawi, M. K., “A Job-Splitting Heuristic for Lot-Size Scheduling in Multi-Stage, Multi- Product Production Processes”, European Journal of Operational Research, Vol. 75, pp. 365-377, 1994.
13. Ouenniche, J., Boctor, F. F., and Martel, A., “The Impact of Sequencing Decisions on Multi- Item Lot Sizing and Scheduling in Flow Shops”, International Journal of Production Research, Vol. 37, pp. 2253-2270, 1999.
14. Torabi, S. A., Fatemi Ghomi, S. M. T., and Karimi, B., “A Hybrid Genetic Algorithm for the Finite Horizon Economic Lot and Delivery Scheduling in Supply Chains”, European Journal of Operational Research, Vol. 173, pp. 173-189, 2006.
15. Jenabi, M., Fatemi Ghomi, S. M. T., Torabi, S. A., and Karimi, B., “Two Hybrid Meta- Heuristics for the Finite Horizon ELSP in Flexible Flow Lines with Unrelated Parallel Machines”, Applied Mathematics and Computation, Vol. 186, pp. 230-245, 2007.
16. Mladenović, N., and Hansen, P., “Variable Neighborhood Search”, Computers & Operations Research, Vol. 24, No. 11, pp. 197-1100, 1997.
17. Deming, L.,“Variable Neighborhood Search for Two-Agent Flow Shop Scheduling Problem”, Computers & Industrial Engineering, Vol. 80, pp. 125-131, 2015.
18. Moslehi, Gh., and Khorasanian. D., “A Hybrid Variable Neighborhood Search Algorithm for Solving the Limited-Buffer Permutation Flow Shop Scheduling Problem with the Makespan Criterion”, Computers & Operations Research, Vol. 52, pp. 260-268, 2014.
19. Hatami, S., Ruiz, R., and Andrés-Romano, C., “The Distributed Assembly Permutation Flowshop Scheduling Problem”, International Journal of Production Research Vol. 51, No. 17, pp. 5292-5308, 2013.
20. Hansen, P., and Mladenovic, N., A Tutorial on Variable Neighborhood Search. Groupe d'études et de recherche en analyse des décisions, HEC Montréal, 2003.
21. Wen-Tsao, P. “A New Fruit Fly Optimization Algorithm: Taking the Financial Distress Model as an Example”, Knowledge-Based Systems, Vol. 26, pp. 69-74, 2012.
22. Ouenniche, J., and Boctor. F., “Sequencing, Lot Sizing and Scheduling of Several Products in Job Shops: The Common Cycle Approach”, International Journal of Production Research, Vol. 36, No. 4, pp. 1125-1140, 1998.
2. Santander-Mercado, A., and Jubiz-Diaz., M., “The Economic Lot Scheduling Problem: A Survey”, International Journal of Production Research, pp. 1-20, 2016.
3. Akrami, B., Karimi, B., and Hosseini, S. M., “Two Metaheuristic Methods for the Common Cycle Economic Lot Sizing and Scheduling in Flexible Flow Shops with Limited Intermediate Buffers: The Finite Horizon Case”, Applied Mathematics and Computation, Vol. 183, pp. 634-645, 2006.
4. Taft, E. W., “The Most Economical Production Lot”, Iron Age, Vol. 101, pp. 1410-1412, 1918.
5. Rogers, J., “A Computational Approach to the Economic Lot Scheduling Problem”, Management Science, Vol. 4, pp. 264-291, 1958.
6. Gallego, G., and Shaw, D. X., “Complexity of the ELSP with General Cyclic Schedules”, IIE Transactions, Vol. 29, pp. 109-113, 1997.
7. Davis, S. G., “Scheduling Economic Lot Size Production Runs”, Management Science, Vol. 36, pp. 985-998, 1990.
8. Moon, I., Silver, E. A., and Choi, S., “Hybrid Genetic Algorithm for the Economic Lot-Scheduling Problem”, International Journal of Production Research, Vol. 40, pp. 809-824, 2002.
9. Holmbom, M., and Segerstedt, A., “Economic Order Quantities in Production: From Harris to Economic Lot Scheduling Problems”, International Journal of Production Economics, Vol. 155, pp. 82-90, 2014.
10. Dobson, G., and Yano, C. A., “Cyclic Scheduling to Minimize Inventory in a Batch Flow Line”, European Journal of Operational Research, Vol. 75, pp. 441-461, 1994.
11. El-Najdawi, M. K., and Kleindorfer, P. R., “Common Cycle Lot-Size Scheduling for Multi-Product, Multi-Stage Production”, Management Science, Vol. 39, pp. 872-885, 1993.
12. El-Najdawi, M. K., “A Job-Splitting Heuristic for Lot-Size Scheduling in Multi-Stage, Multi- Product Production Processes”, European Journal of Operational Research, Vol. 75, pp. 365-377, 1994.
13. Ouenniche, J., Boctor, F. F., and Martel, A., “The Impact of Sequencing Decisions on Multi- Item Lot Sizing and Scheduling in Flow Shops”, International Journal of Production Research, Vol. 37, pp. 2253-2270, 1999.
14. Torabi, S. A., Fatemi Ghomi, S. M. T., and Karimi, B., “A Hybrid Genetic Algorithm for the Finite Horizon Economic Lot and Delivery Scheduling in Supply Chains”, European Journal of Operational Research, Vol. 173, pp. 173-189, 2006.
15. Jenabi, M., Fatemi Ghomi, S. M. T., Torabi, S. A., and Karimi, B., “Two Hybrid Meta- Heuristics for the Finite Horizon ELSP in Flexible Flow Lines with Unrelated Parallel Machines”, Applied Mathematics and Computation, Vol. 186, pp. 230-245, 2007.
16. Mladenović, N., and Hansen, P., “Variable Neighborhood Search”, Computers & Operations Research, Vol. 24, No. 11, pp. 197-1100, 1997.
17. Deming, L.,“Variable Neighborhood Search for Two-Agent Flow Shop Scheduling Problem”, Computers & Industrial Engineering, Vol. 80, pp. 125-131, 2015.
18. Moslehi, Gh., and Khorasanian. D., “A Hybrid Variable Neighborhood Search Algorithm for Solving the Limited-Buffer Permutation Flow Shop Scheduling Problem with the Makespan Criterion”, Computers & Operations Research, Vol. 52, pp. 260-268, 2014.
19. Hatami, S., Ruiz, R., and Andrés-Romano, C., “The Distributed Assembly Permutation Flowshop Scheduling Problem”, International Journal of Production Research Vol. 51, No. 17, pp. 5292-5308, 2013.
20. Hansen, P., and Mladenovic, N., A Tutorial on Variable Neighborhood Search. Groupe d'études et de recherche en analyse des décisions, HEC Montréal, 2003.
21. Wen-Tsao, P. “A New Fruit Fly Optimization Algorithm: Taking the Financial Distress Model as an Example”, Knowledge-Based Systems, Vol. 26, pp. 69-74, 2012.
22. Ouenniche, J., and Boctor. F., “Sequencing, Lot Sizing and Scheduling of Several Products in Job Shops: The Common Cycle Approach”, International Journal of Production Research, Vol. 36, No. 4, pp. 1125-1140, 1998.
)