مروري بر مقالات و تحقيقات در زمينه زمانبندي كارگاه گردش كاري چندهدفه

ساسان تقدسي و فريد خوش الحان

كلمات كليدي چكيده:

زمانبندي ، در اين مقاله مرور كاملي در زمينه تحقيقات انجام شده در باره زمانبندي كارگاه گردش كاري كارگاه گردش كاري ، چندهدفه ارائه شده است . مقالات مرتبط با اين مسأله از سال 1986تا سال 2010 ميلادي مورد
بهينه سازي چندهدفه ، مطالعه قرار گرفته و سپس گزارش تحليلي ارائه شده است. مقالات بر اساس انواع توابع هدف،
مرور ادبيات فرضيات ساختاري مربوط به كارگاهها و نوع روشهاي حل طبقهبندي شده اند. اين مقاله ميتواند به عنوان مرجعي مناسب براي پژوهشگران در حوزه زمانبندي، به ويژه مسائل زمانبندي كارگاه گردش كاري به حساب آيد.
معيار كمينهسازي بيشترين مقدار: اين معيار سعي دارد بيشترين مقدار از يك مجموعه توابع را كمينه نمايد .
معيار كمينهسازي جمع مقادير: اين معيار به منظور كمينه كردن جمع مجموعهاي از توابع عمل مي نمايد.
در ادامه به معرفي هر يك از اين معيارها ميپردازيم.

2 -1 معيار كمينه سازي بيشترين مقدار
1268732040128Downloaded from ijiepm.iust.ac.ir at 14:22 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:22 IRST on Saturday November 4th 2017

در اين بخش، آن دسته از معيارهاي minimax معرفي ميشوند كه در گزارشات و منابع معتبر مورد توجه و بررسي قرار گرفته اند. مرسومترين و مهمترين اين معيارها، معياري است كه زمان تكميل همه كارها را اندازهگيري ميكند. اين معيار با نماد Cmax نمايش داده شده و به آن زمان ساخت، ميگويند .انواع توابع هدف مرتبط با اين معيارها، عبارتند از:

