TY - JOUR ID - TI - Branch and Bound Method to Solve Multiple Objective Function AU - Mohammad Kadhim Al-Zuwaini محمد كاظم الزويني AU - Najah Ali Husein نجاح علي حسين PY - 2012 VL - 3 IS - 3 SP - 212 EP - 229 JO - University of Thi-Qar Journal of Science مجلة علوم ذي قار SN - 19918690 27090256 AB - Abstract:This paper presents a branch and bound algorithm for sequencing a set of jobs on a single machinescheduling with the objective of minimizing total cost of flow time and maximum earliness, when the jobsmay have unequal ready time.For solving this problem we proposed two lower bounds (LB1, LB2) by decomposing the problem intotwo subproblems. The lower bounds of the problem is the sum of the lower bounds of two subproblems. Theproposed heuristic algorithm, which is used as an upper bound in the branch and bound (BAB) algorithm, iseffective in finding an optimal or near optimal schedule. Also, we prove some special cases of the problemwhich lead to optimal solution. We stated and proved three dominance rules. Results of extensivecomputational tests show the proposed (BAB) algorithm is effective in solving problems up to about (50) jobsat a time less than or equal to (30) minutes.

المستخلص:يقدم هذا البحث خوارزمية التفرع والتقيد لترتيب مجموعة من النتاجات على الماكنه الواحدة, الهدف تصغير الكلفة الكلية لزمن انسياببتجزئة ) LB1 ,LB النتاجات وكلفة أكبر تبكير عندما يكون للنتاجات أزمنة تحضير غير متساوية.لحل هذه المسألة تم اشتقاق قيدين أدنين ) 2المسألة الأصلية إلى مسألتين جزئيتين. القيدان الأدنيان للمسألة قيد البحث هما مجموع القيود الدنيا للمسألتين الجزئيتين. الخوارزمية التقريبيةالمقترحة والتي استخدمت في طريقة التفرع والتقيد كقيد أعلى كانت تعطي حالا امثلا أو قريبا من الحل الأمثل. كذلك برهنا بعض الحالاتالخاصة للمسأله والتي تقودنا إلى الحل الأمثل وتم برهان ثلاث قواعد هيمنة. تم تقييم كفاءة خوارزمية التفرع والتقيد المقترحة على مجموعةكبيرة من المسائل الأختباريه يبين بأنها فعالة في حل المسائل إلى ما يقارب من ) 05 ( نتاجاً وبزمن اقل أو يساوي ) 05 ( دقيقة. ER -