کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
7540685 1489042 2018 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Parallel dedicated machine scheduling with conflict graphs
ترجمه فارسی عنوان
برنامه ریزی موازی اختصاصی با نمودارهای درگیری
موضوعات مرتبط
مهندسی و علوم پایه سایر رشته های مهندسی مهندسی صنعتی و تولید
چکیده انگلیسی
This paper investigates a variant of parallel-machine scheduling problems with conflict constraints. A set of identical parallel machines is available for processing a set of jobs subject to conflict constraints, which specify pairs of jobs that are mutually disjoint due to resource availability. Jobs conflicting to each other cannot be processed simultaneously. The scheduling problem is to construct a feasible schedule that optimizes the considered managerial performance measures. This paper discusses the specific two-machine setting where each machine has a designated set of jobs to process. We give NP-hardness proofs for the case with the presence of a fixed processing sequence on one of the machines. Polynomial-time dynamic programming algorithms are proposed to produce optimal schedules for the case where the processing sequences on both machines are known and fixed a priori.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Industrial Engineering - Volume 124, October 2018, Pages 316-321
نویسندگان
, ,