بیشینه‌سازی سود در مسئلۀ دوعاملی پذیرش و زمان‌بندی یکپارچۀ سفارش‌ها

نوع مقاله: مقاله پژوهشی

نویسندگان

1 استادیار، دانشکدة مهندسی صنایع و سیستم‌ها، دانشگاه صنعتی اصفهان

2 استاد، دانشکدة مهندسی صنایع و سیستم‌ها، دانشگاه صنعتی اصفهان

چکیده

در بازارهای رقابتی شرط بقای یک سازمان، جذب مشتریان بالقوه و حفظ مشتریان فعلی است؛بنابراین توجه به نیازها و خواسته‌های مشتریان بسیار مهم است. در این مقاله مسئلة پذیرش و زمان‌بندی سفارش‌ها، در حالتی بررسی شده است که دو نوع مشتری یا عامل در یک محیط تک‌ماشین برای رسیدن به اهداف خود با هم رقابت می‌کنند. هدف بیشینه‌سازی مجموع سود سفارش‌های عامل اول و درآمد سفارش‌های عامل دوم است؛ بنابراین فقط عامل اول جریمه دارد وتابع آن مجموع مغایرت زمان تکمیل و موعد تحویل است. سفارش‌های عامل دوم نیز دارای یک موعد تحویل مشترک بوده و این عامل هیچ سفارشهمراه به دیرکرد را نمی‌پذیرد. برای حل مسئله  مدلی ریاضی، یک الگوریتم ابتکاری و یک برنامه‌ریزی پویای شبه‌چندجمله‌ای ارائه شده است. نتایج حل این الگوریتم‌ها در مسائل نمونه حاکی از توانایی حل بهینة تمامی مسائل تا ابعاد 70 سفارش و %12/93 از مسائل تا ابعاد 150 سفارش توسط برنامه‌ریزی پویا است.

کلیدواژه‌ها


عنوان مقاله [English]

Maximizing Total Profit in Two-agent Problem of Order Acceptance and Scheduling

نویسندگان [English]

  • Mohammad Reisi-Nafchi 1
  • Ghasem Moslehi 2
  • Mehdi Bijari 2
1 Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran
2 Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran
چکیده [English]

In competitive markets, attracting potential customers and keeping current customers is a survival condition for each company. So, paying attention to the requests of customers is important and vital. In this paper, the problem of order acceptance and scheduling has been studied, in which two types of customers or agents compete in a single machine environment. The objective is maximizing sum of the total profit of first agent's accepted orders and the total revenue of second agent. Therefore, only the first agent has penalty and its penalty function is lateness and the second agent's orders have a common due date and this agent does not accept any tardy order. To solve the problem, a mathematical programming, a heuristic algorithm and a pseudo-polynomial dynamic programming algorithm are proposed. Computational results confirm the ability of solving all problem instances up to 70 orders size optimally and also 93.12% of problem instances up to 150 orders size by dynamic programming.

کلیدواژه‌ها [English]

  • Single machine
  • Orders acceptance
  • two-agent scheduling
  • mathematical programming
  • Dynamic programming

- مقدمه

امروزه در بازارهای رقابتی، رمز بقای یک تولیدکننده در جذب، حفظ و نگهداری مشتریان نهفته است؛اما در عمل نیازها و خواسته‌های مشتریان متفاوت است که در صورت تأمین‌نشدن این نیازها در بازار رقابتی، مشتری به رقبا مراجعه می‌کند و در عمل تولیدکننده متضرر خواهد شد. آنچه که در مطالعات انجام شده در پذیرش و زمان‌بندی سفارش‌ها مشاهده می‌شود، مغفول‌ماندن نیازهای متفاوت مشتریان است. سعی شده که در این مقاله این نقیصه با درنظرگرفتن دو دسته مشتری هریک با توابع جریمة متفاوت برطرف شود؛ به‌طوری که مشتریان دستة اول با افزایش دیرکرد، جریمه دریافت می کنند و با تحویل زودتر از موعد حاضر به دادن پاداش به تولیدکننده در قبال دریافت سفارش خود، زودتر از موعد نهایی هستند. از طرف دیگر مشتریان عامل دوم به هیچ عنوان حتی با دریافت جریمه نیز حاضر به تحویل گرفتن سفارش‌های همراه با دیرکرد نیستند. در دهة گذشته در ادبیات موضوع رقابت چند دسته کار بر یک محیط ماشینی هریک با اهداف متفاوت، تحت عنوان «زمان‌بندی چندعاملی[1]» مطرح شده که مطالعات در این حوزه نیز رو به افزایش است. بدیهی است که استفاده از این ایده در حوزة پذیرش و زمان‌بندی سفارش‌ها هم با واقعیت تطبیق بیشتری دارد و هم مورد توجه تولیدکنندگان خواهد بود. در ادامه برخی از مهم‌ترین مطالعات صورت‌گرفته در این دو زمینه به اختصار مرور می شود.

اسلاتنیک[2](2011)یک مقالة مروری دربارۀ مسئلة پذیرش و زمان‌بندی سفارش‌ها نوشته است. در این مقاله وی مطالعات صورت‌گرفته را دسته‌بندی کرده و در هر دسته آخرین دستاوردها را بیان کرده است. به‌منظور جلوگیری از طولانی‌شدن بحث، خوانندگان به این مقاله ارجاع داده می‌شوند. اسلاتنیک و مورتون[3] (1996) مسئلة پذیرش و زمان‌بندی سفارش‌ها را با هدف بیشینه‌سازی سود و درنظرگرفتن مجموع مغایرت وزنی به‌عنوان تابع جریمه بررسی کردند. از آنجا که با فرض معلوم‌بودن مجموعة سفارش‌های پذیرفته‌شده، تعیین توالی بهینة سفارش‌ها براساس ترتیب WSPT[4] به دست می‌آید، آنان چند خاصیت برای مسئلة اصلی ارائه کرده‌اند. در این مطالعه یک الگوریتم شاخه و کران و دو الگوریتم ابتکاری برای حل مسئله توسعه داده شده و نشان داده شده که شاخه و کران، مسائل نمونه را تا ابعاد 17 سفارش، به‌طور بهینه حل می‌کند. در ادامه قوش[5] (1997) نشان داد که مسئلة فوق NP-hardبود و برای حل آن دو الگوریتم برنامه‌ریزی پویای شبه‌چندجمله‌ای و یک الگوی تقریب کاملاً چندجمله‌ای (FPTAS[6]) با پیچیدگی  توسعه دادند.

اسلاتنیک و مورتون (2007) مسئلۀ پذیرش و زمان‌بندی سفارش‌ها در حالت تک‌ماشین را با درنظرگرفتن جریمۀ دیرکرد وزنی بررسی کردند. آنان نشان دادند که این مسئله NP-hard بود و از این رو برای حل آن یک رویۀ شاخه و کران و چند الگوریتم ابتکاری ارائه کردند. رام و اسلاتنیک[7] (2009) نیز یک الگوریتم ژنتیک برای همین مسئله توسعه دادند که جواب‌های با کیفیت بیشتری نسبت به الگوریتم‌های ابتکاری ارائه‌شده در ادبیات موضوع تولید می‌کند. نوبیبون و لئوس[8] (2011) نیز این مسئله را در حالتی تعمیم دادند که تعدادی سفارش از قبل پذیرفته‌شده و تعدادی سفارش در انتظار تصمیم وجود دارد. پس از بررسی پیچیدگی، این نویسندگان دو مدل برنامه‌ریزی خطی عدد صحیح مختلط و دو الگوریتم شاخه و کران با به‌کارگیری خواص ارائه‌شده توسط اسلاتنیک و مورتون (2007) و رام و اسلاتنیک (2009) ارائه کردند. نتایج محاسباتی آنان عملکرد این رویه‌ها را تحت سناریوهای مختلف مقایسه کرده است.

سیسارت و همکاران (2012) نیز مسئلة پذیرش و زمان‌بندی سفارش‌ها را با درنظرگرفتن ضرب‌الاجل تحویل برای سفارش‌ها و جریمة دیرکرد وزنی برای تأخیر در تحویل در بازة بین موعد تحویل و ضرب‌الاجل تحویل بررسی کردند. در این مطالعه برای هر سفارش زمان ورود و زمان آماده‌سازی وابسته به توالی در نظر گرفته شده است. آنان برای حل این مسئله یک الگوریتم جستجوی ممنوع (TS[9]) توسعه دادند و عملکرد آن را با دو الگوریتم ابتکاری موجود در ادبیات موضوع مقایسه کردند. چن و همکاران[10] (2014) بر مسئله‌ای که سیسارت و همکاران[11](2012) بررسی کردند، مطالعه انجام دادند و برای حل آن یک الگوریتم ژنتیک ارائه کردند. نتایج محاسباتی آنان حاکی از کیفیت بهتر جواب‌های به‌دست‌آمده در مقایسه با روش‌هایی است که سیسارت و همکاران (2012) ارائه کردند.