زمان : Cj )Cmax = max j=1,,n{C j} زمان ساخت :Cmax • (ام j تكميل كار
• ( n : تعداد كل كارها )

-1519229475

1. مقدمه1
در مقايسه با مسائل زمانبندي تك معياره، تحقيقات انجام شده در زمينه مسائل زمانبندي كارگاه گردش كاري چنددفعه بسيار كمتر است. اين امر در زمينه زمانبندي كارگاه گردش كاري محسوستر است. روشهاي پيشنهادي جهت حل مسائل زمانبندي كارگاه گردش كاري چندمعياره عمدتاًعمدتا بر اساس روشهاي بهينه سازي تكاملي و همچنين روشهاي جستجوي محلي، مانند روش هاي شبيه سازي تبريدي و جستجوي ممنوع مي باشند 1[].
هدف از اين مقاله، مرور مقايسهاي و تحليلي در حوزه مسائل زمان بندي كارگاه گردش كاري چند هدفه است كه رويكرد اصلي در آن شناسايي زمينههاي مختف تحقيقاتي در اين حوزه ميباشد.

2. توابع هدف در مدلهاي زمان بندي
جهت ارزيابي برنامه زمانبندي مي توان از يك يا چند معيار استفاده كرد، كه اين معيارها به دو دسته كلي زير تقسيم بندي مي شوند:
تاريخ وصول: 5/12/88 تاريخ تصويب: 26/3/89
ساسان تقدسي ،دانشجوي كارشناسي ارشد، دانشكده مهندسي صنايع، دانشگاه
صنعتي خواجه نصيرالدين طوسي ،sasan_taghadosi@yahoo.com دكتر فريد خوش الحان، استاديار، دانشكده مهندسي صنايع، دانشگاه صنعتي خواجه نصيرالدين طوسي، نويسنده مورد مكاتبه ،khoshalhan@kntu.ac.ir
3. رويكردهاي چندهدفه در مسائل زمان بندي با تأكيد بر مسائل چندهدفه در حوزه زمانبندي، رويكردهاي مختلفي جهت برخورد با توابع هدف وجود دارد كه در ادامه تشريح ميشوند.
Z : از اين علامت وقتي استفاده مي شود، كه در مسأله تنها يك معيار مورد توجه و ارزيابي قرار گيرد .
(Fl (Z1 ,…, Zk : از اين علامت وقتي استفاده ميشود كه؛ همه K معيار موجود در مسأله در قالب يك معيار كلي كه از تركيب خطي محدب ساير معيارها، به وجود آمده است، مورد توجه و ارزيابي قرار گيرند.
(Zu / Z1 , …. , Zu-1 , Zu+1 , …, Zk)ε : اين علامت نشان دهنده رويكرد مربوط به روشهاي محدوديتε مي باشد كه هدف از آن، كمينه كردن Z است، البته به شرطي كه ساير توابع هدف با گرفتن يك مقدار مشخص، در حد بالا قرار داشته باشند.
(P (Z1 ,…, Zk : نشان دهنده يك تابع غيرنزولي از K تابع هدف موجود در مسأله است كه بايد كمينه شود.
(FT (Z1 ,…, Zk : نشان دهندهي يك تابع هدفي است كه بيانگر فاصلهي حل، از حل ايدهآل مي باشد. اين فاصله، با استفاده از معيار چبيشف محاسبه مي شود. حل ايدهآل معمولامعمولاً با توجه به شرايط و محدوديت هاي مسأله قابل دستيابي نيست.
(FTp (Z1 ,…, Zk : نشان دهنده تابع هدفي است كه بيانگر فاصله حل، از يك حل ايده آل مشخص ميباشد. و تفاوت آن با معيار FT، آن است كه در اين حالت، فاصله با استفاده از معيار چبيشف وزني محاسبه ميشود. بايد توجه داشت كه در اين روش هم، حل ايدهآل قابل دستيابي نيست .
(FTpa (Z1 ,…, Zk : نشان دهنده تابع هدفي است كه بيانگر فاصله حل، از يك حل ايده آل مشخص است. در اين حالت ،فاصله با استفاده از معيار چبيشف وزني الحاقي محاسبه ميشود. بايد توجه داشت كه در اين روش هم، حل ايده آل قابل دستيابي نيست.
(FS (Z1,…, Zk : نشان دهنده تابع هدف خاصي است كه از يك حل ايده آل مشخص براي پيدا كردن حل مورد جستجو استفاده مي كند. اين روش در فضاي رويكرد دستيابي به هدف جهت حل مسائل چندهدفه قرار دارد.
(GP (Z1, …, Zk : وقتي كه براي هر يك از توابع هدف، يك مقدار آرماني وجود داشته باشد مي توان مسائل را با روش برنامه ريزي آرماني حل نمود. در چنين حالتي از اين نماد، استفاده

1268732040128Downloaded from ijiepm.iust.ac.ir at 14:22 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:22 IRST on Saturday November 4th 2017

Fmax: بيشترين زمان سپري شده در كارگاه
{Fj ) Fmax =max j=1,,n{Fj : مدت زمان در جريان سيستم بودن كار j ام)
Imax: بيشترين زمان بيكاري ماشينها در كارگاه
{Ii ) Imax =maxi=1,,m{Ii : جمع زمانهاي بيكاري براي ماشين i ام ( ) m : تعداد كل ماشينها )
Lmax : بيشترين تاخير {Lj) Lmax =max j=1,,n{Lj : مدت زمان تأخير كار j ام)
Tmax : بيشترين ديركرد {Tj) Tmax =max j=1,,n{Tj: مدت زمان ديركرد كار j ام) • Emax : بيشترين زودكرد {Ej) Emax =maxj=1,,n{Ej : مدت زمان زودكرد كار j ام)

2 -2. معيار كمينه سازي جمع مقادير
معيارهاي از نوع minisum ، به دنبال كمينه كردن مجموع يك سري توابع هستند كه در زير متداول ترين آنها معرفي ميشوند.

Ctotal ( C(: ميانگين زمان تكميل كارها (كل زمان تكميل
128020513719

C =1∑n C j =1Ctotal (كارها
n j=1n
1649020144

CW: ميانگين وزني زمان تكميل كارها
CW = n 1 ∑n WjC j
∑Wjj=1
j=1
( Wj : ميزان اهميت كار j ام از ديد تصميم گيرنده با توجه به معيار مربوطه)

Ftotal) F) : ميانگين مدت زمان در جريان ساخت (كل زمان
90836726464

F =1∑n Fj =

1Ftotal (در جريان ساخت
n j=1n

Ttotal) T) : ميانگين زمان ديركرد(كل زمان ديركرد كارها)
157738413633

T =1∑n Tj =1Ttotal
n j=1n

51975073562

TW : ميانگين وزني ديركردهاW = n 1 ∑n WjTj T
∑Wjj=1
j=1
Nt : تعداد كارهاي داراي ديركردNt =∑n U j
j=1
U j =0ifTj >0
1 ifTj ≤0
Idle : كل زمان بيكاري ماشينها idle =∑m Ii
i=1
2203774-17300

Etotal)E) : ميانگين زودكردها (كل زمان زودكرد)
151643911023

E = 1 ∑n Ej = 1Etotal
n j=1n

(# (Z1,…, Zk: نشاندهندهي وقتي است كه روش حل مسأله به دنبال پيدا كردن همه جوابهاي بهينه پارتو است و در اين مسير از هيچ يك از روش هاي يكپارچه سازي و يا تركيب توابع هدف استفاده نمي كند [1]. روشهاي GP ،Lex ،Fl و # از كاربرد بسيار بيشتري نسبت به ساير روشها، در مقالات و نوشتارهاي مربوط به زمانبندي چندهدفه، برخوردارند.

4. انواع روشهاي حل مسائل زمانبندي
براي هر مسأله زمانبندي، بسته به ساختار مسأله، نوع محدوديتها ،توابع هدف و ديگر مفروضات مسأله روشهاي مختلفي براي حل آن وجود دارد. برخي از اين روشها ساده و برخي ديگر ممكن است بسيار پيچيده باشند. در شكل1 ميتوان طبقه بندي روشهاي حل مسائل زمانبندي بر مبناي موارد مطرح شده در ادبيات موضوع و مراجع را مشاهده كرد.

ميشود. اين روش به دنبال بهينه كردن معيارها نيست، بلكه به دنبال حلهايي است كه بتوانند مقادير آرماني به كار رفته در مسأله را ارضا نمايند .با اين فرض، جوابها مي توانند متعلق به مجموعه پارتو هم نباشند.
1268732040128Downloaded from ijiepm.iust.ac.ir at 14:22 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:22 IRST on Saturday November 4th 2017

• (Lex (Z1,…, Zk: اين عبارت نشاندهنده رويكرد لكسيكوگرافيكي ميباشد كه در آن هيچ تعادلي بين معيارها از نظر تصميم گيرنده وجود ندارد و هر كدام از معيارها، از درجه اهميت خاصي نزد تصميمگيرنده، برخوردارند. در اين حالت ،مهمترين معيار از نظر تصميمگيرنده در رتبه اول قرار مي گيرد و مسأله به منظور بهينه كردن آن حل ميشود. در مرحله بعد به سراغ دومين معيار مهم از نظر تصميمگيرنده رفته و دوباره مسأله به منظور بهينه كردن معيار دوم و با شرط بهينگي بدست آمده جهت معيار اول در مرحله قبل حل مي شود و به همين ترتيب به صورت مرحله به مرحله به سراغ ديگر معيارها مي رود. اين كار تا زماني كه همه معيارها مورد بررسي قرار بگيرند، ادامه مييابد.

شكل
.1
طبقه

بند
ي

كل
ي

روش
هاي

مسائل

زمانبند
حل

ي

روش

زمانبندي

مسائل

حل
هاي

هاي
ايستا
هاي

روش

حل

مدل

حل

روش
مدل
هاي
پويا

هاي

)

تصميم
گيري
Real time
(
هاي

روش
كلاس

ي
ك

ابتكاري
هاي

روش

قواني

ن
توز
يع

سي
خب

ستمهاي
ره

سي
استنتاج

ستمهاي

فازي

سي

ستمهاي

عامل
بر

مبتني

شبكههاي

عصبي

ري

برنامه
زي

پويا

روش

و

شاخه
كرانه

روش
صفحات

برش

ابتكاري

فراابتكاري

Gupta

Palmer

CDS

غيره

SA

GA

TS

ACO



قیمت: تومان


دیدگاهتان را بنویسید