زمانبندي دو معياره براي حداقل سازي زمان ديركرد كل و واريانس زمان انتظار بر روي يك ماشين با استفاده از الگوريتم ژنتيك

Bicriteria single machine scheduling to minimize total tardiness and waiting time variance by genetic algorithms

مساي عملي زمانبندي معمولاً تصميمگيرنده را وادار به در نير گرفتن تعداد زيادي از معيارها قب از اتخار تصميم مي نمايند. اين تحييد يك مسيله زمانبندي تك ماشين را مورد بررسي قرار مي دهد كه هدف در آن حداق كردن تركيبي از دو معيار ديركرد ك و واريانا زمان انتيار مي باشد به حوري كه زمان بيكاري در ماشين مجاز نيست. حداق كردن ديركرد ك هميشه به عنوان يك معيار عملكرد مهم در سيستم هاي عملي، كه مي توان با استفاده از آن از تحمي هزينههاي جريمه ديركرد اجتناب نمود، مطرح مي باشد و واريانا زمان انتيار نيز يك معيار مهم در پيادهسازي كيفيت هدمات ) QoS ( در بسياري از سيستم ها مي باشد. هر كدام از اين دو معيار از نوع NP-hard مي باشند و بنابراين تركيب هطي آن ها نيز NP-hard هواهد بود. براي اين مسيله الگوريتمي ژنتيك حراحي شده كه از ساهتار معمول آن استفاده مي كند. دو نوع جمعيت هيوريستيك و تصادفي براي جمعيت اوليه و دو نوع تابع برازش در الگوريتم به كار رفته است. كارايي الگوريتم ژنتيك ارايه شده به وسيله تست روي تعداد زيادي از مساي نشان داده مي شود

Actual scheduling problems may necessitate the decision maker to consider a variety of criteria prior to make any decision. This research considers a single machine scheduling problem, with the objective of minimizing a combination of total tardiness and waiting time variance criteria in which the idle time is not allowed. Minimizing total tardiness is always regarded as one of the most important performance criteria in practical systems to avoid penalty costs of tardiness and waiting time variance is an important criterion in establishing Quality of Service (QoS) in many systems. Each of these criteria is known to be NP-hard and therefore the linear combination of them will be NP-hard as well. For this problem, we developed a genetic algorithm by utilizing its general structure. Two types of heuristic and random initial population and two distinct fitness functions are applied to genetic algorithms. The GA is shown experimentally to perform well by testing on various instances.