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.
Articles accepted for publication in Al-Mustansiriyah Journal of Science (MJS) are protected under the Creative Commons Attribution 4.0 International License (CC BY-NC). Authors of accepted articles are requested to sign a copyright release form prior to their article being published. All authors must agree to the submission, sign copyright release forms, and agree to be included in any correspondence between MJS and the authors before submitting a work to MJS. For personal or educational use, permission is given without charge to print or create digital copies of all or portions of a MJS article. However, copies must not be produced or distributed for monetary gain. It is necessary to respect the copyright of any parts of this work that are not owned by MJS.
How to Cite