به‌طور رسمی در سال 2003، بیکر و اسمیت (2003) مسئلة زمان‌بندی چندعاملی را معرفی کردند. آنان نشان دادند که می‌توان مسئلة  را در زمان چندجمله‌ای حل کرد. همچنین نشان دادند که مسئلة  را می‌توان به مسئلة  تبدیل کرد و ثابت کردند که مسئلة  از نظر پیچیدگی NP-hard است و برای حل حالت خاص آن یعنی مسئلة  یک برنامه‌ریزی پویا ارائه کردند. یوان و همکاران (2005) نشان دادند که برنامه‌ریزی‌های پویایی که بیکر و اسمیت (2003)برای مسائل  و  ارائه کرده‌اند اشتباه هستند. آنان برای حل این مسائل یک الگوریتم با پیچیدگی چندجمله‌ای ارائه کردند.   

اگنتیس و همکاران[12] (2004) به بررسی مسائل زمان‌بندی دوعاملی با توابع هدف بیشینه مقدار یک تابع منظم[13]  ( )، تعداد کارهای همراه با دیرکرد ( ) و مجموع وزنی زمان‌های تکمیل  ( ) پرداختند. آنان سناریوهای مختلفی وابسته به تابع هدف هر عامل و نیز محیط کارگاهی، در نظر گرفتند و برای هر سناریو پیچیدگی مسائل مربوط را بررسی کردند. لیونگ و همکاران (2010) نیز در مطالعة خود به بررسی پیچیدگی مسائل زمان‌بندی دوعاملی با استفاده از ترکیبات مختلف توابع هدف ، ،   و مجموع دیرکرد ( ) در حالت کمینه‌سازی تابع هدف یک عامل و محدودکردن تابع عامل دوم پرداختند. آنان مسائل مختلفی را در حالت تک‌ماشین، ماشین‌های موازی یکسان و مجازبودن یا نبودن انقطاع برای کارهای هر عامل بررسی کردند؛ مثلاً آنان نشان دادند که مسئة  به‌طور عادی NP-hard[14] بود و برای هریک از مسائل  و یک الگوریتم شبه‌چندجمله‌ای ارائه کردند.

یین و همکاران (2012) مسئلة بهینه‌سازی مقیدِ کمینه‌سازی مجموع دیرکرد کارهای عامل اول با در نظر گرفتن محدودیت بر مقدار بیشینة مغایرت زمان تکمیل و موعد تحویل عامل دوم در حالت زمان‌های ورود برای هر کار، بررسی کردند. آنان یک مدل برنامه‌ریزی عدد صحیح و یک الگوریتم شاخه و کران برای حل بهینة مسئله ارائه کردند و برای دستیابی به جواب‌های نزدیک بهینه در مسائل بزرگ، یک الگوریتم فرااِبتکاری بهینه‌سازی ازدواج در زنبورهای عسل[15] ارائه کردند. یین و همکاران (2013)مسئلة کمینه‌سازی مجموع وزنی زودکرد تمامی کارها با محدودکردن بیشینه زودکرد کارهای یکی از عوامل را مورد بررسی قرار دادند. آنان نشان دادند که این مسئله بهشدت NP-hard[16] است. برای حل آن نیز یک مدل MIP و یک الگوریتم شاخه و کران ارائه کردند. همچنین در این مطالعه یک الگوریتم شبیه‌سازی تبرید([17]SA) برای حل مسائل در ابعاد بزرگ ارائه شده است.

وو و همکاران (2013) مسئلة دوعاملی کمینه‌سازی مجموع زمان‌های تکمیل عامل اول و محدودکردن مجموع زمان‌های تکمیل عامل دوم با فرض درنظرگرفتن زمان ورود برای هر کار ( ) را مطالعه کردند. آنان نشان دادند که این مسئله به شدت NP-hard بود و برای حل بهینة آن یک الگوریتم شاخه و کران ارائه کردند. همچنین در این مطالعه یک الگوریتم اجتماع مورچگان[18] و چهار الگوریتم ژنتیک نیز برای یافتن جواب‌های نزدیک بهینه توسعه داده شده است. ژائو و لو (2013) نشان دادند که مسائل زمان‌بندی دوعاملی  و  دارای پیچیدگی NP-hard بود و برای هریک از این مسائل یک الگوریتم برنامه‌ریزی پویای شبه‌چندجمله‌ای ارائه کردند. همچنین بر مبنای این الگوریتم‌ها برای هر مسئله یک FPTAS نیز توسعه دادند. چنگ و همکاران (2013) برای حل مسئلة  یک الگوریتم شاخه و کران و یک الگوریتم SA توسعه داده و نشان دادند که الگوریتم SA دارای میانگین درصد خطای %5/0 در کل مسائل نمونه است.

لی و وانگ (2014) مسئلة زمان‌بندی سه‌عاملی کمینه‌سازی مجموع وزنی زمان‌های تکمیل کارهای عامل اول را مشروط به اینکه دامنة عملیات عامل دوم کوچک‌تر از یک مقدار معین باشد و فعالیت نگهداری و تعمیرات عامل سوم در یک بازة مشخص از زمان انجام شود، حل کرده‌اند. آنان یک الگوریتم شاخه و کران برای حل بهینه و یک الگوریتم ژنتیک برای یافتن جواب‌های نزدیک بهینه ارائه کرده‌اند. شاخه و کران ارائه‌شده در این مقاله قادر به حل بهینة مسائل تا ابعاد 24 کار است. ژائو و لو (2014) یک الگوریتم تقریب با حد بدترین خطای 2 و پیچیدگی  برای مسئلة  ارائه کردند. همچنین آنها برای حالتی که تعداد ماشین‌های موازی برابر دو ماشین باشد یک الگوریتم چندجمله‌ای با پیچیدگی  توسعه دادند که حد بدترین خطای آن برابر 28/1 است.

بیشتر مطالعات انجام شده در ادبیات موضوع زمان‌بندی چندعاملی در حالت دوعاملی انجام شده است که به نظر می‌رسد دلیل آن افزایش پیچیدگی مسائل با بیش از دوعامل است و معدود مطالعات بیش از دوعامل نیز در حالت‌های ساده و خاص مسئله بوده است. در این مقاله نیز همان‌طور که گفته شد مسئلة پذیرش و زمان‌بندی سفارش‌ها در حالت دوعاملی بررسی شده است؛بنابراین نوآوری مقاله در بررسی توأم این دو موضوع و نیز تلاش بر حل بهینة مسئله است. بدیهی است که ایدة ترکیب دو مسئلة پذیرش و زمان‌بندی سفارش‌ها و زمان‌بندی چندعاملی در راستای کاربردی‌کردن هر دو مسئله است و در آینده می‌تواند از حوزه‌های جذاب پژوهشی باشد.

در ادامة مقاله، مسئلة موردنظر و نمادهای موردنیاز در بخش دوم تعریف شده و سپس در بخش سوم یک مدل ریاضی، یک الگوریتم ابتکاری و یک برنامه‌ریزی پویای شبه‌چندجمله‌ای برای حل مسئله ارائه شده است. در بخش چهارم نیز نتایج حل روش‌های توسعه‌داده‌شده بر مسائل نمونه ارائه و تحلیل شده است. در انتها در بخش پنجم، نتیجه‌گیری و پیشنهادهایی برای مطالعات آتی ذکر شده است.

2- تعریف مسئله و نمادهای موردنیاز

در این مقاله مسئلة دوعاملی پذیرش و زمان‌بندی سفارش‌ها در محیط تک‌ماشین با هدف بیشینه‌کردن مجموع سود سفارش‌های پذیرفته‌شدة عامل اول و درآمد سفارش‌های پذیرفته‌شدة عامل دوم در حالت مجاز‌نبودن دیرکرد برای سفارش‌ها عامل دوم بررسی می‌شود. تابع جریمة عامل اول نیز مجموع مغایرت زمان تکمیل و موعد تحویل در نظر گرفته شده که معنای آن دریافت پاداش درصورت تحویل زودتر از موعد و پرداخت جریمه درصورت تأخیر در تحویل می‌باشد. برای سفارش‌ها عامل دوم نیز موعد تحویل مشترک در نظر گرفته شده است. همچنین به‌هنگام پردازش هر سفارش پذیرفته‌شده انقطاع مجاز نیست و بیکاری عمدی ماشین نیز توجیهی ندارد. برخی نمادهای استفاده‌شده برای بیان مسئله عبارت‌اند از:

 : مجموعة کل سفارش‌ها

 : تعداد کل سفارش‌ها

 : تعداد سفارش‌های متعلق به عامل

                                                                   ( )

 : مجموعة سفارش‌های متعلق به عامل

(  و )      ( )

 : سفارش iمتعلق به عامل

(  و )

 : مدت‌زمان پردازش

(  و )

: مجموع زمان پردازش سفارش‌های عامل اول

 ( )

: مجموع زمان پردازش سفارش‌های عامل دوم

( )

: مجموع زمان پردازش کل سفارش‌ها

 ( )

 : درآمد     (  و )

 : زمان تکمیل (  و )

 : زمان تکمیل  در توالی

(  و )

 : موعد تحویل (  و )

 : موعد تحویل مشترک سفارش‌ها عامل دوم

( )

 : مغایرت زمان تکمیل و موعد تحویل ، که برابر با است.(  و )

 : اگر برای مقدار  مثبت باشد، این سفارش همراه با دیرکرد است و مقدار  برابر 1 و در غیر این صورت برابر صفر قرار می‌گیرد.

