Exact Method with Dominance Rules for Solving Scheduling on a Single Machine Problem with Multiobjective Function
Keywords:Multiobjective Problem (MOP), Branch and Bound (BAB) method. Upper Bound (UB), Lower bound (LB), Dominance Rules.
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.
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.
How to Cite
Copyright (c) 2022 Al-Mustansiriyah Journal of Science
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
The journal has no restrictions for the author to hold the copyrights of his articles. The journal does not allow authors to republish the same article in other journals or conferences that is published in one of its volumes.