A branch and bound algorithm for jobshop scheduling أسلوب فرع وحد لمشكلة تنظيم الأعمال في ورشة تعاقدية

Abstract

المشكلة محل البحث عبارة عن تنظيم الأعمال في ورشة عمل تعاقدية، حيث يتوافر عدد n من الأعمال المطلوب إنجازها على M آلة كل عمل من الأعمال، ولمدة زمنية محددة على كل آلة منها، ليتم إنجازه عليها اقترحنا أسلوب فرع وحد لحل هذه المشكلة الحد الأدنى المستخدم تم الحصول عليه بحل مشكلة تنظيم على آلة واحدة في حين يعتمد أسلوب التفريع المتبع على اختيار مجموعة من العمليات (كل عملية تمثل إنجاز عمل على آلة معينة) التي تتطلب نفس الآلة لإنجازها كل عقدة في شجرة التفريع مثل احتمال إنجاز أحد العمليات في هذه المجموعة قبل بقية العمليات في نفس المجموعة قمنا كذلك بكتابة برنامج كمبيوتر بلغة فورتران لاختبار فعالية أسلوب الفرع والحد المقترح على مشاكل اختبار مختلفة

The problem of scheduling jobs in a general jobshop to minimize the maximum completion time is considered A branch and bound algorithm is proposed The lower bound is obtained from the preemptive schedules which form solutions of single machine subproblems In the branching rule a set of operations which each require the same machine is selected and branches of the search tree corresponding to the possibilities that an operation of this set is sequenced before (or after) the optohretersd Computational experience with a variety of test problems is reported