(  و )

بر این اساس مسئلة موردبررسی را می‌توان مطابق نمادگذاری سه‌جزئی گراهام و همکاران (1979) به صورت‌  نشان داد. در این نمادOA نشان‌دهندة پذیرش یا رد سفارش‌هااست و موعد تحویل مشترک سفارش‌های عامل دوم برابر است.

3- بررسی مسئله

در مسئلة  با فرض اینکه تعداد سفارش‌های عامل اول صفر در نظر گرفته شود، این مسئلة به فرم ساده‌تر تبدیل می‌شود که در آن هر سفارش یک درآمد و یک زمان پردازش دارد و سفارش‌های پذیرفته‌شده باید قبل از موعد تحویل مشترک  به اتمام برسند. همان‌طور که مشاهده می‌شود مسئلة فوق، یک مسئلة کوله‌پشتی است که دارای پیچیدگی به‌طور عادی NP-hardاست(گری و جانسون (1979)؛ از این رو، می‌توان نتیجه گرفت که پیچیدگی مسئلة  نیز حداقل به‌طور عادی NP-hard است؛ اما از آنجا که در ادامه برای این مسئله یک برنامه‌ریزی پویای شبه‌چندجمله‌ای ارائه شده است، پیچیدگی دقیق مسئله به‌طور عادی NP-hardاست. در رابطه با این مسئله، دو لم زیر ارائه می‌شود:

لم 1:با فرض معلوم‌بودن مجموعة سفارش‌های پذیرفته‌شدة هر عامل، یک توالی بهینه وجود دارد؛ به‌طوری که در آن سفارش‌های پذیرفته‌شدة عامل دوم به ترتیب دلخواه پشت سر هم و قبل از  زمان‌بندی شده‌اند.

اثبات: در هر توالی بهینه با شیفت‌دادن سفارش‌های پذیرفته‌شدة عامل دوم به سمت موعد تحویل مشترک  (سمت راست)، زمان تکمیل سفارش‌های پذیرفته‌شدة عامل اول در قبل از موعد تحویل  افزایش نخواهد یافت و زمان تکمیل سفارش‌های عامل اول در بعد از  نیز ثابت خواهد ماند؛بنابراینمجموع مغایرت عامل اول افزایش ندارد و می‌توان در هر توالی بهینه، سفارش‌های پذیرفته‌شدة عامل دوم را به‌سمت موعد تحویل  شیفت داد. همچنین به‌دلیل موعد تحویل مشترک سفارش‌ها عامل دوم، ترتیب قرارگرفتن آنها در قبل از  می‌تواند به‌طور دلخواه باشد.      ■

لم 2:با فرض معلوم‌بودن مجموعة سفارش‌های پذیرفته‌شدة هر عامل، یک توالی بهینه وجود دارد که در آن سفارش‌های پذیرفته‌شدة عامل اول به ترتیب غیرنزولی از زمان پردازش (SPT[19]) زمان‌بندی شده‌اند.

اثبات:بدیهی است که سفارش‌های عامل اول در قبل و بعد از بلوک سفارش‌های عامل دوم به‌تنهایی از ترتیب SPT پیروی می‌کنند؛ بنابراین کافی است ثابت شود که این ترتیب به‌طور سراسری و بین کلیة سفارش‌های قبل و بعد از بلوک عامل دوم نیز برقرار است؛ از این رو فرض کنید که در توالی بهینة ، ترتیب SPT بین سفارش‌های عامل اول رعایت نشده باشد. بدیهی است که توالی بهینه امکان‌پذیر است. حال فرض می‌شود که در توالی  دو سفارش دلخواه که ترتیب SPT سفارش‌های عامل اول را بر هم زده‌اند مانند  و  ( ) انتخاب شده و با جابه‌جایی آنها توالی جدیدی با نام  ایجاد شود به‌طوری که سفارش  قبل از سفارش  قرار گیرد. این دو توالی مطابق لم 1 در شکل 1 نشان داده شده‌اند. در این توالی‌ها،  ( ) بلوک‌هایی از سفارش‌های عامل اول و  بلوک سفارش‌های عامل دوم است.

مطابق شکل 1، زمان تکمیل سفارش‌ها درون بلوک  و  در هر دو توالی یکسان است. برای هر سفارش  درون بلوک‌های  و ، رابطة  و نیز روابط  و  برقرار است؛ بنابراین مجموع مغایرت سفارش‌های پذیرفته‌شدة عامل اول در توالی  کوچک‌تر یا مساوی مجموع مغایرت این سفارش‌ها در توالی است. همچنین از آنجا که زمان تکمیل سفارش‌های درون بلوک  نیز افزایش نداشته، این توالی امکان‌پذیر است و می‌توان نتیجه گرفت که توالی  نیز یک توالی بهینه است. همین رویه را برای سایر سفارش‌هایی که ترتیب SPT را بر هم زده‌اند می‌توان ادامه داد تا ترتیب SPT برای سفارش‌های عامل اول برقرار شود و از آنجا که مقدار مجموع درآمد سفارش‌های پذیرفته‌شدة هر دو توالی یکسان است، اثبات کامل است.             ■

نتیجة1: بر اساس لم‌های فوق می‌توان فرمت کلی جواب بهینه را به‌صورت یک توالی با سه بلوک در نظر گرفت که بلوک وسط از سفارش‌های پذیرفته‌شدة عامل دوم و بلوک‌های اول و سوم از سفارش‌های پذیرفته‌شدة عامل اول تشکیل شده‌اند که ترتیب کلی سفارش‌های عامل اول از ترتیب SPT پیروی می‌کند.

در زیر یک حد بالا برای مسئله ارائه می‌شود؛ در حالتی که تعدادی از سفارش‌های عامل دوم از قبل پذیرفته یا رد شده‌اند. در این حد بالا ترتیبی از سفارش‌های  مجازی با نام  بهره گرفته شده که با استفاده از سفارش‌های عامل اول ایجاد می‌شود؛ به‌طوری که زمان پردازش، موعد تحویل و درآمد سفارش‌های عامل اول به‌ترتیب به‌طور غیرنزولی، غیرصعودی و غیرصعودی به سفارش‌های مجازی تخصیص یابد. همین ترتیب برای سفارش‌های تعیین‌ِتکلیف‌نشدة عامل دوم با نام  نیز استفاده شده است. همچنین برای نشان‌دادن تعداد اعضای یک مجموعه مانند  نماد  به کار رفته است.

لم 3 (حد بالا): فرض می‌شود که مجموعة سفارش‌های پذیرفته‌شده و ردشدة عامل دوم به‌ترتیب  و  باشد و مقداری مانند ( ) وجود داشته باشد؛ به‌طوری که روابط  و  برقرار باشند. همچنین می‌توان سفارش‌های درون  را بلافاصله قبل از  به ترتیب دلخواه قرار داد و از ابتدای ترتیب  سفارش‌های مجازی را تا زمانی که قبل از  جا شده و مقدار سود آنها مثبت است، زمان‌بندی کرد.

 

 

شکل 1. توالی‌های  و  در اثبات لم 2

 

سپس سفارش‌های عامل دوم را تا حد امکان به سمت چپ شیفت داد و مابقی سفارش‌های ترتیب  را بعد از بلوک عامل دوم تا زمانی که سود آنها مثبت است، زمان‌بندی کرد. اگر در ترتیب حاصل، مجموع سود حاصل از سفارش‌های مجازی عامل اول به‌مقدار  افزوده شود، یک حد بالا برای مسئله به دست آمده است.

اثبات:مقدار  برابر با مجموع درآمد سفارش‌های پذیرفته‌شدة عامل دوم است. در صورتی که قرار باشد فضای باقیمانده در قبل از  تنها با سفارش‌های تعیینِ‌تکلیف‌نشدة عامل دوم پر شود، قراردادن سفارش‌ها در این فضا، از ابتدای ترتیب  به‌دلیل اینکه با افزایش مدت‌زمان پردازش، درآمد هر سفارش نیز کاهش می‌یابد، می‌تواند یک حد بالا برای این حالت ایجاد کند که مقدار آن برابر  است. حال فرض می‌شود که فضای قبل از بلوک عامل دوم و نیز بعد از آن با سفارش‌های عامل اول پر باشد. بدیهی است با ورود سفارش‌های ترتیب ، در صورتی که سود یک سفارش مجازی مثبت نشود به‌دلیل افزایش زمان پردازش سفارش بعدی در ترتیب  و کاهش موعد تحویل آن، مقدار مغایرت آن کاهش می‌یابد و چون درآمد آن نیز کم می‌شود، سود این سفارش و سفارش‌های بعدی نیز مثبت نخواهد شد. همچنین سفارش‌های پذیرفته‌شده از ترتیب  نیز به‌دلیل تخصیص غیرصعودی درآمد و موعد تحویل بهترتیب غیرنزولی از زمان پردازش، در بهترین حالت ممکن از نظر مجموع سود قرار دارند؛ بنابراین با افزودن مجموع سود این سفارش‌ها به‌مقدار یک حد بالا برای مسئله حاصل می‌شود.                    n

نتیجة2: در لم 3 در صورتی که کلیة سفارش‌های عامل دوم و تعدادی از سفارش‌های عامل اول، تعیینِ‌تکلیف شده باشد، حد بالای مسئله را می‌توان با تشکیل  برای سفارش‌های تعیینِ‌تکلیف‌نشدة عامل اول و زمان‌بندی آنها مطابق نتیجة 1، در کنار سفارش‌های پذیرفته‌شدة هر دو عامل و افزودن سود سفارش‌های مجازی زمان‌بندی‌شده به‌مقدار تابع هدف حاصل از سفارش‌های پذیرفته‌شدة هر دو عامل به دست آورد.

1-3- مدل برنامه‌ریزی ریاضی M1

براساسنتیجة 1 برای مسئلة موردبررسی می‌توان یک مدل ریاضی عدد صحیح مختلط ارائه کرد. متغیرهای تصمیم زیر برای نوشتن مدل تعریف شده است:

 : اگر  پذیرفته شود و قبل از  به اتمام برسد، مقدار 1 و در غیر این صورت مقدار صفر می‌گیرد. ( )

 : اگر  پذیرفته شود و بعد از  به اتمام برسد، مقدار 1 و در غیر این صورت مقدار صفر می‌گیرد. ( )

 : اگر  پذیرفته شود مقدار 1 و در غیر این صورت مقدار صفر می‌گیرد. ( )

 : برابر زمان تکمیل سفارش پذیرفته‌شدة  است، اگر این سفارش قبل از  به اتمام برسد و در صورت پذیرفته‌نشدن برابر صفر است. ( )

 : برابر زمان تکمیل سفارش پذیرفته‌شدة  است؛ اگر این سفارش بعد از  به اتمام برسد و در صورت پذیرفته‌نشدن برابر صفر است.

( )

با استفاده از متغیرهای فوق مدل ریاضی برنامه‌ریزی خطی مختلط عدد صحیح زیر با نام M1 برای مسئله ارائه می‌شود. مطابقلم 2 در این مدل فرض شده که سفارش‌های عامل اول بهترتیب SPT شماره‌گذاری شده‌اند.

 

 

                 

 

   

 

                  

                

 

,

در مدل فوق رابطة تابع هدف مجموع سود سفارش‌های پذیرفته‌شدة عامل اول و درآمد سفارش‌های پذیرفته‌شدة عامل دوم را نشان می‌دهد. محدودیت برای جلوگیری از قرارگرفتن یک سفارش از عامل اول به‌طور هم‌زمان در قبل و بعد از  نوشته شده است. در محدودیت‌های و زمان تکمیل سفارش‌های عامل اول محاسبه شده که در آنها  و  دو عدد بزرگ به‌ترتیب با حداقل مقادیر  و  هستند. محدودیت نیز برای جلوگیری از دیرکردداشتن سفارش‌های پذیرفته‌شدة عامل دوم و نیز جلوگیری از بیشترشدن زمان تکمیل سفارش‌های پذیرفته‌شده از عامل اول که قبل از بلوک عامل دوم قرار دارند، از مقدار  نوشته شده است. محدودیت ضامن مثبت‌بودن متغیرهای مربوط به زمان تکمیل سفارش‌های عامل اول و بالاخره رابطة نشان‌دهندة صفرویک‌بودن سایر متغیرهای مسئله است.

مدل فوق دارای  متغیر صفرویک،  متغیر پیوسته و  محدودیت است. بر این اساس تعداد متغیرها و محدودیت‌های این مدل تابعی خطی و درجه یک از تعداد سفارش‌های هر عامل است.

2-3- الگوریتم ابتکاری GAO

 در این قسمت یک الگوریتم ابتکاری حریصانه با نام GAO، برای حل مسئله ارائه می‌شود. در این الگوریتم کلیة سفارش‌ها به ترتیب غیرصعودی مقدار  مرتب شده و به همین ترتیب نیز به توالی جواب افزوده می‌شوند. در صورتی که مقدار تابع هدف افزایش نیابد سفارش واردشده از توالی حذف می‌شود. درنهایت توالی جواب به‌عنوان خروجی ارائه می‌شود. گام‌های این الگوریتم به‌قرار زیر است:

گام 1:    سفارش‌ها را به ترتیب غیرصعودی از مقدار  مرتب کنید و این ترتیب را [20]  بنامید.توالی جواب را  بنامید و قرار دهید ،  و .

گام 2:    اگر  به گام 8 بروید و در غیر این صورت سفارش  ام از ترتیب  را  نامیده و اگر این سفارش متعلق به عامل اول است به گام 3 بروید و در غیر این صورت به گام 4 بروید.

گام 3:    سفارش را در توالی  طوری قرار دهید که ترتیب SPTسفارش‌های عامل اول در این توالی حفظ شود؛ سپس به گام 5 بروید.

گام 4:    اگر مجموع زمان پردازش سفارش‌های عامل دوم در توالی به علاوة زمان پردازش سفارش بزرگ‌تر از  است به گام 7 بروید و در غیر این صورت سفارش را در توالی  بعد از آخرین سفارش از عامل دوم قرار دهید وبه گام 5 بروید.

گام 5:    اگر زمان تکمیل آخرین سفارش از عامل دوم در توالی  بزرگ‌تر از  است؛ تا زمانی که این مقدار کوچک‌تر یا مساوی  شود، آخرین سفارش از عامل اول در قبل از بلوک سفارش‌های عامل دوم را به بعد از این بلوک منتقل کنید.

گام 6:    اگر مقدار تابع هدف توالی  کوچک‌تر یا مساوی مقدار  است، سفارش  را از توالی  حذف کنید و در غیر این صورت مقدار  را برابر با مقدار تابع هدف توالی  قرار دهید.

گام 7:    قرار دهید  و به گام 2 بروید.

گام 8:    توالی  را  به‌عنوان جواب ارائه دهید.

گام 9:    پایان.

درشکل 2 نیز فلوچارت الگوریتم فوق نشان داده شده است.

پیچیدگی گام 1 الگوریتم GAO به‌دلیل مرتب‌کردن سفارش‌های هر عامل  است. گام‌های 3 تا 6 نیز با پیچیدگی  به تعداد  بار تکرار می‌شود؛ از این رو پیچیدگی الگوریتم GAO  است.

3-3- الگوریتم برنامه‌ریزی پویای DP1

در این قسمت یک الگوریتم برنامه‌ریزی پویا با نام DP1 و پیچیدگی شبه‌چندجمله‌ای برای حل مسئله توسعه داده شده است. این الگوریتم دارای دو فاز است که در فاز اول، سفارش‌های عامل دوم به ترتیب دلخواه وارد می شود و پس از تولید حالت‌های جدید با به‌کارگیری حدود بالا و پایین و یک اصل غلبه، فضای حالت شماره 1 به‌روز می‌شود و این کار تا اتمام سفارش‌های عامل دوم ادامه می‌یابد. در فاز دوم به‌ترتیب هریک از حالـت‌هـای درون فضــای حالـتشماره 1 در فضای جدیدی به‌نام فضای حالت شماره 2 قرار گرفته و واردکردن سفارش‌های عامل اول آغاز می‌شود. حالت‌های جدید، تولید می‌شود و پس از مقایسة حدود بالا و پایین و به‌روزرسانی فضای حالت شماره 2 این روند تا اتمام ورود سفارش‌های عامل اول ادامه می‌یابد. سپس بهترین جواب به‌دست‌آمده تاکنون از بین حالت‌های نهایی فضای حالت شماره 2 به‌روز شده و فضای حالت شماره 2 تهی می‌شود. حال این رویه با ورود حالت بعدی از فضای حالت شماره 1 به فضای حالت شماره 2 ادامه می‌یابد تا درنهایت جواب بهینه حاصل شود.

 

 

شکل 2. فلوچارت الگوریتم GAO

 

با توجه به نتیجة 1، نحوة نمایش حالت‌ها در فضای حالت در این الگوریتم به‌صورت  درنظر گرفته شده استکه در آن  مقدار تابع هدف،  و  به مجموع زمان پردازش سفارش‌های پذیرفته‌شدة عامل اول با زمان تکمیل به‌ترتیب قبل و بعد از ،  مجموع زمان پردازش سفارش‌های پذیرفته‌شدة عامل دوم و  مقدار مجموع مغایرت سفارش‌های پذیرفته‌شدة عامل اول است. هر حالت در فاز اول در صورتی در فضای حالت قرار داده می‌شود که هیچ‌کدام از سفارش‌های پذیرفته‌شدة عامل دوم در آن دیرکرد نداشته باشند. گام‌های الگوریتم DP1 به‌شرح زیر است:

گام 1:    سفارش‌های عامل اول را بهترتیب SPT در مجموعة  قرار دهید.

سفارش‌های عامل دوم را به ترتیب دلخواه در مجموعة  قرار دهید.

حالت  را در فضای حالت شمارة 1 قرار دهید.

بهترین تابع هدف فعلی را برابر با مقدار تابع هدف خروجی الگوریتم ابتکاری GAO در نظر بگیرید.

گام 2:    در صورتی که  به گام 3 بروید و در غیر این صورت سفارش ابتدای  را بنامید و آن را از  حذف کنید و به گام 2-1 بروید.

گام 2-1:  برای تمامی حالت‌های موجود در فضای حالت شماره 1 مانند ، مقدار  را محاسبه کنید. اگر  است، حالت جدید  را ایجاد کنید. در پایان به گام 2-2 بروید.

گام 2-2:  (محاسبة حد بالا)برای هریک از حالت‌های جدید ایجادشده در گام 2-1، حد بالا را مطابق لم 3 محاسبه کنید و اگر این حد از بهترین تابع هدف فعلی بزرگ‌تر است آن را به فضای حالت شمارة 1 بیفزایید و در غیر این صورت این حالت را نادیده بگیرید. اگر حالت جدیدی به فضای حالت شمارة 1 اضافه شده به گام 2-3 و در غیر این صورت به گام 2 بروید.

گام 2-3:   (اصل غلبة 1)برای هر دو حالت  و  در فضای حالت شمارة 1، در صورتی که روابط  و  برقرار باشد، کافی است تنها حالت  در فضای حالت شمارة 1 نگه داشته شود. این شرایط را بر فضای حالت شمارة 1 اعمال کنید و پس از به‌روزرسانی آن به گام 2 بروید.

گام 3:    تعداد کل حالت‌های موجود در فضای حالت شمارة 1 را برابر  در نظر بگیرید و قرار دهید: .

گام 4:    اگر  به گام 7 بروید و در غیر این صورت حالت ام از فضای حالت شمارة 1 را در یک فضای جدید با نام فضای حالت شمارة 2 وارد کنید، قرار دهید:  و به گام 5 بروید.

گام 5:    در صورتی که  به گام 6 بروید؛ در غیر این صورت سفارش ابتدای  را بنامید و آن را از  حذف کنید و به گام 5-1 بروید.

گام 5-1:   برای هریک از حالت‌های درون فضای حالت شمارة 2 مانند ، مقدار  را محاسبه کنید و اگر ، حالت  و در غیر این صورت حالت  را ایجاد کنید و در پایان به گام 5-2 بروید.

گام 5-2:   (محاسبة حد بالا)برای هریک از حالت‌های جدید ایجادشده در گام 5-1، حد بالا را مطابق نتیجة 2 محاسبه کنید و اگر این حد از بهترین تابع هدف فعلی بزرگ‌تر است آن را به فضای حالت شمارة 2 بیفزایید و در غیر این صورت این حالت را نادیده بگیرید. اگر حالت جدیدی به فضای حالت شمارة 2 اضافه شده به گام 5-3 و در غیر این صورت به گام 5 بروید.

گام 5-3:   (اصل غلبة 2)برای هر دو حالت و  در صورتی که رابطه‌های ،  و برقرار باشد کافی است تنها حالت  در فضای حالت شمارة 2 نگه داشته شود. این شرایط را بر فضای حالت شمارة 2 اعمال کنید و پس از به‌روزرسانی آن به گام 5 بروید.

گام 6:    در صورتی که بهترین تابع هدف حالت‌های موجود در فضای حالت شمارة 2 بزرگ‌تر از بهترین تابع هدف فعلی است آن را جایگزین بهترین تابع هدف فعلی کنید. قرار دهید: ، فضای حالت شمارة 2 را تهی کنید و به گام 4 بروید.

گام 7:    بهترین تابع هدف فعلی را به‌عنوان جواب ارائه کنید.

گام 8:    پایان.

در ادامه اصول غلبة استفاده‌شده در گام‌های 2-3 و 5-3 الگوریتم DP1 در قالب دو لم اثبات می‌شود. این اصول کارآیی الگوریتم را بالا برده و منجر به دستیابی به پیچیدگی شبه‌چندجمله‌ای برای آن شده است.

لم 4 (اصل غلبة 1):در گام 2-2 الگوریتم DP1، در صورتی که دو حالت  و  با شرایط زیر وجود داشته باشند، می‌توان بدون ازدست‌دادن جواب بهینه حالت  را از فضای حالت حذف کرد.

                                     (8)

                              (9)

اثبات:فرض کنید با حذف حالت  از فضای حالت جواب بهینه از دست می‌رود، بدین معنی که این حالت منجر به رسیدن به جواب بهینه می‌شود. از طرفی از آنجا که در الگوریتم DP1، هر دو حالت فوق در فاز اول یعنی زمانی بررسی می‌شوند که تنها سفارش‌های عامل دوم وارد شده‌اند؛ بنابراین برای رسیدن به جواب بهینه در گام‌های بعدی الگوریتم هم می‌توان سفارش‌های باقیماندة عامل دوم و نیز سفارش‌های عامل اول را وارد کرد. در این صورت فرض کنید که مجموعة سفارش‌های عامل اول و دوم که باید به حالت  افزود تا جواب بهینه به دست آید به‌ترتیب  و  باشند. همچنین فرض می‌شود که مجموعة  به دو مجموعه، شامل سفارش‌های عامل اول با زمان تکمیل قبل و بعد از  به‌ترتیب با نام‌های  و  افزار شود. ( ).

از آنجا که جواب بهینه (که مطابق فرض اولیه از حالت به دست آمده)، یک جواب امکان‌پذیر است، داریم:

 

فرض کنید که  و  در توالی بهینة به‌دست‌آمده از حالت ، برابر مجموع زمان تکمیل سفارش‌های  و  باشند. حال اگر سفارش‌های درون و  به همین ترتیب به مجموعة سفارش‌ها قبل و بعد از بلوک عامل دوم در حالت  افزوده شوند و سفارش‌های مجموعة  نیز به بلوک عامل دوم در این حالت افزوده شوند، از آنجا که رابطة (9)  برقرار است، در آن صورت روابط  و  نیز برقرار است؛ بنابراین داریم:

 

از طرفی باز به‌دلیل برقراری رابطة (9) خواهیم داشت:

 

با ترکیب روابط و رابطة زیر به دست می‌آید که درحقیقت بیانگر امکان‌پذیری جواب به‌دست‌آمده از حالت  با افزودن ،  و به آن، با ترتیب گفته‌شده در بالا، است.

 

همچنین با توجه به برقراری رابطة (8) می‌توان نوشت:

 

با ترکیب روابط و این نتیجه به دست می‌آید که مقدار تابع هدف جواب به‌دست‌آمده از حالت  کمتر از حالت  نیست و هر دو جواب نیز امکان‌پذیر هستند، فرض بهینه‌بودن جواب به‌دست‌آمده از حالت  نقض می‌شود؛ از این رو این فرض باطل است و حذف حالت  منجر به ازدست‌رفتن جواب بهینه نمی‌شود.     n

لم 5 (اصل غلبة 2):در گام 8 الگوریتم DP1، در صورتی که دو حالت  و  با شرایط زیر وجود داشته باشند می‌توان بدون ازدست‌دادن جواب بهینه حالت  را از فضای حالت شمارة 2 حذف کرد.

                                     (15)

(16)

                              (17)

اثبات: مشابه اثبات لم 4 است.                     n

چون در فاز اول سفارش‌های عامل دوم وارد شده و این سفارش‌ها نیز دارای موعد تحویل مشترک هستند گویی یک مسئلة کوله‌پشتی طرح شده که در آن هدف، پرکردن فضای قبل از  با سفارش‌های عامل دوم است؛ به‌طوری که درآمد مربوطه حداکثر شود؛ از این رو با اعمال اصل غلبة 1 در گام 2-2، پیچیدگی این قسمت از الگوریتم با احتساب پیچیدگی حد بالای ارائه‌شده،برابر  خواهد بود. همچنین حداکثر تعداد حالت‌های درون فضای حالت شمارة 1 در پایان این فاز برابر است. سپس در فاز دوم به‌ازای هر حالت موجود در فضای حالت شمارة 1 به‌نوعی یک الگوریتم برنامه‌ریزی پویا اجرا می‌شود؛ بنابراین با به‌کارگیری اصل غلبة 2 در گام 5-3 حداکثر تعداد حالت‌های درون فضای حالت شمارة 2 برابر  خواهد بود که در آن  و  به‌ترتیب دامنة تغییرات  و است؛پس پیچیدگی اجرای فاز دوم با احتساب پیچیدگی حد بالا و درنتیجه پیچیدگی کل الگوریتم، برابر  است که می‌توان آن را به‌صورت نیز بیان کرد. همچنین در صورتی که زمان پردازش همگی سفارش‌ها برابر واحد باشد، این الگوریتم در زمان چندجمله‌ای و با پیچیدگی  قادر به حل مسئله است.

4- نتایج محاسباتی

به‌منظور بررسی کارایی الگوریتم‌های ارائه‌شده در حل مسئلة دوعاملی پذیرش و زمان‌بندی  سعی شده تا  کیفیت آنها در حل مسائل نمونه بررسی شود. این الگوریتم‌ها در محیط برنامه‌نویسی Visual C# 2010 پیاده‌سازی شده و بر یک دستگاه رایانه با مشخصات Intel® Core™ i7-2600 CPU 3.4 GHz و 4 GB RAMدر محیط سیستم عامل Windows 7 به اجرا گذاشته شده‌اند. همچنین مدل ریاضی M1با استفاده از نرم‌افزار CPLEXنسخة 1/11حل شده است. محدودیت زمانی حل نیز در کلیة مسائل برابر 3600 ثانیه در نظر گرفته شده است.

 با توجه به جدیدبودن مسئلة پذیرش و زمان‌بندی سفارش‌های دوعاملی که در این مقاله طرح شده، سعی شده تا با الگوگیری از نحوة تولید مسائل نمونه در ادبیات موضوع پذیرش و زمان‌بندی سفارش‌ها و نیز مطالعات گذشته در زمینة زمان‌بندی چندعاملی و اعمال تغییراتی براساس شرایط مسئلة جدید، به طراحی مسائل نمونه به‌طور تصادفی پرداخته شود.

از آنجا که آزمایش‌های مقدماتی نشان‌دهندة این است که تنها پارامترهای تعداد سفارش هر عامل، درآمد و مدت‌زمان پردازش سفارش‌های عامل اول و عامل دیرکرد ( ) عامل اول در کارایی و عملکرد الگوریتم ارائه‌شده تأثیرگذار است، در ادامه تنها این پارامترها در آزمایش‌های محاسباتی در نظر گرفته شده‌اند؛بنابراین زمان‌های پردازش سفارش‌های عامل اول از توزیع یکنواخت گسسته در دو بازة  مطابق نوبیبون و لئوس (2011) و  براساس ادبیات موضوع زمان‌بندی چندعاملی (سلطانی و همکاران (2010)، چنگ و همکاران (2013) و لی و همکاران (2010)) تولید شده است. موعد تحویل هر سفارش از عامل اول مانند  نیز مطابق مطالعات قبلی (سلطانی و همکاران (2010)، لی و همکاران (2010)، نوبیبون و لئوس (2011) و یین و همکاران (2012) و از توزیع یکنواخت گسسته به‌صورت  تولید شدهکه در آن  و  به‌ترتیب عامل دیرکرد و عامل پراکندگی موعد تحویل عامل اول هستند. در این مطالعه مقادیر 3/0 و 7/0 برای  در نظر گرفته شده است. به‌منظور بررسی تأثیر تعداد سفارش‌های هر عامل، در نیمی از مسائل تعداد سفارش‌های عامل اول نصف تعداد سفارش‌های عامل دوم ( ) و در نیمی دیگر دو برابر تعداد سفارش‌های عامل دوم ( ) لحاظ شده است. همچنین مقدار درآمد سفارش‌های عامل اول از توزیع یکنواخت گسسته در دو بازة  و  تولید شده است. مقادیر درنظرگرفته‌شده برای پارامترهای مسئله و سطوح مربوط به آنها در جدول نشان داده شده است.بدین ترتیب براساس مقادیر درنظرگرفته‌شده برای درآمد و زمان پردازش عامل اول،  عامل اول و ترکیب تعداد سفارش عامل‌ها تعداد 16 ( ) گروه مختلف با نام‌های G01 تا G16، شکل می‌گیرد. به‌ازای هریک از گروه‌های 16گانه، سه اندازة مسئلة 70، 110 و 150 و به‌ازای هر اندازه در هر سری 10 مسئلة نمونه بررسی شده است.

جدول(1):  مشخصات پارامترهای استفاده‌شده در تولید مسائل نمونه

نام پارامتر

نماد

مقدار

سطح

اندازه

n

70

110

150

70

110

150

تعداد سفارش عامل اول

n1

2n1=n2

Low

n1=2n2

High

درآمد عامل اول

qi_1

[1,2×pi1]

Low

[1,20×pi1]

High

زمان پردازش عامل اول

pi_1

[1,10]

Low

[1,100]

High

مقدار τ عامل اول

tou_1

3/0

Low

7/0

High

چون نتایج محاسباتی نشان داد که مدل ریاضی M1 قادر به حل کلیة مسائل نمونه تنها تا ابعاد 35 سفارش است و از طرفی الگوریتم DP1 مسائل را تا ابعاد 70 سفارش به‌طور کامل حل کرده است؛ در ادامه تنها نتایج الگوریتم DP1 ارائه می‌شود.برای بررسی تأثیر پارامترهای جدول بر الگوریتم DP1، از آنالیز واریانس[21] استفاده شده است؛ بنابراین با توجه به تعداد گروه‌ها و اندازه‌های مختلف، 48 (3×16) تیمار[22] در نظر گرفته شده است. گفتنی است که سه پیش‌فرض اصلی آنالیز واریانس شامل نرمال‌بودن و مستقل‌بودن باقیمانده‌ها و برابری واریانس‌ها بررسی شد و همة این پیش‌فرض‌ها پذیرفته شده‌اند. نتیجة این تحلیل در جدول (2) برای متغیر پاسخ «درصد مسائل نمونة بهینه حل‌شده توسط DP1 در 3600 ثانیه» به نمایش درآمده است.براساس جدول (1)نیز درصد مسائل بیشتری حل شده‌اند.

Source

S.S.*

d.f.**

M.S.***

F

P-Value

Model

333/151583

20

167/7579

339/22

000/0

n

000/22625

2

500/11312

343/33

000/0

n1

500/22687

1

500/22687

870/66

000/0

qi1

833/11020

1

833/11020

483/32

000/0

pi1

833/13020

1

833/13020

378/38

000/0

τ1

500/1687

1

500/1687

974/4

026/0

n * n1

000/22625

2

500/11312

343/33

000/0

n * qi1

667/8041

2

833/4020

851/11

000/0

n * pi1

667/10291

2

833/5145

167/15

000/0

n * τ1

000/1625

2

500/812

395/2

092/0

n1 * qi1

833/11020

1

833/11020

483/32

000/0

n1 * pi1

833/13020

1

833/13020

378/38

000/0

n1 * τ1

500/1687

1

500/1687

974/4

026/0

qi1* pi1

500/4687

1

500/4687

816/13

000/0

qi1* τ1

833/7520

1

833/7520

167/22

000/0

pi1 * τ1

833/20

1

833/20

061/0

804/0

Error

167/155729

459

279/339

 

 

Total

000/4470000

480

 

 

 

* S.S. : Sum of Squares

** d.f. : degree of freedom

*** M.S. : Mean of Squares

جدول (2): جدول آنالیز واریانس برای برای درصد مسائل نمونة بهینه حل‌شده

پارامترهای درنظرگرفته‌شده در این آزمایش در سطح اطمینان[23] 5درصد معنادار هستند. آثار متقابل پارامترها نیز به‌جز در دو مورد که مربوط به پارامتر  است، همگی در سطح اطمینان 5درصد معنادار هستند. در شکل 3 نیز آثار اصلی پارامترها بر متغیر پاسخ نشان داده شده است. همان‌طور که در این شکل نیز مشخص است کلیة پارامترها بر متغیر پاسخ اثرگذار هستند. بر این اساس با افزایش ابعاد مسئله درصد کمتری از مسائل به‌طور بهینه توسط DP1 حل شده‌اند؛ به‌طوری که در ابعاد 70، 110 و 150 سفارش به‌ترتیب %100، %62/95 و %75/83 از مسائل نمونه به‌طور بهینه حل شده‌اند. همچنین با قرارگیری سایر پارامترها در سطح Low نیز درصد مسائل بیشتری حل شده‌اند.

Source

S.S.*

d.f.**

M.S.***

F

P-Value

Model

333/151583

20

167/7579

339/22

000/0

n

000/22625

2

500/11312

343/33

000/0

n1

500/22687

1

500/22687

870/66

000/0

qi1

833/11020

1

833/11020

483/32

000/0

pi1

833/13020

1

833/13020

378/38

000/0

τ1

500/1687

1

500/1687

974/4

026/0

n * n1

000/22625

2

500/11312

343/33

000/0

n * qi1

667/8041

2

833/4020

851/11

000/0

n * pi1

667/10291

2

833/5145

167/15

000/0

n * τ1

000/1625

2

500/812

395/2

092/0

n1 * qi1

833/11020

1

833/11020

483/32

000/0

n1 * pi1

833/13020

1

833/13020

378/38

000/0

n1 * τ1

500/1687

1

500/1687

974/4

026/0

qi1* pi1

500/4687

1

500/4687

816/13

000/0

qi1* τ1

833/7520

1

833/7520

167/22

000/0

pi1 * τ1

833/20

1

833/20

061/0

804/0

Error

167/155729

459

279/339

 

 

Total

000/4470000

480

 

 

 

* S.S. : Sum of Squares

** d.f. : degree of freedom

*** M.S. : Mean of Squares

شکل 3. نمودار آثار اصلی پارامترها، متغیر پاسخ: درصد مسائل نمونة بهینه حل‌شده توسط DP1

در جدول نتایج حل به‌ازای 16 گروه G01 تا G16، ارائه شده است.

در این جدول برای بررسی عملکرد الگوریتم ابتکاری GAO از معیار میانگین درصد انحراف نسبی (RPD[24])  استفاده شده که مطابق رابطة زیر محاسبه می‌شود:

                 

در رابطة فوق  و  به‌ترتیب مقدار تابع هدف حاصل از الگوریتم‌های DP1 (بهینه) و GAOاست.

در جدول می‌توان مشاهده کرد که با افزایش ابعاد مسائل، مدت‌زمان حل کل الگوریتم DP1 و نیز مدت‌زمان صرف‌شده در هریک از دو فاز این الگوریتم نیز افزایش یافته است؛ به‌طوری که به‌ترتیب، میانگین مدت‌زمان حل مسائل نمونة بهینه حل‌شده با ابعاد 70، 110 و 150 سفارش برابر 04/13، 86/298 و 22/416 ثانیه است.

 

جدول(3):  نتایج حل DP1 به‌ازای گروه‌های 16گانه

گروه

مقادیر پارامترها

تعداد نمونه بهینه از 10 نمونه

میانگین RPD برای  الگوریتم GAO

میانگین مدت زمان حل (ثانیه)

فاز اول: میانگین درصد حالاتِ

فاز دوم: میانگین درصد حالاتِ

ni

qi1

pi1

τ1

n

کل

فاز

اول

فاز

دوم

بررسی شده

حذف شده به دلیل

منتقل شده به فاز دوم

بررسی شده

حذف شده به دلیل

باقی مانده

حد بالا

اصل

غلبة 1

حد بالا

اصل

غلبة2

G01

2n1=n2

 

 

3/0

70

10

28/8

08/0

02/0

06/0

60/26

38/8

43/87

20/4

40/73

62/90

37/1

01/8

[1,2× pi1]

[1,10]

110

10

20/7

36/0

07/0

29/0

38/25

46/6

82/90

72/2

62/74

40/93

15/1

45/5

150

10

59/6

09/1

24/0

85/0

11/19

90/4

17/93

93/1

89/80

19/93

29/2

51/4

G02

7/0

70

10

15/24

25/0

02/0

23/0

80/5

91/2

36/92

74/4

20/94

79/87

71/3

50/8

110

10

99/24

76/1

10/0

66/1

66/2

75/1

12/95

12/3

34/97

17/90

60/4

23/5

150

10

21/25

92/7

29/0

64/7

61/1

42/1

30/96

28/2

39/98

30/89

44/6

26/4

G03

[1,100]

3/0

70

10

86/12

28/0

03/0

25/0

79/5

00/0

00/94

00/6

21/94

98/81

96/6

06/11

110

10

24/10

51/3

11/0

40/3

60/2

00/0

07/96

93/3

40/97

39/80

30/11

31/8

150

10

22/11

42/18

39/0

03/18

63/1

00/0

20/97

80/2

37/98

44/79

49/14

07/6

G04

7/0

70

10

44/11

67/0

03/0

64/0

98/1

00/0

03/94

97/5

02/98

15/89

39/3

47/7

110

10

72/10

22/18

11/0

11/18

34/0

00/0

07/96

93/3

66/99

79/86

47/8

75/4

150

10

54/12

83/132

38/0

44/132

14/0

00/0

21/97

79/2

86/99

01/88

48/8

51/3

G05

[1,20× pi1]

[1,10]

3/0

70

10

16/2

07/0

02/0

05/0

11/25

92/10

20/85

88/3

89/74

32/92

00/0

68/7

110

10

60/3

37/0

08/0

29/0

44/21

41/10

04/87

55/2

56/78

88/93

74/0

38/5

150

10

18/4

08/1

27/0

81/0

96/23

91/5

25/92

85/1

04/76

24/95

61/0

15/4

G06

7/0

70

10

49/15

28/0

02/0

26/0

00/6

91/2

36/92

73/4

00/94

87/87

58/3

55/8

110

10

08/23

12/5

10/0

02/5

67/1

77/1

09/95

13/3

33/98

63/85

59/8

78/5

150

10

62/21

62/38

33/0

29/38

87/0

41/1

31/96

28/2

13/99

82/86

79/8

38/4

G07

[1,100]

3/0

70

10

82/7

24/0

03/0

21/0

06/8

00/0

12/94

88/5

94/91

91/88

73/2

35/8

110

10

11/9

27/2

12/0

15/2

15/3

00/0

13/96

87/3

85/96

80/85

36/7

84/6

150

10

53/9

93/26

37/0

56/26

80/0

00/0

17/97

83/2

20/99

32/86

95/7

74/5

G08

7/0

70

10

95/14

64/1

03/0

61/1

03/1

00/0

06/94

94/5

97/98

09/85

27/6

64/8

110

10

44/16

09/76

12/0

97/75

18/0

00/0

09/96

91/3

82/99

00/83

36/11

64/5

150

10

21/14

81/678

38/0

44/678

05/0

00/0

17/97

83/2

95/99

53/78

11/17

36/4

G09

n1=2n2

[1,2× pi1]

[1,10]

3/0

70

10

59/2

43/0

01/0

42/0

95/0

07/12

18/78

75/9

05/99

84/84

25/8

91/6

110

10

71/2

44/3

05/0

39/3

57/0

15/10

21/84

64/5

43/99

46/82

71/12

83/4

150

10

65/2

58/23

16/0

42/23

35/0

69/6

20/89

11/4

65/99

69/83

53/12

78/3

G10

7/0

70

10

34/4

56/1

01/0

55/1

18/0

99/1

07/87

95/10

82/99

70/88

43/7

88/3

110

10

75/4

85/29

06/0

79/29

06/0

15/1

90/91

95/6

94/99

10/88

39/9

51/2

150

10

32/4

55/154

20/0

35/154

03/0

94/0

93/93

14/5

97/99

37/88

83/9

80/1

G11

[1,100]

3/0

70

10

27/3

84/16

02/0

82/16

08/0

00/0

72/87

28/12

92/99

91/75

72/16

37/7

110

10

99/2

37/119

08/0

28/119

03/0

00/0

20/92

80/7

97/99

47/78

56/16

97/4

150

5

04/1

12/390

28/0

83/389

01/0

00/0

31/94

69/5

99/99

33/93

26/4

41/2

G12

7/0

70

10

74/3

85/12

01/0

84/12

03/0

00/0

02/87

98/12

97/99

13/87

92/8

94/3

110

10

55/4

62/253

09/0

53/253

01/0

00/0

41/92

59/7

99/99

04/87

57/10

39/2

150

10

47/4

47/1884

27/0

21/1884

00/0

00/0

33/94

67/5

00/100

74/87

56/10

70/1

G13

[1,20× pi1]

[1,10]

3/0

70

10

58/1

48/0

01/0

47/0

56/1

42/15

91/74

67/9

44/98

72/89

07/4

21/6

110

10

83/1

38/11

06/0

32/11

66/0

59/11

92/82

50/5

34/99

41/88

04/7

55/4

150

10

62/2

40/112

21/0

19/112

22/0

10/5

58/90

32/4

78/99

43/84

89/11

68/3

G14

7/0

70

10

29/4

14/13

01/0

13/13

06/0

54/1

14/87

31/11

94/99

45/80

92/14

63/4

110

10

28/4

04/566

09/0

95/565

02/0

79/0

36/92

85/6

98/99

38/76

57/20

06/3

150

6

05/7

15/1962

27/0

88/1961

01/0

64/0

30/94

07/5

99/99

83/80

01/17

15/2

G15

[1,100]

3/0

70

10

27/2

77/3

01/0

76/3

11/0

00/0

72/87

28/12

89/99

31/86

46/7

23/6

110

10

06/3

25/834

07/0

18/834

01/0

00/0

28/92

72/7

99/99

75/80

49/14

76/4

150

3

41/1

39/810

29/0

11/810

01/0

00/0

56/94

44/5

99/99

87/92

69/4

44/2

G16

7/0

70

10

14/5

08/156

01/0

07/156

01/0

00/0

52/87

48/12

99/99

41/71

74/23

85/4

110

3

66/3

18/2856

08/0

10/2856

00/0

00/0

94/91

06/8

00/100

27/73

75/23

98/2

150

0

-

-

-

-

-

-

-

-

-

-

-

-

میانگین

 

 

22/8

02/239

13/0

89/238

06/4

71/2

58/91

77/5

94/95

75/85

04/9

21/5

 

همچنین براساس این جدول سخت‌ترین مسائل مربوط به گروه G16 است که در آن تمامی پارامتر‌ها در بیشترین مقدار خود قرار دارند؛ به‌طوری که در این گروه هیچ‌یک از 10 مسئلة نمونة تولیدشده در ابعاد 150 سفارش توسط DP1 حل نشده‌اند. بررسی نتایج نشان داد که دلیل این امر را می‌توان افزایش تعداد حالت‌های فضای حالت شمارة 2 در فاز دوم ذکر کرد که علی‌رغم عملکرد خوب اصل غلبة 2 و حدبالا در این فاز، تعداد حالت‌ها به‌طور چشم‌گیری افزایش داشته و بنابراین الگوریتم نتوانسته در مدت‌زمان تعیین‌شده همة آنها را بررسی کرده و به جواب دست پیدا کند.

نکتة دیگر در جدول، مدت‌زمان بسیار کم صرف شده در فاز اول الگوریتم است. همان‌طور که ذکر شد با توجه به اینکه در فاز اول به‌نوعی یک مسئلة کوله‌پشتی حل می‌شود و از آنجا که این مسئله به‌دلیل استفاده از اصل غلبة ارائه‌شده، در ابعاد موردبررسی بسیار سریع حل می‌شود، این امر دور از انتظار نیست. از طرف دیگر چون به‌ازای هر حالت نهایی در فضای حالت شمارة 1 یک الگوریتم برنامه‌ریزی پویا انجام می‌شود. بدیهی است که فاز دوم الگوریتم زمان‌بر باشد. براساس درصد حالات بررسی‌شدة هر فاز نیز می‌توان این امر را تأیید کرد.

با توجه به جدول می‌توان عملکرد اصول غلبه و حد بالا را نیز بررسی کرد. در فاز اول الگوریتم، اصل غلبة 1 به‌طور میانگین %58/91 از حالت‌های تولیدشده را حذف کرده است؛ اما بر خلاف فاز اول، در فاز دوم حد بالا عملکرد قابل‌ملاحظه‌ای داشته و در فاز دوم به‌طور میانگین %75/85 از حالت‌های این فاز به‌دلیل حد بالا حذف شده‌اند و به‌طور طبیعی درصد بسیار کمتری توسط اصل غلبة 2 می‌تواند حذف شود که این مقدار برابر %04/9است. به هر حال، مجموع حد بالا و اصول غلبه در فاز اول و دوم به‌ترتیب %29/94 و %79/94 از حالت‌های تولیدشده را حذف کرده‌اند.

همان‌طور که در گام 1 الگوریتم برنامه‌ریزی پویا آمده است، جواب الگوریتم ابتکاری GAO به‌عنوان یک جواب اولیه (حد پایین مسئله) برای استفاده در الگوریتم برنامه‌ریزی پویا استفاده شده است؛ بنابرایناز آنجا که هدف اصلی از توسعة این الگوریتم استفاده از جواب آن به‌عنوان در الگوریتم برنامه‌ریزی پویا بوده است، ادعای چندانی مبنی بر کیفیت جواب آن وجود ندارد. با این حال با میانگین درصد انحراف نسبی این الگوریتم در تمام گروه‌هایی که جواب بهینه از الگوریتم DP1 به دست آمده است، برابر %22/8 است که عملکرد قابل‌قبولی به نظر می‌رسد.

5- نتیجه‌گیری

در این مقاله یک مسئلة کاربردی در حوزة تحقیق در عملیات با عنوان پذیرش و زمان‌بندی سفارش‌ها بررسی شد. این مسئله در حالت وجود دو عامل رقابتی یا دو نوع مشتری مطالعه شدو یک مسئلة جدید با هدف بیشینه‌سازی مجموع سود سفارش‌های عامل اول و مجموع درآمد سفارش‌های عامل دوم با درنظرگرفتن مجموع مغایرت به‌عنوان تابع جریمة عامل اول بررسی شد. در این مسئله فرض شد که عامل دوم هیچ سفارش همراه با دیرکردی را نمی‌پذیرد و نیز سفارش‌های این عامل دارای موعد تحویل مشترک هستند. پس از اینکه نشان داده شد این مسئله به‌طور عادی NP-hard است؛ برای حل آن یک مدل ریاضی، یک الگوریتم ابتکاری و یک برنامه‌ریزی پویای شبه‌چندجمله‌ای ارائه شد. برای بررسی عملکرد الگوریتم‌ها نیز تعدادی مسئلة نمونه تولید شد و تأثیر پارامترهای لحاظ‌شده در تولید این مسائل با استفاده از آنالیز واریانس تحلیل شد. نتایج حل حاکی از قابلیت حل تمامی مسائل تا ابعاد 70 سفارش در مدت‌زمان اندک، توسط الگوریتم برنامه‌ریزی پویا است. همچنین در کل %12/93از مسائل تا ابعاد 150 سفارش توسط این الگوریتم در مدت‌زمان 3600 ثانیه به‌طور بهینه حل شده است. الگوریتم ابتکاری نیز با میانگین درصد انحراف نسبی %22/8عملکرد قابل‌قبولی از خود نشان داده است.

برای مطالعات آتی با توجه به جدیدبودن مسئلة موردبررسی می‌توان فرضیات متنوعی را در نظر گرفت و مسئله را حل کرد؛ مثلاً درنظرگرفتن تابع جریمة دیرکرد وزنی و یا محیط چندماشین می‌تواند جالب‌توجه باشد. همچنین می‌توان روش‌های حل دیگری نظیر شاخه و کران را بررسی کرد و با برنامه‌ریزی پویای ارائه‌شده مقایسه کرد. جدای از این موارد کلی می‌توان وزن‌دارکردن سفارش‌ها را نیز در مسئله افزود و یا حالت‌های مختلف دو عامل را نیزبررسی کرد که از آن جمله می‌توان درنظرگرفتن جریمة هر دو عامل در تابع هدف را ذکر کرد. همگی این موارد به کاربردی‌ترشدن مسئله کمک می‌کنند؛ ولی حل آن را پیچیده می‌کنند.



1 multi agent scheduling

2 Slotnick

3 Slotnick and Morton

4  Weighted Shortest Processing Time

5 Ghosh

6  Fully Polynomial Time Approximation Scheme

7 Rom and Slotnick

8 Nobibon and Leus

9 Tabu Search

10 Chen etal.

11  Cesaret et al.

12  Agnetis et al.

13 regular function

14 ordinary NP-hard

15 marriage in honey-bees optimization algorithm

16 strongly NP-hard

17 Simulated Annealing

18 ant colony

19  Shortest Processing Time

20 Revenue and Slack time to Processing time Ratio

21 ANalysis Of VAriance

22 treatment

23 confidence level

24  Relative Percentage Deviation

Agnetis, A., Mirchandani, P. B., Pacciarelli, D., & Pacifici, A. (2004). "Scheduling Problems with Two Competing Agents". Operations Research, 52(2), 229-242.

Baker, K. R., & Smith, J. C. (2003). "A multiple criterion model for machine scheduling". Journal of Scheduling, 6(1): 7-16.

Cesaret, B., Oğuz, C., & Salman, F. S. (2012). "A tabu search algorithm for order acceptance and scheduling". Computers and Operations Research, 39, 1197-1205.

Chen, C., Yang, Z., Tan, Y., & He, R. (2014). "Diversity Controlling Genetic Algorithm for Order Acceptance and Scheduling Problem". Mathematical Problems in Engineering, 2014, 1-11.

Cheng, T. C. E., Chung, Y. H., Liao, S. C., & Lee, W. C. (2013). "Two-agent singe-machine scheduling with release times to minimize the total weighted completion time". computers and Operations Research, 40, 353–361.

Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness (First Edition ed.): W. H. Freeman.

Ghosh, J. B. (1997). "Job selection in a heavily loaded shop". Computers and Operations Research, 24(2): 141-145.

Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). "Optimization and approximation in deterministic machine scheduling: A survey". Annals of Discrete Mathematics, 5, 287-326.

Lee, W. C., Chen, S. K., & Wu, C. C. (2010). "Branch-and-bound and simulated annealing algorithms for a two-agent scheduling problem". Expert Systems with Applications, 37(9), 6594–6601.

Lee, W. C., & Wang, J. Y. (2014). "A scheduling problem with three competing agents". Computers & Operations Research, 51(0), 208-217.

Leung, J. Y. T., Pinedo, M., & Wan, G. (2010). "Competitive Two-Agent Scheduling and Its Applications". Operations Research, 58(2), 458-469.

Nobibon, F. T., & Leus, R. (2011). "Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment". Computers and Operations Research, 38(1), 367-378.

Rom, W. O., & Slotnick, S. A. (2009). "Order acceptance using genetic algorithms". computers and Operations Research, 36, 1758–1767.

Slotnick, S. A. (2011). "Order acceptance and scheduling: A taxonomy and review". European Journal of Operational Research, 212, 1-11.

Slotnick, S. A., & Morton, T. E. (1996). "Selecting jobs for a heavily loaded shop with lateness penalties". Computers and Operations Research, 23(2), 131-140.

Slotnick, S. A., & Morton, T. E. (2007). "Order acceptance with weighted tardiness". Computers and Operations Research, 34, 3029–3042.

Soltani, R., Jolai, F., & Zandieh, M. (2010). "Two robust meta-heuristics for scheduling multiple job classes on a single machine with multiple criteria". Expert Systems with Applications, 37, 5951-5959.

Wu, C. C., Wu, W. H., Chen, J. C., Yin, Y., & Wu, W. H. (2013). "A study of the single-machine two-agent scheduling problem with release times". Applied Soft Computing, 13, 998–1006.

Yin, Y., Wu, C. C., Wu, W. H., Hsu, C. J., & Wu, W. H. (2013). "A branch-and-bound procedure for a single-machine earliness scheduling problem with two agents". Applied Soft Computing, 13, 1042–1054.

Yin, Y., Wu, W. H., Cheng, S. R., & Wu, C. C. (2012). "An investigation on a two-agent single-machine scheduling problem with unequal release dates". Computers and Operations Research, 39, 3062–3073.

Yuan, J. J., Shang, W. P., & Feng, Q. (2005). "A note on the scheduling with two families of jobs". Journal of Scheduling, 8, 537-542.

Zhao, K., & Lu, X. (2013). "Approximation schemes for two-agent scheduling on parallel machines". Theoretical Computer Science, 468, 114–121.

Zhao, K., & Lu, X. (2014). "Two approximation algorithms for two-agent scheduling on parallel machines to minimize makespan". Journal of Combinatorial Optimization, 1-19.


پی نوشت‌: