سامانه اطلاعات پژوهشی

پژوهش های ریاضی، جلد ۱۱، شماره ۳، صفحات ۰-۰

عنوان فارسی

حل مسئلۀ کارگاه جریان جایگشتی به وسیله تنظیمات درایه‌های ستونی در ماتریس زمان‌های پردازش

چکیده فارسی مقاله

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

کار روی

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

چنان ساخته می‌شود که هر

نشان‌دهنده اندازه مناسب بودن جای سطر قدیم

ام در مکان جدید

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

کلیدواژه‌های فارسی مقاله

زمان‌بندی، کارگاه جریانی جایگشتی، روش‌های ابتکاری، دنباله اولیه، ماتریس زمان‌ها، حداکثر زمان در جریان، آلگوریتم NEH، مسائل محک تیلارد.

عنوان انگلیسی

Solving Permutation Flow shop Problem by the Regulations of Columnar Entries in the Processing Times Matrix

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

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

jobs to be processed on

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

is made such that every

determines the measure of the fitness for the location of the

th old row in the

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.

Introduction
In the permutation flow shop problem (PFSP),

jobs must be processed in a suitable order on

machines. The objective is to minimize the makespan (

), the time to complete all jobs. There exists an exact solution for

, but for

the problem is completely NP-hard [1]. Many authors proposed heuristic algorithms for solving PFSP. There are many assumptions such as infinite buffering space between jobs, the sameness of the processing orders of jobs on machines, jobs not passing each other at the processing etc. Matrix

is the matrix of the processing times of

jobs on

machines. The

is the processing time of the

th job on the

th machine.

Methods: Heuristic Algorithms
Among many proposed algorithms for solving PFSP, NEH, method is the most effective [2].

NEH Algorithm
The jobs are sorted according to their decreasing completion times. The order of the first two jobs is chosen after finding the best makespan from permutation of them. The third job is inserted before, between or after the fixed two jobs in the previous step. The best makespan shows the best ordering. The above processes are repeated for the fourh and the rest jobs.

RCE Algorithm
The regulations of the columnar entries (RCE) is an algorithm similar to the algorithms that are finding a suitable initial sequences of jobs. The desired order is obtained after regulating the columnar entries in the time matrix

. As the object is

, the permutation of rows and a new order in

must be determined. These rows will be ordered on the basis of RCE in such a form that:
1) entries on the main hypothetical diagonal are small.
2) entries that approach the border of

are greater.
3) the greatest entries on the border of

are placed on the secondary hypothetical diagonal. Then they will decrease by approaching the center of

.

The following figure is a plot for the mentioned design.

Figure 1. Plot for final design of A

The intersection of the

th column and the main hypothetical diagonal is called

. Matrix

is not the square, thus there is probably no entry in this intersection. We have

The entries of the

th column are sorted in ascending order. The new ordering of the rows i.e.

with the transformation

is obtained. If

, then the

th row of matrix

will be newly located in the

th position. We have

. If some of the entries equal each other, then we will choose one of the orders randomly.
Consider the transformation

with

for

and with

for

.
The last position for the

th row is denoted by

when

.
For every

in the matrix

, the entries are defined such that:
- for every

, the entry in the

th row and the

th column of

is equal to

,
- all other entries are zero.
Now

is a matrix in which every

denotes the fitness of the location of the

th old row in the new position

.
i) The greatest entry in

, named

, is selected, and for the

th row in

the location

will be specified.
ii) The

th row and the

th column in

are deleted. In the new matrix that obtained from

the same operations of step (i) are run.
iii) The previous steps are repeated and finally the desired initial good order of jobs is resulted.

Bellman, Esogbue and Nabeshima theorem [3] gives the makespan in which
1) the movement is just allowed in two directions right and down from

,
2) the sum of the entries that are passed by is found.

Numerical Results
The new heuristic algorithm was tested on benchmark problems from Taillard Page [4]. Relative percentage deviation (RPD) which refers to the difference between the heuristic and NEH solutions was calculated by:

Following table shows these percentages.

Table 1. Average percentage increase over the NEH solutions

J/M	20×5	20×10	20×20	50×5	50×10	50×20	100×5	100×10	100×20	200×10	200×20	500×20	Average
RCE	16	18	14	13	16	18	11	13	15	12	13	11	14

Conclusions
The new heuristic algorithm is found to generate better solutions than some of the proposed heuristics in the literature. Moreover, it can be as good as NEH on an average.

کلیدواژه‌های انگلیسی مقاله

Scheduling, Permutation flow shop, Heuristics, Initial sequences, Time matrix, Makespan, NEH, Taillard’s benchmark

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

شهریار فرهمند راد | Shahriar Farahmand Rad
Payame Noor University, Tehran
دانشگاه پیام نور، تهران

نشانی اینترنتی

http://mmr.khu.ac.ir/browse.php?a_code=A-10-480-2&slc_lang=fa&sid=1

فایل مقاله

فایلی برای مقاله ذخیره نشده است

کد مقاله (doi)

زبان مقاله منتشر شده

موضوعات مقاله منتشر شده

جریان شبکه- تحقیق عملکرد

نوع مقاله منتشر شده

علمی پژوهشی کاربردی

برگشت به: صفحه اول پایگاه | نسخه مرتبط | نشریه مرتبط | فهرست نشریات

ارسال پیام برخط

آمار پایگاه

اطلاعات تماس

توجه