Exact Method with Dominance Rules for Solving Scheduling on a Single Machine Problem with Multiobjective Function
DOI:
https://doi.org/10.23851/mjs.v33i2.1091Keywords:
Multiobjective Problem (MOP), Branch and Bound (BAB) method. Upper Bound (UB), Lower bound (LB), Dominance Rules.Abstract
The present article proposes an exact algorithm for the single-machine scheduling problem to minimize the sum of total completion times, range of lateness and maximum tardiness on a single machine (1/ /(∑ C_(σ_j + R_L + T_max)), where machine idle time is prohibited. In this paper, one of the multiobjective function problem for single criteria on just one machine is being studied. To obtain the optimal solution for the suggested problem, we propose to use Branch and Bound method (BAB) depending upon some dominance rules. This exact method used new technique to obtain three upper bounds (UB) and single lower bound (LB). The proposed BAB method proved its sufficiency by the practical results for n ≤ 15 in a reasonable time. Lastly, we proved a theorem as special case for our problem.
Downloads
References
Hoogeveen H., "Multicriteria Scheduling, Department of Computer, Utrecht University, P.O. Box 80089, Utrecht 3508TB, (2005). Netherlands.
Poongothai V., Godhandaraman P.and Arockia Jenifer A.,"Single Machine Problem for Minimizing Total Tardiness of a Weighted Jobs in a Batch Delivery System, Stochastic Rework and Reprocessing Times. 020132(2019). AIP Conference Proceeding, 2112.
Faez H. Ali and Shrmeen B. Abdul-Kareem, "Scheduling a Single Machine to Minimize Max Tardiness,Max Late Work and Total Late Work",2017,Mathematics and Statistics Journal, 3(1): 1-17.
Abdul-Razaq, T. S., and Motair, H. M., "Solving Four Cost Multi-Objective Scheduling Problem Simultaneously", (2018), Journal of Kerbala University, Vol. 16(1), pp. 77-88.
Hanan Ali Chachan and Hussein Abdullah Jaafar, "Exact Solutions for Minimizing cost Function with Five Criteria and Release Dates on Single Machine". 2020, Ibn Al-Haitham Journal For Pure and Appl. Sci.33(3), pp.140-157. Doi: 10.30526/33.3.2479
D. A. Abbass, "Using Branch and Bound and Local Search Methods to solve Multi-Objective Machine Scheduling Problem". First International Conference of Computer and Applied Sciences (CAS), (2019), pp:63-66.
A. A. Jawad, F. H. Ali and W. S. Hasanain "Using Heuristic and Branch and Bound Methods to Solve a Multi-Criteria Machine Scheduling Problem", Iraqi Journal of Science, 2020, Vol. 61, No. 8, pp: 2055-2069,
Smith W. E.,"Various optimizers for single- stage production", Navel Research Logistics Quarterly, 1956, 3, 59-66.
Hoogeveen, H., "Invited Review Multicriteria Scheduling", European Journal of Operation Research, , 2005, 167:592-623.
Hoogeveen J.A., "Minimizing maximum earliness and maximum lateness on a single machine", In Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference (pp. 283-295).
F. Ali and T. Abdul-Razaq, "Combinatorial Optimization Problems: Modeling and Solvingˮ, Lap Lambert Academic Publishing, 2016, ISBN-13: 978-3-659-93685-2.
Hafed M. "Solving Single and Flow Shop Scheduling Multicriteria Problems Using Branch and Bound and Local Search Algorithms", PhD Thesis Dept. of Mathematics, College of Science, Mustansiriyah University, (2018).
Faez H. Ali and Manal G. Ahmed, "Optimal and Near Optimal Solutions for Multi Objective Function on a Single Machine" International Conference on computer Science and Software Engineering (CSASE), IEEE, Duhok Iraq, 2020, pp. 152-156.
Faez H. Ali and Manal G. Ahmed, "Local Search Methods for Solving Total Completion Times, Range of Lateness and Maximum Tardiness Problem",6th international engineering conference", Sustainable Technology and Development", (IEC-2020), IEEE, Erbil Iraq, 2020, pp. 103-108.
Downloads
Key Dates
Published
Issue
Section
License
Copyright (c) 2022 Al-Mustansiriyah Journal of Science
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
(Starting May 5, 2024) Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution (CC-BY) 4.0 License that allows others to share the work with an acknowledgement of the work’s authorship and initial publication in this journal.
How to Cite
