This paper present algorithm for solving a single machine scheduling problem to minimize the sum of total completion times, total tardiness, maximum tardiness, and maximum earliness. The single machine total tardiness problem is already NP-hard, so they consider problem is strongly NP-hard, and several algorithms are used to solve it. Branch and bound algorithm with dominance rule and local search algorithms are proposed for the problem. For the Branch and bound algorithm results- show that using dominance rule improve the performance of the algorithm in both computation times and optimal values, but it needs longer times. Thus we tackle the problem of large sizes with local search algorithms descent method, simulated annealing and tabu search. The performance of these algorithms is evaluated on a large set of test problems and the results are compared. The computational results show that simulated annealing algorithm and Tabu search algorithm are better than descent method with preference to simulated annealing algorithm, and show that the three algorithms find optimal or near optimal solutions in reasonable times.

Multicriteria Scheduling --- Branch and bound --- Dominance rule --- Local search algorithms.

This paper considers a branch and bound (BAB) algorithm for simultaneous multicriteria problem of minimizing the sum of the three criteria of total completion time, maximum tardiness and maximum late work within the single machine context.Late work is the amount of work executed after a given due date. Heuristic method was used to find an upper bound. This BAB proposes a lower bound based on the decomposition property of the multicriteria problem. Based on results of computational experiments, conclusions are presented on the efficiency of the BAB algorithm.

إن هذا البحث يقدم خوارزمية التفرع والتقيد ((Branch and bound(BAB) لمسألة متعددة المقاييس تحدث في وقت واحد لتقليل المجموع للمقاييس الثلاثة لوقت الإتمام الكلي (ΣCj) ، أعظم تأخير لا سالب (Tmax) وأعظم تأخير لوحدات عمل متأخر(Vmax) على ماكنة واحدة. العمل المتأخر هو مقدار العمل الذي يُنفذ بعد وقت مثالي معطى. استُخدمت طريقة تقريبية لإيجاد القيد الأعلى (Upper bound). في خوارزمية التفرع والتقيد يتم إيجاد قيد أدنى (Lower bound) يعتمد على تجزئة المسألة متعددة المقاييس. بالاعتماد على نتائج التجارب الحسابية قُدمت استنتاجات حول كفاءة خوارزمية التفرع والتقيد(BAB).

Multicriteria scheduling --- late work criterion --- branch and bound algorithm --- single machine --- جدولة متعددة المقاييس، مقياس عمل متأخر، خوارزمية التفرع والتقيد، ماكنة واحدة