کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
479629 1446008 2015 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A single machine scheduling problem with two-dimensional vector packing constraints
ترجمه فارسی عنوان
یک ماشین زمانبندی یک ماشین با محدودیت بسته بندی بردار دو بعدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی


• A single machine scheduling problem with two-dimensional vector packing constraints is considered.
• A recovering beam search approach and a matheuristic procedure are proposed.
• The combination of the two approaches reaches the best results.
• Seven new bounds were obtained on the original 2-constraint vector packing instances.

We consider a scheduling problem where jobs consume a perishable resource stored in vials. It leads to a new scheduling problem, with two-dimensional jobs, one dimension for the duration and one dimension for the consumption. Jobs have to be finished before a given due date, and the objective is to schedule the jobs on a single machine so that the maximum lateness does not exceed a given threshold and the number of vials required for processing all the jobs is minimized. We propose a two-step approach embedding a Recovering Beam Search algorithm to get a good-quality initial solution reachable in short time and a more time consuming matheuristic algorithm. Computational experiments are performed on the benchmark instances available for the two-dimensional vector packing problem integrated with additional due dates to take into account the maximum lateness constraints. The computational results show very good performances of the proposed approach that remains effective also on the original two-dimensional vector packing instances without due dates where 7 new bounds are obtained.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 243, Issue 1, 16 May 2015, Pages 75–81
نویسندگان
, , ,