view in publisher's site

An approximation algorithm for proportionate scheduling in the two-stage hybrid flow shop

In the hybrid flow shop, jobs are subjected to process through stages in series as in the classical flow shop, while each stage contains one or more identical machines. This paper mainly studies the scheduling problem in the two-stage hybrid flow shop, namely the proportionate scheduling. In such problem, it is assumed that each job has the same processing time in different stages. The objective of minimizing the makespan is considered. If there are two machines in the first stage and m machines in the second, then an approximation algorithm with worst case ratio no more than 3/2 is provided. If each stage consists of only two machines, we show that the tight bound of our algorithm can be reduced to 4/3.

یک الگوریتم تقریبی برای زمان‌بندی متناسب در یک فروشگاه جریان هیبرید دو مرحله‌ای

در کارگاهی با جریان ترکیبی، مشاغل در حال پردازش از طریق مراحل در سری‌های زمانی در کارگاه کلاسیک جریان هستند، در حالی که هر مرحله دارای یک یا چند ماشین مشابه است. این مقاله عمدتا مساله برنامه‌ریزی را در یک فروشگاه جریان هیبرید دو مرحله‌ای، یعنی زمان‌بندی متناسب، مورد مطالعه قرار می‌دهد. در چنین مواردی فرض می‌شود که هر کار زمان پردازش مشابه در مراحل مختلف دارد. هدف به حداقل رساندن زمان در نظر گرفته شده‌است. اگر دو ماشین در مرحله اول و m در مرحله دوم وجود داشته باشد، آنگاه یک الگوریتم تقریبی با بدترین حالت در مقایسه با ۳ / ۲ ارایه می‌شود. اگر هر مرحله شامل دو ماشین باشد، نشان می‌دهیم که کران بالای الگوریتم ما را می توان به ۴ / ۳ کاهش داد.
ترجمه شده با

Download PDF سفارش ترجمه این مقاله این مقاله را خودتان با کمک ترجمه کنید
سفارش ترجمه مقاله و کتاب - شروع کنید

95/12/18 - با استفاده از افزونه دانلود فایرفاکس و کروم٬ چکیده مقالات به صورت خودکار تشخیص داده شده و دکمه دانلود فری‌پیپر در صفحه چکیده نمایش داده می شود.