MULTIPLE OBJECTIVE FUNCTION ON A SINGLE MACHINE SCHEDULING
DOI:
https://doi.org/10.31642/JoKMC/2018/010103Keywords:
Scheduling, single machine, simulated annealing, geneticAbstract
We consider a single machine scheduling problem to minimize a multiple objective function; sum
of earliness, tardiness and completion time. As this problem is complete NP-hard we propose a branch and
bound algorithm to obtain an optimal solution. The implementation of optimizing algorithms dose seen to be
promising but it need longer time. Thus we tackle the problem with local search methods: descent method,
simulated annealing and threshold acceptance. The performance of these heuristic methods is evaluated on a
large set of test problems, and the results are also compared with these obtained by genetic algorithm and
hybrid method which is combining the simulated annealing with the genetic algorithm. The best results are obtained with the hybrid method. We solved the problem optimality with up to 35 jobs and approximately with up to 150000 jobs.
Downloads
References
Abdul-Razaq, T. S. and Potts, C. N. “Dynamic Programming State-Space Relaxation for
single- Machine Scheduling”, J. Opt .Res. Vol.39. No. 2.141- 152 (1988).
Abdul-Razaq, T. S. and Mahmood, A. A. “Single Machine Earliness and Tardiness
Schedule with Set-up Time”. The first National Conference In Mathematical Science 25-
/Sep/2001. College of Science, Al-Mustansiriyah University Baghdad-Iraq 3/7
Abdul-Razaq, T. S. “Machine Scheduling Problem: A Branch and Bound Approach”, Ph.
D. Thesis Department of Mathematics university of keele, July, 1987.
Bean, J. C. “Genetic algorithms and Random Keys for Sequencing and Optimization”
ORSA Journal on Computing 6(2), (1994), 154-160.
Bryan, R. k. and Bahran Alidaee, “Single Machine Scheduling to Minimize Total
Weighted Late Work: a Comparison of Scheduling Rules and Search Algorithm”, Computers
and Industrial Engineering 43 (2002)509-528.
Celso M.Hino, Debora P. Ronconi and Andre B. mends, “ Minimizing Earliness and
Tardiness Penalties in a Single-Machine Problem with a Common Due Date” European
Journal of Operational Research 160 (2005) 190-201.
Celia A.Glass and Chris N .Potts, “A Comparison of local search methods for flow shop
scheduling”, Annals operations Research 63 (1996) 489-509.
Chichang Jou, “A genetic algorithm with sub-indexed partitioning genes and its
application to production scheduling of parallel machines”, Computers and Industrial
Engineering 48 (2005) 39-54.
George Li, “Theory and Methodology Single Machine Earliness and Tardiness
Scheduling”, European Journal of Operational Research, 1996.
Hall, N. G. , Kubink W. and S. P. Sethi, “Earliness-Tardiness Scheduling Problem. II:
Deviation of Completion Times about a Restrictive Common Due Date”, Operations
Research, 39(1991), 847-856.
Hoogeveen, J. A. and S. L. Van de Velde “Scheduling a Round a Small Common Due
Date” European Journal of Operational Research. 55(1991), 237-242.
Jan Bank and Frank werner, “Heuristic Algorithms for Unrelated parallel Machine
scheduling with a Common Due Date, Release Dates and Linear Earliness and Tardiness
Penalties”, OTTO-Van-Guericke-Universitat Magdeburg, Postfach 4120, 39016 Magdeburg
Germany(2000).
Kanet, J. J. “Minimizing the Average Deviation of jobs Completion Times about a
Common Due Date”, Naval Research Logistics Quarterly 28 (1981), 643-651.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Abdul Razaq T. S. . S, Al Saidy S. K. K, Al Zuwaini M. K
This work is licensed under a Creative Commons Attribution 4.0 International License.
which allows users to copy, create extracts, abstracts, and new works from the Article, alter and revise the Article, and make commercial use of the Article (including reuse and/or resale of the Article by commercial entities), provided the user gives appropriate credit (with a link to the formal publication through the relevant DOI), provides a link to the license, indicates if changes were made and the licensor is not represented as endorsing the use made of the work.
