کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420641 683966 2008 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Batch processing with interval graph compatibilities between tasks
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Batch processing with interval graph compatibilities between tasks
چکیده انگلیسی

We analyze batch-scheduling problems that arise in connection with certain industrial applications. The models concern processing on a single max-batch machine with the additional feature that the tasks of the same batch have to be compatible. Compatibility is a symmetric binary relation—the compatible pairs are described with an undirected “compatibility graph”, which is often an interval graph according to some natural practical conditions that we present. We consider several models with varying batch capacities, processing times or compatibility graphs. We summarize known results, and present a min–max formula and polynomial time algorithms.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 5, 1 March 2008, Pages 556–568
نویسندگان
, , , ,