Algorithms for scheduling a single machine to minimize total completion time and total tardiness
Other Title(s)
خوارزميات تقليل وقت الإتمام الكلي و التأخير الكلي لجدولة ماكنة واحدة
Joint Authors
Abd al-Razzaq, Tariq Salih
Ali, Faiz Hasan
Source
Issue
Vol. 34, Issue 2A (31 Dec. 2016), pp.113-132, 20 p.
Publisher
University of Basrah College of Science
Publication Date
2016-12-31
Country of Publication
Iraq
No. of Pages
20
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Abd al-Razzaq, Tariq Salih& Ali, Faiz Hasan. 2016. Algorithms for scheduling a single machine to minimize total completion time and total tardiness. Basrah Journal of Science،Vol. 34, no. 2A, pp.113-132.
https://search.emarefa.net/detail/BIM-771592
Modern Language Association (MLA)
Abd al-Razzaq, Tariq Salih& Ali, Faiz Hasan. Algorithms for scheduling a single machine to minimize total completion time and total tardiness. Basrah Journal of Science Vol. 34, no. 2A (2016), pp.113-132.
https://search.emarefa.net/detail/BIM-771592
American Medical Association (AMA)
Abd al-Razzaq, Tariq Salih& Ali, Faiz Hasan. Algorithms for scheduling a single machine to minimize total completion time and total tardiness. Basrah Journal of Science. 2016. Vol. 34, no. 2A, pp.113-132.
https://search.emarefa.net/detail/BIM-771592
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references : p. 130-132
Record ID
BIM-771592