ارايه حدود پايين جديد روي مقدار بهينه زمان انجام كل كارها در يك سيستم تك ماشينه‌ي پردازش‌گر انباشته

New Lower Bounds for the Optimal Makespan on a Single Batch Processing Machine

در اين مقاله زمان‌بندي يك ماشين پردازش‌گر انباشته با هدف حداقل‌سازي زمان انجام كل كارها (Cmax) بررسي شده است. منظور از يك ماشين پردازشگر انباشته، ماشيني است كه قابليت انجام عمليات هم‌زمان روي گروهي از كارها را در قالب يك دسته يا انباشته دارد. البته با اعمال اين محدوديت كه مجموع اندازه كارهايي كه در يك انباشته با‌‌هم مي‌آيند از ظرفيت ماشين (B) بيشتر نباشد. براي هر يك از كارها دو عامل اندازه و زمان پردازش مفروض است. زمان انجام عمليات ماشين بر روي يك انباشته برابر با زمان عمليات مورد نياز كاري است كه در ميان كارهاي متعلق به آن انباشته بزرگ‌ترين زمان پردازش را دارد. براي اين مساله، دو روش جديد توليد حد پايين روي مقدار بهينه تابع هدف با نام‌هاي LB2 و LB3 ارايه شده و ثابت مي‌شود كه نسبت به تنها حد پايين موجود در ادبيات موضوع مساله (LB1) عملكرد بهتري دارند. هم‌چنين ثابت مي‌شود كه عملكرد LB3 حداقل به خوبي عملكرد LB2 است.

This paper considers minimizing makespan (Cmax) on a single batch-processing machine. A batch-processing machine can process a group of jobs simultaneously, as long as the total size of jobs in the batch does not exceed the machine capacity (B). For each job, we assume a specific job size and job processing time. The processing time of a batch is just the longest processing time of all jobs in the batch. We introduce two new procedures for obtaining lower bounds of the optimal makespan, entitled LB2 and LB3, respectively. We prove that both of the new bounds are tighter than the only existing bound called LB1. We also prove that LB3 is at least as tight as LB2.