[toggle title=”عنوان انگلیسی”]
The use of a fuzzy multi-objective linear programming for solving a multi-objective single-machine scheduling problem
[/toggle]
[toggle title=”فهرست مطالب”]
چکیده
کلیدواژه ها
1. مقدمه
2. مدل زمان بندی چندهدفه تک-ماشینه
2.1. فرمول بندی مسئله
2.1.1 شاخص ها و پارامترها
2.1.2 متغیرهای تصمیم [گیری]
2.1.3 مدل ریاضی
3. الگوی (FMOLP) برنامه ریزی خطی چندهدفه فازی
3.1. الگوریتم
جدول 3 : داده های تولید شده برای 7 کار
4. نمونه های عددی و تحلیل عملکرد FMOLP
4.1 داده های اصلی برای نمونه های عددی
جدول 5 تابع های عضویت برای نمونۀ 7 کاره
جدول 6: راه حلهای FMOLP برای نمونۀ 6 کاره
جدول 7: راه حلهای FMOLP برای نمونۀ 7 کاره
جدول 8: نتایج بدست آمده از سناریو 1.
4.3. راه حلهای برونداد
جدول 10: نتایج تطبیقی برای نمونۀ 6کاره
جدول 11: نتایج تطبیقی برای نمونۀ 7کاره
4.4 تحلیل عملکرد/راندمان
5. نتیجه گیری
[/toggle]
[toggle title=”ترجمه چکیده”]
این مقاله به طرح الگوی برنامه ریزی خطی چندهدفه فازی (FMOLP) برای حل مسئلۀ زمان بندی یک ماشین چندهدفه پرداخته است. الگوی پیشنهادی تلاش دارد کل دیرکرد وزنی و زمان انجام کار را بطور همزمان کاهش دهد. در این مسئله، یک روش FMOLP پیشنهادی در ارتباط با میزان قابل قبول رضایت تصمیم گیرنده (DM) به کار رفته است. تعدادی از نمونه های عددی حل شده اند تا کارایی این رویکرد پیشنهادی اثبات گردد. نتایج مرتبط با رویکرد وانگ و لیانگ مقایسه شده اند. این نتایج محاسباتی ثابت می کنند که الگوی پیشنهادی FMOLP کارکردهای هدفی کمتر و میزان رضایت بیشتری را بدست آورده است.
[/toggle]
[toggle title=”ترجمه مقدمه”]
زمان بندی در بر گیرندۀ برنامه ریزی و مرتب کردن کارها در توالی منظم عملیات هاست تا نیازهای مشتری بر آورده شود [17]. زمان بندی مشاغل و کنترل جریانات آنها در روند تولید از مهمترین عناصر در هر سیستم تولیدی نوینی هستند. محیط تک-ماشینی، اساس انواع دیگر مسئلهات زمان بندی می¬باشد. در زمان بندی تک-ماشینی، تنها یک ماشین باید همۀ مشاغل را پردازش کند و همزمان عملکرد سیستم را مثل زمان انجام کار، زمان تکمیل کار، دیرکرد، تعداد کارهای دارای تأخیر، زمان تلف شده (بیکاری)، جمع کارهای دارای تأخیر و زودکرد بهینه سازی کند [18، 19]. بخش اعظم تحقیق در زمان بندی تک-ماشینی، به کاهش یک معیار ساده مربوط است. با این حال، مسئلهات زمان بندی اغلب بیش از یک جنبه را در بر می گیرد و در نتیجه ممکن است به تحلیل چندمعیاری نیاز داشته باشد [14]. ایشی و تادا [11] یک مسئله زمان بندی تک-ماشینی را با کاهش بیشترین تأخیر مشاغل در رابطه با تقدم فازی در نظر گرفتند. رابطۀ تقدم فازی، رابطۀ تقدم کریسپ (حلقه ای) را تخفیف می¬دهد و سطح رضایتی را در ارتباط با تقدم بین دو کار نشان می دهد. در نتیجه، این مسئله یک هدف دیگر را هم برای زیاد کردن سطح رضایت کمی که توسط روابط تقدم فازی بدست آمده در نظر می گیرد. الگوریتم لازم برای تعیین راه¬حلهای ناغالب بر اساس بازنموداری گرافی/هندسی روابط تقدم پیشنهاد شده است. آداموپولوس و پاپیس [2] رویکردی فازی-زبانی را برای یک مسئله توالی چندمعیاری مطرح کرده اند. آنها یک ماشین را در نظر گرفتند، که در آن هر کار با زمان فرآیند فازی تشخص می¬یابد. هدف آنها تعیین زمان فرآیند کارها و موعد مشترک و توالی دادن به کارهای ماشین بوده که ارزش جریمه¬ها با موعدهای مقرر مشخص شده، زودکرد ، دیرکرد مرتبط هستند. رویکرد دیگر برای حل مسئلۀ زمان بندی تک-ماشین چندهدفه توسط لی و همکاران [12] نشان داده شده است. آنها از ارزشهای زبانی برای ارزیابی هر معیار (بسیار ضعیف، ضعیف، مناسب، خوب و بسیار خوب) و بازنمایی ارزشهای نسبی آنها (بسیار غیرمهم، غیرمهم، نسبتاً مهم، مهم، و بسیار مهم) استفاده کردند. هم چنین، از روش جستجوی ممنوع به عنوان ابزاری تصادفی برای یافتن راه حلی نسبتاً-بهینه برای یک تابع هدفِ فازی ِتجمیعی استفاده شده است. چاناس و کاسپرسکی [6] دو مسئلۀ زمان بندی تک-ماشینی را با زمان فرآیند فازی و موعدهای مقرر فازی در نظر گرفتند. آنها دیرکرد فازی یک کار در یک توالی مشخص شده را [به عنوان] بیشینه فازی صفر و تفاوت بین زمان تکمیل فازی و موعد مقرر فازی این کار تعریف کردند. آنها در مسئلۀ اول، ارزش منتظره حداکثری دیرکرد فازی را کاهش دادند. در مسئلۀ دوم، ارزش منتظره یک دیرکرد فازی حداکثری را کاهش دادند. چاناس و کاسپرسکی [7] مسئلۀ زمان بندی تک-ماشینی را با پارامتریهای داده شده در قالب اعداد فازی در نظر گرفتند. فرض آنها این بوده که زمان بهینه در چنین مسئله ای را نمی توان دقیق تعیین کرد. آنها در مقاله شان، چگونگی محاسبۀ درجات بهینه-سازی ممکن و ضروری یک برنامۀ مشخص شده را در یکی از موارد خاص مسائل زمان بندی تک-ماشینی نشان دادند. عزیز اغلو و همکاران [4] مسئلۀ زمان بندی دو-معیاری ِکاهش دادن ِزودکرد بیشینه و تعداد کارهای دارای دیرکرد یک ماشین را بررسی کردند. فرضیه آنها این بود که وارد کردن زمان بیکاری ممنوع است. ابتدا، مسئلۀ کاهش زودکرد بیشینه را بررسی کردند و همزمان تعداد کارهای دارای دیرکرد را تا ارزش کمینه آن حفظ کردند. آنها هم چنین با ارزیابی تنها بخش کمی از راه حلهای مؤثر، رویه¬ای کلی را برای یافتن برنامۀ مؤثر کاهش دادن یک تابع مرکب/مضاعف برای این دو معیار طراحی کردند. آنها رویه هایی کلی را برای مسئلۀ دو-معیاری کاهش دادن زودکرد بیشینه و کارهای دارای تأخیر اتخاذ کردند. ارن و گونر [8] یک مسئلۀ زمان بندی تک-ماشینی دو-معیاره را بهمراه زمان آماده سازی وابسته به توالی در نظر گرفتند. تابع هدف، مجموع وزنی کل زمان تکمیل و کل زمان تأخیر را کاهش خواهد داد. یک مدل برنامه ریزی صحیح برای این مسئله طراحی شده، که به طبقۀ نامعین سخت (NP hard ) تعلق دارد. از آنجا که حل مسائل در بر گیرندۀ تعداد زیادی از کارهاست، از بحثی ابتکاری هم برای مسائل بزرگ استفاده شده است. برای ارتقاء عملکرد ِروش جستجوی ممنوع (TS)، نتایج الگوریتم ابتکاری پیشنهادی به عنوان راه حل اولیۀ روش TS در نظر گرفته شد. توکلی مقدم و همکاران [20] رویکرد فازی برنامه ریزی هدف را برای حل مدل مختلط عدد صحیح ِ یک مسئلۀ زمان بندی تک-ماشینی ارائه کردند که زمان جریان و کل تأخیر وزنی را کاهش می¬دهد. آنها به دلیل ناسازگاری بین این دو هدف، رویکرد فازی برنامه ریزی هدف را برای حل مدل ریاضی گسترده یک مسئلۀ زمان بندی تک-ماشینی پیشنهاد دادند. این رویکرد بر اساس میزان تمایل تصمیم گیرنده (DM) و تحمل مرتبط با ارزش¬های هدف ساخته شده است. هیو و همکاران [10] مسائل زمان بندی دو-معیاره تک-ماشینی را شامل دیرکرد وزنی بیشینه و تعداد کارهای دارای دیرکرد در نظر می گیرد. چون یکی از این دو معیار، معیار اصلی و دیگری معیار ثانویه می¬باشد، شواهد نامعین سخت را برای مسائل زمان بندی ارائه می¬کنند. آنها روابط پیچیدۀ بین مسائل مختلف را در نظر گرفتند و الگوریتم¬های چندجمله ای را برای موارد خاص و نیز الگوریتم های سریع ابتکاری را برای [این] مورد کلی پیشنهاد دادند. پر واضح است که راه حل بهینه مدلهای تک-هدفه ممکن بسیار متفاوت باشد زیرا هدف ممکن است متفاوت باشد (برای مثال، برای ساده ترین مدل یک ماشین بدون هیچ محدودیت دیگری، قانون کمترین زمان فرآیند (SPT) بهترین روش برای کاهش دادن ¯F ( یعنی میانگین زمان جریان) است ولی قانون زودترین موعد مقرر (EDD) برای کاهش بیشترین دیرکرد (Tmax) بهینه است. در واقع، هر تصمیم گیرندۀ خاص اغلب دوست دارد معیار داده شده را کاهش دهد. برای مثال، مدیر بازرگانی یک شرکت به رضایت مشتریان و در نتیجه کاهش دیرکرد علاقه دارد. از سوی دیگر، مدیر تولید دوست دارد استفاده از ماشین ها را با کاهش زمان انجام کار یا کار در حال انجام را با کاهش بیشینه زمان جریان بهینه کند. علاوه بر این، هر یک از این اهداف از منظر کلی معتبر است. از آنجایی که این اهداف ناسازگار هستند، ممکن است راه حلی برای یک هدف مفید باشد ولی برای اهداف دیگر مضر باشد. به همین دلیل، مسائل زمان بندی اغلب ماهیتی چند-هدفه دارند [14]. زیمرمان [22] ابتدا رویکرد FLP خود را به مسئلۀ برنامه ریزی خطی چند-هدفه (MOLP) گسترش داد. او برای هر تابع هدفی این مسئله فرض کرده بود که تصمیم گیرنده (DM) هدفی فازی دارد مثلاً « تابع های هدف باید لزوماً کمتر یا برابر با برخی از مقادیر باشند.» سپس تابع عضویت خطی متناظر تعریف شده و کمینه اپراتور(=عامل) پیشنهادی توسط بلمان و زاده [15] برای ترکیب همۀ تابع های هدف به کار رفته است. با معرفی یک متغیر کمکی، این مسئله را می تواند به مسئلۀ معادل و قراردادی LP تبدیل کرد و به راحتی با روش سیمپلکس حل کرد. اثر بعدی در مورد برنامه ریزی فازی هدف (FGP) در [9، 13، 15، 16] ارائه شده است. هدف این مقاله طرح و توسعه یک مدل برنامه ریزی خطی چند-هدفه فازی (FMOLP) برای حل مسئلۀ زمان بندی چندهدفه تک-ماشینه در محیط فازی می¬باشد. ابتدا، یک مدل MOLP از مسئلۀ زمان بندی چندهدفه تک-ماشینه ساخته شده است. این مدل تلاش دارد زمان انجام کار و کل دیرکرد وزنی را کاهش دهد. علاوه بر این، این الگو با تلفیق مجموعه های فازی و رویکردهای برنامه ریزی هدف، به مدل FMOLP تبدیل شده است.
[/toggle]
[toggle title=”مقدمه انگلیسی”]
Scheduling consists of planning and arranging jobs in an orderly sequence of operations in order to meet customer’s requirements [17]. The scheduling of jobs and the control of their flows through a production process are the most significant elements in any modern manufacturing systems. The single-machine environment is the basis for other types of scheduling problems. In single-machine scheduling, there is only one machine to process all jobs optimizing the system performance measures such as makespan, completion time, tardiness, number of tardy jobs, idle times, sum of the maximum earliness and tardiness [18] and [19]. In single-machine scheduling, most research is concerned with minimizing a single criterion. However, scheduling problems often involve more than one aspect and therefore may require multiple criteria analyses [14]. Ishi and Tada [11] considered a single-machine scheduling problem minimizing the maximum lateness of jobs with fuzzy precedence relations. A fuzzy precedence relation relaxes the crisp precedence relation and represents a satisfaction level with respect to the precedence between two jobs. Thus, the problem considers an additional objective in order to maximize the minimum satisfaction level that is obtained by the fuzzy precedence relations. An algorithm for determining non-dominated solutions is proposed based on a graph representation of the precedence relations. Adamopoulos and Pappis [2] presented a fuzzy-linguistic approach to a multi-criteria sequencing problem. They considered a single machine, in which each job is characterized by fuzzy processing times. The objective was to determine the processing times of jobs and the common due as well as to sequence the jobs on the machine where penalty values are associated with due dates assigned, earliness, and tardiness. Another approach to solve a multi-criteria single-machine scheduling problem is presented by Lee et al. [12]. They used linguistic values to evaluate each criterion (e.g., very poor, poor, fair, good, and very good) and to represent its relative weights (e.g., very unimportant, unimportant, moderately important, important, and very important). Also, a tabu search method is used as a stochastic tool to find the near-optimal solution for an aggregated fuzzy objective function. Chanas and Kasperski [6] considered two single-machine scheduling problems with fuzzy processing times and fuzzy due dates. They defined the fuzzy tardiness of a job in a given sequence as a fuzzy maximum of zero and the difference between the fuzzy completion time and the fuzzy due date of this job. In the first problem, they minimized the maximal expected value of a fuzzy tardiness. In the second one, they considered minimizing the expected value of a maximal fuzzy tardiness. Chanas and Kasperski [7] considered the single-machine scheduling problem with parameters given in the form of fuzzy numbers. It is assumed that the optimal schedule in such a problem cannot be determined precisely. In their paper, it is shown how to calculate the degrees of possible and necessary optimality of a given schedule in one of the special cases of single-machine scheduling problems. Azizoglu et al. [4] studied the bi-criteria scheduling problem of minimizing the maximum earliness and the number of tardy jobs on a single machine. They assumed that idle time inserted is not allowed. First, they examined the problem of minimizing maximum earliness while keeping the number of tardy jobs to its minimum value. They also developed a general procedure to find an efficient schedule minimizing a composite function of the two criteria by evaluating only a small fraction of the efficient solutions. They adopted the general procedures for the bi-criteria problem of minimizing the maximum earliness and number of tardy jobs. Eren and Güner [8] considered a bi-criteria single-machine scheduling problem with sequence-dependent setup times. The objective function is to minimize the weighted sum of total completion time and total tardiness. An integer programming model was developed for the problem, which belongs to the NP-hard class. For solving problems containing a large number of jobs, a special heuristic is also used for large-sized problems. To improve the performance of the tabu search (TS) method, the result of the proposed heuristic algorithm was taken as an initial solution of the TS method. Tavakkoli-Moghaddam et al. [20] presented a fuzzy goal programming approach for solving a mixed-integer model of a single-machine scheduling problem minimizing the total weighted flow time and total weighted tardiness. Because of the conflict between these two objectives, they proposed a fuzzy goal programming approach to solve the extended mathematical model of a single-machine scheduling problem. This approach was constructed based on desirability of the decision maker (DM) and tolerances considered on goal values. Huo et al. [10] considered bi-criteria single-machine scheduling problems involving the maximum weighted tardiness and number of tardy jobs. They gave NP-hardness proofs for the scheduling problems when one of these two criteria is the primary criterion and the other one is the secondary criterion. They considered complexity relationships between the various problems and proposed polynomial algorithms for some special cases as well as fast heuristics for the general case. It is well known that the optimal solution of single-objective models can be quite different if the objective is different (e.g., for the simplest model of one machine without any additional constraint, the shortest processing time (SPT) rule is optimal to minimize View the MathML sourceF¯ (i.e., mean flow time) but the earliest due date (EDD) rule is optimal to minimize the maximal tardiness (Tmax)). In fact, each particular decision maker often wants to minimize the given criterion. For example, the commercial manager of a company is interested in satisfying customers and then minimizing tardiness. On the other hand, the production manager wishes to optimize the use of machines by minimizing the makespan or the work in process by minimizing the maximum flow time. In addition, each of these objectives is valid from a general point of view. Since these objectives are conflicting, a solution may perform well for one objective, but giving bad results for others. For this reason, scheduling problems often have a multi-objective nature [14]. Zimmermann [22] first extended his FLP approach to a conventional multi-objective linear programming (MOLP) problem. For each of the objective functions of this problem, it was assumed that the DM has a fuzzy goal such as ‘the objective functions should be essentially less than or equal to some value’. Then, the corresponding linear membership function is defined and the minimum operator proposed by Bellman and Zadeh [5] is applied in order to combine all objective functions. By introducing an auxiliary variable, this problem can be transformed into equivalent, conventional LP problem and can be easily solved by the simplex method. Subsequent work on fuzzy goal programming (FGP) is given in [9], [13], [15] and [16]. The aim of this paper is to develop a fuzzy multi-objective linear programming (FMOLP) model for solving the multi-objective single-machine scheduling problem in the fuzzy environment. First, a MOLP model of a multi-objective single-machine scheduling problem is constructed. The model attempts to minimize the makespan and total weighted tardiness. Furthermore, this model is converted into an FMOLP model by integrating fuzzy sets and objective programming approaches.
[/toggle]
[toggle title=”منبع”]
Journal : Applied Soft Computing, Volume 10, Issue 3, June 2010, Pages 919–925
Publisher : Science Direct (Elsevier)
[/toggle]
[aio_button align=”none” animation=”none” color=”red” size=”small” icon=”none” text=”انجام مقاله علمی پژوهشی و ISI در این زمینه” target=”_blank” relationship=”dofollow” url=”http://payannameha.ir/?p=796″]
[aio_button align=”none” animation=”none” color=”orange” size=”small” icon=”none” text=”دریافت سایر مقالات در این زمینه” target=”_blank” relationship=”dofollow” url=”http://payannameha.ir/?page_id=297″]
[aio_button align=”none” animation=”none” color=”blue” size=”small” icon=”none” text=”انجام پایان نامه در این حوزه” relationship=”dofollow” url=”http://payannameha.ir/?page_id=3206″]
[aio_button align=”none” animation=”none” color=”pink” size=”small” icon=”none” text=”انجام پروپوزال در این حوزه” target=”_blank” relationship=”dofollow” url=”http://payannameha.ir/?page_id=3206″]
فایل مقاله : 7 صفحه PDF
فایل ترجمه : 21 صفحه WORD
سال انتشار : 2010
جهت خرید فایل مقاله و ترجمه فارسی آن بر روی دکمه زیر کلیک نمایید: