Solving Multi-Objectives Function with Release Dates Problem using Branch and Bound Methods
DOI:
https://doi.org/10.29304/jqcm.2022.14.2.948Keywords:
Multi-Objective Problem (MOP), Branch and Bound (BAB) method, unequal release times, Gray Wolfe algorithm.Abstract
This research study focuses on solving a multi-objective job scheduling problem on a single machine. This problem involves the summation of four objective functions namely the total flow time ( ), tardiness ( ), earliness ( ), and late work ( ) of each of the n jobs with unequal release dates . This is formulated as .
We present some special cases that yield optimal solutions. also, we propose a branch and bound algorithm in order to find the exact (optimal) solution for it, by derive and use a good lower, and using some heuristics methods to find the upper bound of seven including Gray Wolfe algorithm (GW), and Bat algorithm (BAT), this algorithm was given to find the optimal solution for problems of size up to 17 functions.
Downloads
Download data is not yet available.
References
1- Ali, Simin Poursheikh, and Mehdi Bijari (2012). Minimizing maximum earliness and tardiness on a single machine using a novel heuristic approach. Proceedings of the 2012 International Conference on Industrial Engineering and Operations Management 2012.
2- Blazewicz, J., Ecker, K.H., Pesch, E., Schmidt, G. and Weglarz, J. 2007. Handbook on Scheduling: From Theory to Applications. Springer. Berlin. Heidelberg. New York.
3- Chen, Wei-Yang, and Gwo-Ji Sheen (2007). Single-machine scheduling with multiple performance measures: minimizing job-dependent earliness and tardiness subject to the number of tardy jobs. International Journal of Production Economics. Vol. 109. No. 1-2, p.p. 214-229.
4- Driss Belbachir, Fatima Boumediene, Ahmed Hassam, Latéfa Ghomri, “Adaptation and parameters studies of CS algorithm for flow shop scheduling problem”, international Journal of Electrical and Computer Engineering (IJECE) ,Vol. 11, No. 3, June 2021, pp. 2266~2274.
5- Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. In Annals of discrete mathematics, Vol. 5.Elsevier, p.p. 287-326.
6- Johnson, S.M. 1954. Optimal two and three stage production schedules with set-up times included. Naval Res. Logist Quart. 1: 61-68.
7- Lawler E.L. 1973. Optimal sequencing of a single machine subject to precedence constraints. Management Science 19: 544-546.
8- Smith W.E. 1956 Various Optimizers for single-stage production. Naval. Res. Logist Quart. 3: 59- 66.
9- T’kindt, V. and Billaut, J. 2002. Multi-criteria Scheduling: Theory, Models and Algorithms. Second edition. Springer Berlin Heidelberg New York.
2- Blazewicz, J., Ecker, K.H., Pesch, E., Schmidt, G. and Weglarz, J. 2007. Handbook on Scheduling: From Theory to Applications. Springer. Berlin. Heidelberg. New York.
3- Chen, Wei-Yang, and Gwo-Ji Sheen (2007). Single-machine scheduling with multiple performance measures: minimizing job-dependent earliness and tardiness subject to the number of tardy jobs. International Journal of Production Economics. Vol. 109. No. 1-2, p.p. 214-229.
4- Driss Belbachir, Fatima Boumediene, Ahmed Hassam, Latéfa Ghomri, “Adaptation and parameters studies of CS algorithm for flow shop scheduling problem”, international Journal of Electrical and Computer Engineering (IJECE) ,Vol. 11, No. 3, June 2021, pp. 2266~2274.
5- Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. In Annals of discrete mathematics, Vol. 5.Elsevier, p.p. 287-326.
6- Johnson, S.M. 1954. Optimal two and three stage production schedules with set-up times included. Naval Res. Logist Quart. 1: 61-68.
7- Lawler E.L. 1973. Optimal sequencing of a single machine subject to precedence constraints. Management Science 19: 544-546.
8- Smith W.E. 1956 Various Optimizers for single-stage production. Naval. Res. Logist Quart. 3: 59- 66.
9- T’kindt, V. and Billaut, J. 2002. Multi-criteria Scheduling: Theory, Models and Algorithms. Second edition. Springer Berlin Heidelberg New York.
Downloads
Published
2022-06-14
How to Cite
daowd, O. osama, chachan, H. A., & Daway, H. G. (2022). Solving Multi-Objectives Function with Release Dates Problem using Branch and Bound Methods. Journal of Al-Qadisiyah for Computer Science and Mathematics, 14(2), Math Page 26–46. https://doi.org/10.29304/jqcm.2022.14.2.948
Issue
Section
Math Articles
