دانشگاه صنعتی امیرکبیر نشریه مهندسی مکانیک امیرکبیر 2008-6032 43 2 2012 02 20 New Lower Bounds for the Optimal Makespan on a Single Batch Processing Machine ارائه حدود پایین جدید روی مقدار بهینه زمان انجام کل کارها در یک سیستم تک ماشینه‌ی پردازش‌گر انباشته 75 84 72 10.22060/mej.2012.72 FA علی حسین زاده کاشان دکتری صنایع؛ دانشگاه صنعتی امیرکبیر بهروز کریمی نویسنده مسئول و دانشیار دانشکده صنایع؛ دانشگاه صنعتی امیرکبیر Journal Article 2014 03 15 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. در این مقاله زمان‌بندی یک ماشین پردازش‌گر انباشته با هدف حداقل‌سازی زمان انجام کل کارها (Cmax) بررسی شده است. منظور از یک ماشین پردازشگر انباشته، ماشینی است که قابلیت انجام عملیات هم‌زمان روی گروهی از کارها را در قالب یک دسته یا انباشته دارد. البته با اعمال این محدودیت که مجموع اندازه کارهایی که در یک انباشته با‌‌هم می‌آیند از ظرفیت ماشین (B)بیشتر نباشد. برای هر یک از کارها دو عامل اندازه و زمان پردازش مفروض است. زمان انجام عملیات ماشین بر روی یک انباشته برابر با زمان عملیات مورد نیاز کاری است که در میان کارهای متعلق به آن انباشته بزرگ‌ترین زمان پردازش را دارد. برای این مساله، دو روش جدید تولید حد پایین روی مقدار بهینه تابع هدف با نام‌های LB2 و LB3 ارائه شده و ثابت می‌شود که نسبت به تنها حد پایین موجود در ادبیات موضوع مساله (LB1) عملکرد بهتری دارند. هم‌چنین ثابت می‌شود که عملکرد LB3 حداقل به خوبی عملکرد LB2 است.

https://mej.aut.ac.ir/article_72_32bb90e8976aab5298d5da10fe66f21d.pdf