TY - JOUR ID - TI - Algorithms for Scheduling a Single Machine to Minimize Total Completion Time and Total Tardiness خوارزميات تقليل وقت الاتمام الكلي والتأخير الكلي لجدولة ماكنة واحدة AU - Tariq S. Abdul-Razaq and Faez H. Ali د.طارق صالح عبد الرزاق وفائز حسن علي PY - 2016 VL - 34 IS - 2 A SP - 113 EP - 132 JO - Basrah Journal of Science (Bas J Sci) مجلة البصرة للعلوم SN - 26648288 26648296 AB - In this paper we look at the problem where we have to schedule n jobs with processing times and due dates on a single machine. The objective is to find a schedule that minimize a function of the sum of completion time and sum of tardiness (i,e to minimize the multiple objective functions (Ci,Ti)). We propose two methods for solving this simultaneous minimization problem to find the set of all efficient solutions, (Pareto optimal solutions). This set of all efficient solutions is not easy to find, therefore, it could be preferable to have an approximation to that set in a reasonable amount of time. Therefore branch and bound (BAB) and local search methods are used.The Particle Swarm Optimization (PSO) method is applied as new local search method on a set of randomly generated problems to solve machine scheduling problem with multiple objective functions. Comparison studies are made between Branch and Bound Methods (BAB), PSO and Genetic Algorithm (GA) to show which one is the better method in applications. In addition, tuning the parameters of every method has been suggested in order to improve the application of every method. A new style of development steps has been proposed to achieve good convergence in application. Since our problem is NP-hard, we propose new heuristic method like PSO and GA to find approximation solutions especially when the number of jobs exceeds the ability of some exact methods like complete enumeration and BAB in solving such problems. Lastly, the proposed methods results are compared for this multi-objective scheduling problem. Computational experience is found that these local search algorithms solve problem to '2000 'jobs with reasonable time.

في هذا البحث سيتم مناقشة مسالة جدولة n من الاعمال لها اوقات تنفيذ والوقت المثالي لانجاز النتاج لماكنة واحدة. الهدف هو ايجاد جدولة تقلل قيمة دالة مجموع وقت الاتمام ومجموع وقت التأخير (لتقليل دالة متعددة الاهداف (Ci,Ti)). في هذا البحث نقترح طريقتين لحل مسالة التقليل ألآني لايجاد مجموعة كل الحلول الكفوءة (حلول باريتو المثالية). ان ايجاد مجموعة الحلول الكفوءة ليس بالامر الهين، لذلك، من الافضل ايجاد قيم تقريبية لمجموعة الحلول وفي اوقات معقولة. لذلك تم استخدام طريقة التقيد والتفرع (BAB) وطرق البحث المحلية.تم تطبيق طريقة امثلية السرب الجزيئي (PSO)، طريقة بحث محلية جديدة، على مسائل مولدة عشوائياً لحل مسائل مكائن الجدولة متعددة الاهداف. ولان مسألتنا هي من المسائل المعقدة، فاننا نقترح استخدام طرق تقريبية جديدة مثل (PSO) و(GA) لايجاد حلول تقريبية خصوصا عندما يتجاوز عدد الاعمال امكانية بعض الطرق الحل التام مثل حل التام مثل طريقة العد التام وطريقة (BAB). تم اجراء دراسة مقارنة بين طريقة التقيد والتفرع وطريقة امثلية السرب الجزيئي والخوارزمية الجينية لبيان اي منها الافضل عند التطبيق. ER -