کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
475410 699303 2016 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A beam search heuristic for scheduling a single machine with release dates and sequence dependent setup times to minimize the makespan
ترجمه فارسی عنوان
جستجوی پرتو اکتشافی برای برنامه ریزی یک دستگاه با تاریخ انتشار و زمان تنظیم وابسته به دنباله برای به حداقل رساندن ایجاد فاصله
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی


• A novel mixed integer linear program is proposed for the scheduling problem.
• Experiments showed that a commercial solver can only solve small instances.
• A beam search (BS) heuristic is proposed to solve larger instances.
• Experiments showed that the BS heuristic finds high quality solutions at low cost.

This paper considers the problem of scheduling a set of jobs subject to arbitrary release dates and sequence-dependent setup times on a single machine with the objective of minimizing the maximum completion of all the jobs, or makespan. This problem is often found in manufacturing processes such as painting and metalworking. A new mixed integer linear program (MILP) is firstly proposed. Because the problem is known to be NP-hard, a beam search heuristic is developed. Computational experiments are carried out using a well-known set of instances from the literature. Our results show that the proposed heuristic is effective in finding high quality solutions at low computational cost.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 73, September 2016, Pages 132–140
نویسندگان
, , ,