رويكرد شبيه‌سازي در حل مسأله زمانبندي ماشين هاي موازي پردازشگر دسته اي با زمان هاي احتمالي

Development of Simulation on parallel Batch Scheduling Problem With Stochastic Times

در اين مقاله، مسأله زمانبندي ماشينهاي موازي پردازشگر دستهاي با هدف حداقل كردن حداكثر زمان تكميل كارها بررسي مي‌شود. نوآوري اين پژوهش، به كارگيري زمان هاي پردازش و در دسترس بودن كارها به صورت احتمالي است. در تحقيقات پيشين اثبات شده است كه مسأله مورد بررسي داراي پيچيدگي سخت است. بنابراين، از روشهاي ابتكاري براي حل مسأله استفاده ميشود. مسأله مورد مطالعه، دو مرحله تصميم‌گيري دارد. در مرحله اول ابتدا كارها به دسته‌هايي طبقه‌بندي مي‌شوند و در مرحله بعد، دسته‌هاي به دست آمده به ماشين‌هاي موازي تخصيص مي‌يابند. در اين مقاله، از دو روش ابتكاري براي ايجاد دسته ها و از سه روش ابتكاري براي ترتيب دهي توالي دسته ها استفاده خواهد شد. به علت احتمالي بودن زمانهاي پردازش و در دسترس بودن كارها، با استفاده از رويكرد شبيه سازي، 10000 نمونه مسأله به صورت تصادفي توليد مي‌شود. 6 حالت تركيبي روشهاي ابتكاري با حل نمونه مسائل به دست آمده از شبيه سازي مقايسه مي‌شوند. نتايج به دست آمده نشان ميدهد كه تركيب روش‌هاي ابتكاري MBF در فاز اول و روش ERT-LPT در فاز دوم از كارايي بهتري در رسيدن به جواب‌هاي مناسب برخوردار است.

In this paper, the problem of batch scheduling in parallel machines environment with the objective of minimizing make span (Cmax) is addressed. The main contribution of this research is the stochastic nature of the processing times of jobs and release times for better depiction of the real world. It has been proved that the problem is NP-hard. Therefore, we apply heuristic approaches to solve this problem. The provided problem includes two stages of decision making. In the first stage, the jobs are classified into batches and in the next stage; these batches should be assigned to parallel machines. Two and three heuristic methods are used for producing batches and sequencing batches, respectively. 10,000 test problems are randomly generated due to stochastic nature of processing times and release dates. Using the results of simulating test problems, six combinations of heuristic methods are compared. The results show that applying MBF heuristic method in the first stage and ERT-LPT method in the second stage provide better and efficient solutions.