زمان‌بندی چندعاملی ماشین‌های موازی ناهمگن با در نظر گرفتن هزینه انرژی و کارهای به‌هنگام

نوع مقاله : مقاله پژوهشی

نویسندگان

1 گروه مهندسی صنایع، دانشکده مهندسی، دانشگاه بوعلی سینا، همدان، ایران

2 استادیار گروه صنایع دانشکده مهندسی دانشگاه بوعلی سینا

چکیده

در مدل­های کلاسیک، معمولاً تمرکز بر ارائه برنامه زمان‌بندی با اهداف متناظر با زمان تکمیل کارها است حال‌آنکه با توجه به ارتباط بین اقتصاد، انرژی و نگرانی­های زیست‌محیطی، توجه به انرژی مصرفی ماشین­آلات در سالیان اخیر موردتوجه محققین حوزه‌های مختلف قرار گرفته است. همچنین در تحقیقات عموماً فرض بر آن بوده است که یک عامل (تولیدکننده) به‌تنهایی سعی در بهینه­سازی هدف خود داشته حال‌آنکه در واقعیت ممکن است چندین عامل تولیدی به دلیل محدودیت‌های خود به‌ناچار از منابع مشترک جهت پردازش کارها استفاده کنند. در همین راستا در پژوهش حاضر، مساله زمان‌بندی دوعاملی در کارگاه ماشین­های موازی ناهمگن موردبررسی قرار گرفته و ازآنجاکه انرژی مصرفی ماشین­ها با سرعت پردازش آن‌ها رابطه­ای مستقیم دارد، هزینه انرژی نیز مورد قرار گرفته است. در اینجا فرض شده است که عامل اول درصدد کمینه­سازی مجموع جریمه­های دیرکرد و هزینه انرژی و عامل دوم درصدد کمینه­سازی مجموع جریمه­های دیرکرد و زودکرد است. از آنجائیکه مساله فوق یک مساله Np-hard است، علاوه بر مدل‌سازی و حل آن، جهت ارائه راه‌حل‌های مناسب برای ابعاد بزرگ، الگوریتم فراابتکاری ممتیک پیشنهاد و به‌منظور بررسی عملکرد آن، نتایج حاصل با نتایج خروجی نرم­افزار گمز و فراابتکاری دیگر مقایسه شده است. با توجه به نتایج حاصل، مشاهده گردید که الگوریتم پیشنهادی در ابعاد مختلف مساله عملکرد مناسبی داشته بطوریکه در ابعاد کوچک، در مقایسه نتایج با روش Lp-Metric وزنی، و در ابعاد بزرگ، با در نظر گرفتن چندین معیار عملکردی مطرح در ادبیات، الگوریتم پیشنهادی کارایی بسیار مناسبی داشته است.

کلیدواژه‌ها

عنوان مقاله [English]

Multi-agent heterogeneous parallel machines scheduling problem with energy cost and just-in-time jobs

نویسندگان [English]

  • Amir Afsar 1
  • Javad Behnamian 2
1 Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran
2 Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University
چکیده [English]

In the classic models of scheduling problems, researchers mostly concentrate on the objectives considering jobs completion time. Due to the relation among economy, energy and environmental concerns, attention to the energy use of machines have been considered by researchers in the field of scheduling in recent years. Also, In the literature of scheduling problems, it is mostly assumed that one agent try to optimize the problem. But, occasionally there are several agents that each has their own jobs and they must use a series of common resources to process them. In this study, a two-agent heterogeneous parallel-machines scheduling problem is studied in which the process speed of each job on each machine is adjustable. Since there is a direct link between the energy used in machines and process speed, the used energy costs affect on scheduling problem. In this study, the first agent is tried to minimize total tardiness penalty as well as energy costs of production machines and the second agent is tried to minimize total tardiness and earliness. The suitable schedule should be considered to allocate and sequence jobs of agents to the common resources to optimize appropriately the agent’s objective functions. Since the proposed problem is Np-hard, in order to solve it in large scale problems, a Memetic algorithm is developed and to verify the performance of this algorithm, we take into comparison the results of Memetic algorithm with the results of GAMS software and of another meta-heuristic algorithm.

