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

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

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

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.