Mathematical Researches

fa حل مسئلۀ کارگاه جریان جایگشتی به وسیله تنظیمات درایه‌های ستونی در ماتریس زمان‌های پردازش Solving Permutation Flow shop Problem by the Regulations of Columnar Entries in the Processing Times Matrix جریان شبکه- تحقیق عملکرد Network Flows- Operation Reseach علمی پژوهشی کاربردی S <div style="text-align: justify;">مسئله کارگاه جریانی جایگشتی یکی از مسائل مهم و به روز تحقیق در عملیات گسسته است. در این مقاله آلگوریتم ابتکاری جدیدی با استفاده از تنظیم درایه‌های ستونی ماتریس زمان‌ها برای حل مسئله کارگاه جریانی جایگشتی پیشنهاد می‌شود. <img alt="" src="file:///C:UsersAzarAppDataLocalTempmsohtmlclip1�1clip_image001.wmz" >  کار روی <img alt="" src="file:///C:UsersAzarAppDataLocalTempmsohtmlclip1�1clip_image002.wmz" >  ماشین با زمان‌های قطعی پردازش می‌شوند و هدف اصلی می‌نیمم کردن زمان کل تکمیل کارهاست. مسئله، در زمان چندجمله‌ای قابل حل نیست. مانند بیشتر روش‌های ابتکاری حل مسئله، ابتدا ترتیب اولیه مناسبی از دنباله کارها پیدا می‌شود. برای این منظور ماتریس <img alt="" src="file:///C:UsersAzarAppDataLocalTempmsohtmlclip1�1clip_image003.wmz" >  چنان ساخته می‌شود که هر <img alt="" src="file:///C:UsersAzarAppDataLocalTempmsohtmlclip1�1clip_image004.wmz" >  نشان‌دهنده اندازه مناسب بودن جای سطر قدیم <img alt="" src="file:///C:UsersAzarAppDataLocalTempmsohtmlclip1�1clip_image005.wmz" > ام در مکان جدید <img alt="" src="file:///C:UsersAzarAppDataLocalTempmsohtmlclip1�1clip_image006.wmz" > ام باشد. سپس قضیه بلمن، اسوگبو و نابشیما مورد استفاده قرار می‌گیرد. روش ارائه شده با آلگوریتم NEH که بهترین روش شناخته و موجود است مقایسه می‌شود. مقایسه روی مسائل محک و استاندارد تیلارد انجام می‌گیرد. نتایج محاسباتی نشان می‌دهند آلگوریتم ابتکاری بهتر از بعضی روش‌های پیشنهاد شده قبلی می‌باشد و نسبت به بقیه در تعدادی از مثال‌های تیلارد برتر است. به عنوان نتیجه آلگوریتم ابتکاری تقریباً به خوبی NEH و امیدبخش می‌باشد. بر اساس ساختار ارائه شده، آلگوریتم ابتکاری پیشنهادی می‌تواند به خوبی نقش یک روش فراابتکاری را ایفا کند.</div> Scheduling theory and permutation therein are two important subjects in discrete operation research. In this paper, a new heuristic algorithm is proposed for solving permutation flow shop problem by using regulations of columnar entries in the processing times matrix. There are <img alt="" src="file:///C:/Users/pc/AppData/Local/Temp/msohtmlclip1/01/clip_image002.png" style="width:15px; height:13px" > jobs to be processed on <img alt="" src="file:///C:/Users/pc/AppData/Local/Temp/msohtmlclip1/01/clip_image004.png" style="width:19px; height:13px" > machines with deterministic processing times and the object is obtaining the minimum of the total time to complete the schedule (makespan). This is not solvable in polynomial time. First, an initial suitable sequence of jobs is determined similar to many heuristics. For this, the matrix <img alt="" src="file:///C:/Users/pc/AppData/Local/Temp/msohtmlclip1/01/clip_image006.png" style="width:59px; height:25px" > is made such that every <img alt="" src="file:///C:/Users/pc/AppData/Local/Temp/msohtmlclip1/01/clip_image008.png" style="width:18px; height:21px" >determines the measure of the fitness for the location of the <img alt="" src="file:///C:/Users/pc/AppData/Local/Temp/msohtmlclip1/01/clip_image010.png" style="width:12px; height:17px" >th old row in the <img alt="" src="file:///C:/Users/pc/AppData/Local/Temp/msohtmlclip1/01/clip_image012.png" style="width:12px; height:17px" >th new position. Thereafter, the Bellman Esogbue Nabeshima theorem is used. The presented algorithm is compared with the NEH (the best well-known existing method). This comparison is made by the Taillard’s standard test problems. Computational results demonstrate that the heuristic algorithm is better than some of the proposed heuristics known so far and it is superior with respect to others in a number of Taillard instances. As a result, it is almost as good as NEH and is very promising for the problem. On the basis of the structure of the proposed algorithm, it can perform a role as meta-heuristic. زمان‌بندی, کارگاه جریانی جایگشتی, روش‌های ابتکاری, دنباله اولیه, ماتریس زمان‌ها, حداکثر زمان در جریان, آلگوریتم NEH, مسائل محک تیلارد. Scheduling, Permutation flow shop, Heuristics, Initial sequences, Time matrix, Makespan, NEH, Taillard’s benchmark 1 23 http://mmr.khu.ac.ir/browse.php?a_code=A-10-480-2&slc_lang=fa&sid=1 Shahriar Farahmand Rad شهریار فرهمند راد sh_fmand@pnu.ac.ir 10031947532846006399 10031947532846006399 Yes Payame Noor University, Tehran دانشگاه پیام نور، تهران