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

ابتکاری برای برنامه ریزی تولید کارگاهی برای به حداقل رساندن تاخیر وزن کل

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی تعداد کلمات
18901 2002 11 صفحه PDF سفارش دهید محاسبه نشده
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
A heuristic for job shop scheduling to minimize total weighted tardiness
منبع

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

Journal : Computers & Industrial Engineering, Volume 42, Issues 2–4, 11 April 2002, Pages 137–147

کلمات کلیدی
برنامه ریزی تولید کارگاهی - تاخیر وزن کل - الگوریتم اکتشافی
پیش نمایش مقاله
پیش نمایش مقاله ابتکاری برای برنامه ریزی تولید کارگاهی برای به حداقل رساندن تاخیر وزن کل

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

This paper considers the job shop scheduling problem to minimize the total weighted tardiness with job-specific due dates and delay penalties, and a heuristic algorithm based on the tree search procedure is developed for solving the problem. A certain job shop scheduling to minimize the maximum tardiness subject to fixed sub-schedules is solved at each node of the search tree, and the successor nodes are generated, where the sub-schedules of the operations are fixed. Thus, a schedule is obtained at each node, and the sub-optimum solution is determined among the obtained schedules. Computational results on some 10 jobs and 10 machines problems and 15 jobs and 15 machines problems show that the proposed algorithm can find the sub-optimum solutions with a little computation time.

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

We consider the minimum total weighted tardiness problem of job shop scheduling with job-specific due dates and delay penalties. A delay penalty is charged if a job is completed after its due date that has been promised to a customer. This penalty is assumed to be constant over time and includes cost of lost future sales or changed orders and rush shipping cost. The minimum total weighted tardiness problem in a job shop is NP hard in a strong sense, and some priority dispatching rules have been suggested. For example, Vepsalainen and Morton (1987) presented the apparent tardiness cost (ATC) rule. Anderson and Nyirenda (1990) showed two kinds of rules that combine two dispatching rules. On the other hand, Singer and Pinedo (1998) have presented a branch and bound algorithm. It is important to explore the ways of obtaining the optimum schedule. However, the enumerative methods are computation time intensive, and typically limited to cases with no more than 10 jobs and 10 machines. Pinedo and Singer (1999) have shown a heuristic, which is based on the shifting bottleneck procedure (SBP) proposed by Adams, Balas, and Zawack (1988). Their heuristic yielded the solutions that are close to optimum on some 10 jobs and 10 machines problems. However, the performance of their heuristic depends on the setting of the two control parameters. A heuristic algorithm based on the tree search procedure for solving the minimum total weighted tardiness problem is developed in this paper to obtain a sub-optimum solution with a little computation time without setting any control parameter. A certain job shop scheduling to minimize the maximum tardiness subject to fixed sub-schedules is solved at each node of the search tree in the proposed algorithm. The longest path for every tardy job at a searching node is found, and the sub-schedule of every operation on the longest path of a tardy job is fixed at each successor node. Some conditions to stop a node are also considered to improve the efficiency of searching. Thus, a schedule is obtained at each node, and the sub-optimum solution is determined among the obtained schedules.

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

This paper proposed a heuristic algorithm for solving the job shop scheduling to minimize the total weighted tardiness. The proposed algorithm is based on the tree search procedure, and does not require any parameter estimation for its implementation. Some computational results showed that the proposed algorithm can find a sub-optimum solution with a little computation time. Some works remain to be done to improve the method for solving the mini–max tardiness problem subject to fixed sub-schedules, and thus the better solution will be obtained with a less computational time.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.