دانلود مقاله ISI انگلیسی شماره 20079
ترجمه فارسی عنوان مقاله

برنامه ریزی شغلی با معیارهای دوگانه و تنظیم وابسته به توالی:برنامه ریزی ریاضی در مقابل برنامه ریزی ژنتیک

عنوان انگلیسی
Job scheduling with dual criteria and sequence-dependent setups: mathematical versus genetic programming
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی
20079 2004 9 صفحه PDF
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Omega, Volume 32, Issue 2, April 2004, Pages 145–153

ترجمه کلمات کلیدی
0 - 1 برنامه ریزی معیارهای دوگانه - زمان نصب وابسته به توالی - برنامه ریزی ریاضی 0 - 1 - الگوریتم ژنتیک -
کلمات کلیدی انگلیسی
Dual criteria scheduling,Sequence dependent setup times,0-1 mathematical programming,Genetic algorithm,
پیش نمایش مقاله
پیش نمایش مقاله  برنامه ریزی شغلی با معیارهای دوگانه و تنظیم وابسته به توالی:برنامه ریزی ریاضی در مقابل برنامه ریزی ژنتیک

چکیده انگلیسی

Flexibility, speed, and efficiency are major challenges for operations managers in today's knowledge-intensive organizations. Such requirements are converted into three production scheduling criteria: (a) minimize the impact of setup times in flexible production lines when moving from one product to another, (b) minimize number of tardy jobs, and (c) minimize overall production time, or makespan, for a given set of products or services. There is a wide range of solution methodologies for such NP-hard scheduling problems. While mathematical programming models provide optimal solutions, they become too complex to model for large scheduling problems. Simultaneously, heuristic approaches are simpler and very often independent of the problem size, but provide “good” rather than optimal solutions. This paper proposes and compares two alternative solutions: 0-1 mixed integer linear programming and genetic programming. It also provides guidelines that can be used by practitioners in the process of selecting the appropriate scheduling methodology.

مقدمه انگلیسی

Improving scheduling systems for greater customer satisfaction and operations efficiency requires an optimization criterion that incorporates both meeting due times and minimizing the makespan. Simultaneously, the sequence-dependent setup time environment with dual criteria is a very common scheduling problem in both manufacturing and service organizations [1]. This paper deals with a single-server-scheduling problem with dual criteria: minimizing the number of tardy jobs and makespan, while considering the impact of setup times between jobs. Following the three-field notation provided by Pinedo [2], such a problem is denoted as View the MathML source. This dual criteria problem is an NP-hard problem since its simpler case of the single criterion problem, 1|sjk|Cmax is an NP-hard problem [2]. Consequently, this scheduling situation provides an appropriate case study for the comparison of mathematical programming and heuristic programming, two viable alternative solution methodologies. In general, mathematical programming models ensure the best possible solution for a given scheduling problem. However, due to the complex nature of the problem, such models can not always be implemented to solve large-scale scheduling problems. On the other hand, heuristic approaches can be used to address combinatorial complexity of NP-hard scheduling problems. The purpose of this paper is to (1) propose two alternative solution methodologies for View the MathML source scheduling problem and (2) compare these two distinct approaches in terms of the appropriateness of each approach under different conditions. The paper is structured as follows: First, a brief literature review of solution methodologies for bi-criteria, sequence-dependent setup times scheduling is provided. Then, a 0-1 mixed integer programming model is formulated to solve such a scheduling problem. In Section 4, a genetic algorithm (GA) is proposed to solve the same scheduling problem. In Section 5, we compare two methods and provide guidelines that can be used by practitioners in the process of solving dual criteria scheduling problems with sequence dependent setup times.

نتیجه گیری انگلیسی

This paper provides two alternative solution methodologies for an NP hard scheduling problem: single machine, sequence dependent-setup time, and dual criteria. The two alternative methodologies are a 0-1 mixed integer-programming and a genetic search algorithm. Due to increasing computer presence and its processing power in today's workplace, operation schedulers’ concern is not the time that a computer takes to generate a solution. Instead, more practical goals would be to improve user interface and to achieve the best possible solution. Table 4 provides some practical recommendations that can be used to select one of the above two solution methods. For the View the MathML source scheduling problem, our findings suggest that when the major concern of the operations scheduler is the quality of the output, and when the number of jobs to be sequenced is relatively small, then mathematical programming is an appropriate methodology. While mathematical programming generally ensures an optimal solution, genetic algorithms do not always guarantee an optimal solution. If the number of jobs to be sequenced is relatively large or when achieving a “good” solution is acceptable, then genetic algorithms (GAs) can be used. The number of jobs that need to be sequenced does not affect the GA performance. In contrast, mathematical programming model becomes very complex and even unmanageable when the number of jobs is more than ten. In addition, our analysis shows that the proposed GA performs better when the ratio between sequence-dependent setup times and processing times for each job is relatively large.