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

کلیدواژه: زمان بندی تولید، انتقال، برنامه نویسی دینامیک، طرح تخمینی زمان چندجمله ای کامل

1- مقدمه

هماهنگی مربوط به زمان بندی تولیدات و انتقال اخیرا توجه زیادی را از نقطه نظر منطق و تحقیقات مدیریتی صنعتی به سمت خود جلب کرده است.فعالیت های نیمه تمام از یک منطقه به سمت تاسیسات صنعتی برای پردازش بیشتر توسط انتقال دهنده ها در بسیاری از بخش های صنعتی انتقال یافته است. انگیزه دیگری نیز در بسیاری از صنایع ایجاد شده است که هماهنگی بین تولید و انتقال برای ذخیره انرژی و کاهش مصرف سوخت کمک کننده می باشد. این مورد در صنعت فلزات و آهن حقیقی می باشد. در فرایند تولید شمش، این فلز توسط بعضی از دستگاه ها به کوره های عمیق انتقال داده می شود.