کلیدواژه‌ها [English]

  • Multi-agent scheduling
  • Parallel-machines scheduling
  • Energy cost
  • Just-in-time jobs
  • Memetic algorithm

مراجع

[1] Pinedo, M., (2001). Scheduling: Theory, Algorithms, and Systems. Prentice-Hall Inc., Englewood Cliffs, N.J.
[2] Kim, D-W., Kim, K-H., Jang, W., Chen, F., (2002). “Unrelated parallel machine scheduling with setup times using simulated annealing”. Robotics and ComputerIntegrated Manufacturing, 18: 223-231.
[3] Vredeveld, T., Hurkens, C., (2002). “Experimental comparison of approximation algorithms for scheduling unrelated parallel machines”. Informs Journal on Computing, 14(2): 175-189.
[4] Rogendran, R., Subur, F., (2004). “Unrelated parallel machine scheduling with job splitting”. IIE Transaction, 36: 356-372.
[5] Tavakkoli-Moghaddam, R., Taheri, F., Bazzazi, M., Izadi, M., Sassani, F., (2009). “Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints”. Computers & Operations Research, 36: 3224-3230.
[6] Balin, S., (2011). “Non-identical parallel machine scheduling using genetic algorithm”. Expert System with Applications, 38: 6814-6821.
[7] Lin, Y. K., Pfund, M. E., Fowler, J. W., (2011). “Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problem”. Computers & Operations Research, 38(6): 901–916.
[8] Vallada, E., Ruiz, R., (2011). “A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times”. European Journal of Operational Research, 211: 612-622.
[9] Rodriguez, F. J., Lozano, M., Blum, C., Garcia-Martinez, C., (2013). “An iterated greedy algorithm for the large-scale unrelated parallel machine scheduling problem”. Computers & Operations Research, 40: 1829-1841.
[10] Fanjul-Peyro, L., Perea, F., Ruiz, R., (2017). “Models and matheuristics for the unrelated parallel machine scheduling problem with additional resources”. European Journal of Operational Research 000 (2017): 1-12.
[11] Hoogeveen, H., (2005). “Multicriteria scheduling”. European Journal of Operational Research, 167: 592e623.
[12] Liu, Y., Dong, H., Lohse, N., Petrovic, S., Gindy, N., (2013). “An investigation into minimizingtotal energy consumption and total weighted tardiness in job shops”.Journal of Cleaner Production, 1e10.
[13] Yan, H., Fei, L., Hua-jun, C., Cong-bo, L., (2005). A bi-objective model for job-shopscheduling problem to minimize both energy consumption and makespan.J. Cent. South Univ. Technol. 12.
[14] Liu, X., Zou, F., Zhang, X., (2008). “Mathematical model and genetic optimization forhybrid flow shop scheduling problem based on energy consumption”. In: 2008 Chinese Control and Decision Conference, pp. 1002e1007.
[15] Yildirim, M.B., Mouzon, G., (2011). “Single-machine sustainable production planning tominimize total energy consumption and total completion time using a multipleobjective genetic algorithm”. In: IEEE Transactions on Engineering Management,pp. 1e13.
[16] Fang, K., Uhan, N., Zhao, F., Sutherland, J.W., (2011). “A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction”. Journal of Manufacturing Systems, 30, 234e240.
[17] Fang, K., Bertrand M.T., Lin. (2012). “Parallel-machine scheduling to minimize tardiness penalty and power cost”. Computers & Industrial Engineering, 64 (2013): 224-234.
[18] Ada Che, Shibohua Zhang, Xueqi, Wu. (2017). “Energy-conscious unrelated parallel machine scheduling under time-of-use electricity tariffs”. Journal of cleaner production.156(10): 688-697.
[19] Moon, J.Y., Shin, K., Park, J., (2013). “Optimization of production scheduling with time-dependent and machine-dependent electricity cost for industrial energy efficiency”. International Journal of Advanced Manufacturing Technology,68, 523-535.
[20] Ding, J.Y., Song, S., Zhang, R., Chiong, R., (2016). “Parallel machine scheduling under time-of-useelectricity prices: new models and optimization approaches”. IEEE Transactions on Automation Science & Engineering,13(2): 1138-1154.
[21] Luo, H., Du, B., Huang, G.Q., Chen, H., Li, X., (2013). “Hybrid flow shop scheduling considering machine electricity consumption cost”. International Journal of Production Economics,146: 423-439.
[22] Zhang, H., Zhao, F., Fang, K., Sutherland, J.W., (2014). “Energy-conscious flow shop scheduling under time-of-use electricity tariffs”. CIRP Annals – Manufacturing Technology,63: 37-40.
[23] Sharma, A., Zhao, F., Sutherland, J.W., (2015). “Econological scheduling of a manufacturingenterprise operating under a time-of-use electricity tariff”. Journal of Cleaner Production,108: 256-270.
[24] Baker, K. R., Smith, J. C. (2003). “A multiple-criterion model for machine scheduling”. Journal of Scheduling, 6(1): 7-16.
[25] Agnetis, A., Mirchandani, P. B., Pacciarelli, D., Pacifici, A., (2004). “Scheduling problems with two competing agents”. Operations Research, 52(2): 229-242.
[26] Cheng, T. C. E., Ng, C. T., Yuan, J. J., (2006). “Multi-agent scheduling on a singlemachine to minimize total weighted number of tardy jobs”. Theoretical Computer Science, 362(1–3): 273-281.
[27] Leung, J. Y. T., Pinedo, M., Wan, G. H., (2010). Competitive two agents scheduling and its applications. Operations Research, 58(2): 458-469.
[28] Wu, C. C., Huang, S. K., Lee, W. C., (2011). “Two-agent scheduling with learning consideration”. Computers & Industrial Engineering, 61(4): 1324-1335.
[29] Cheng, T. C. E., Cheng, S. R., Wu, W. H., Hsu, P. H., Wu, C. C., (2011). “A two-agent single machine scheduling problem with truncated sum-of-processing-timesbased learning considerations”. Computers & Industrial Engineering, 60(4): 534-541.
[30] Elvikis, D., Hamacher, H. W., T’kindt, V., (2011). “Scheduling two agents on uniformparallel machines with makespan and cost functions”. Journal of Scheduling, 14(5): 471-481.
[31] Lee, W. C., Chung, Y. H., Hu, M. C., (2012). “Genetic algorithms for a two-agentsingle-machine problem with release time”. Applied Soft Computing, 12(11):3580-3589.
[32] Lee, W. C., Wang, J. Y., Lin, M. C., (2016). “A branch-and-bound algorithm forminimizing the total weighted completion time on parallel identical machineswith two competing agents”. Knowledge-Based Systems, 105: 68-82.
[33] Lee, W. C., Wang, J. Y., (2014). “A scheduling problem with three competing agents”. Computers & Operations Research, 51: 208-217.
[34] Lee, W. C., Wang, J. Y., (2017). “A three-agent scheduling problem for minimizing the makespan on a single machine”. Computers & Industrial Engineering, 106: 147-160.
[35] Shiau, Y. R., Tsai, M. S., Lee, W. C., Cheng, T. C. E., (2015). “Two-agent two-machine flowshop scheduling with learning effects to minimize the total completion time”. Computers & Industrial Engineering, 87: 580-589.
[36] Yuan, J. J., Ng, C. T., Cheng, T. C. E., (2015). “Two-agent single-machine schedulingwith release dates and preemption to minimize the maximum lateness”. Journal of Scheduling, 18(2): 147-153.
[37] Pinedo, M. (2001). Scheduling: Theory, Algorithms, and Systems. Prentice-Hall Inc., Englewood Cliffs, N.J.
[38] Garey, MR., Johnson, DS., (1978). “Strong NP-completeness results: Motivation,examples, and implications”. Journal of the Association for Computing Machinery,25(3): 499-508.
[39] Behnamian J., Fatemi Ghomi SMT, Zandieh M., (2009). “A multi-phase covering Pareto-optimal front method to multi-objective scheduling in a realistic hybrid flowshop using a hybrid metaheuristic”. Expert Systems with Applications, 36(8): 11057-1106
نشریه پژوهش های مهندسی صنایع در سیستم های تولید
دوره 7، شماره 15
اسفند 1398
صفحه 287-303

فایل ها

هم رسانی

ارجاع به این مقاله

آمار