An unrelated-parallel-machine scheduling model with job rejection option was studied. In this model, all jobs are available at time zero but some machines are not available at time zero. Each job is either accepted and processed once without interruption, or is rejected at a penalty cost. To minimize the makespan of all accepted jobs plus the total cost of rejecting and processing jobs, we provide a heuristic with worst-case ratio bound of 2

چکیده

در این مقاله، یک مدل زمان‌بندی ماشین‌آلات موازی و غیر مرتبط که از قابلیت ردِ کار برخودار می ­باشند، مورد مطالعه قرار گرفته است. در این مدل، همه‌ی کارها در زمان صفر موجود و آماده می‌باشند ولی بعضی از ماشین‌آلات در زمان صفر حاضر و آماده‌ی سرویس‌ دهی نیستند. هر کار، یا به صورت یک‌باره و بدون وقفه مورد پذیرش و پردازش قرار گرفته و یا با متحمل شدن هزینه‌ی جریمه، رد می‌شود. به منظور به حداقل رساندن زمان تکمیل کل کارهای پذیرفته شده و همچنین به حداقل رساندن هزینه‌ی کل رد و پردازش کارها، یک راهکار هیروستیکی ( ابتکاری) را که نسبت کارائی آن در بدترین حالت برابر با 2 می ­باشد ارائه داده ایم.

1-مقدمه

امروزه مسائل مربوط به زمان‌بندی در سطح گسترده‌ای و آنهم با توجه به این فرضیه که همه‌ی کارها را باید پردازش کرد، مورد مطالعه قرار گرفته است. اگر چه در واقعیت، تولیدکنندگان غالباً اقدام به رد بعضی از کارها و پردازش کارهای باقیمانده نموده تا درآمد کل خود را به حداکثر سطح ممکن برسانند [12]. از این رو در طی دو دهه‌ی اخیر، مسئله‌ی زمان‌بندی ماشین‌آلات با قابلیت رد کار (MSR) مورد توجه گسترده‌ی محققین و همچنین مدیران عملیاتی قرار گرفته است...