Branch and Bound Method to Solve The Sum of Two Objective Functions

Hussein Kamil Taher, Al- Zuwaini Mohammed Kadhim

Abstract


In this paper, the problem of sequencing a set of n jobs on single machine was considered to minimize multiple objectives function (MOF). The objective  is to find the optimal  solution (scheduling) for n independent jobs to minimize the objective function consists of a sum  of  weighted number  of  early  jobs  and  total  weighted of completion time. This problem is strongly NP-hard and to resolve it we derived two lower bounds (LB1, LB2) and heuristic method to get an upper bound which are used in root node of branch and bound tree. Some special cases  and dominance rule were proposed and proved. Results of extensive computational tests show that the proposed (BAB) algorithm effective in solving problems with up to (30)  jobs in time less than or equal to (30) minutes.


Keywords


Single machine, Scheduling, number of early jobs,completion time

Full Text:

PDF

References


A. Lann, and G. Mosheiov, “Single machine scheduling to minimize the number of early and tardy jobs.” Computers& Operations Research, vol. 8, pp. 769-781, 1996.

A. Lann, and G. Mosheiov, “A note on the maximum number of on-time jobs on parallel identical machines.” Computers & Operations Research, vol. 30, pp.1745-1749, 2003.

Huang RH and Yang CL (2007). "Single-machine scheduling to minimize the number of early jobs". Proceedings of the IEEE International Conference on Industrial Engineering and Engineering Management, 2–4 December, pp. 955, 957, doi: 10.1109/IEEM.2007.4419333.

Baruch Mor and GurMosheiov ''Minimizing the number of early jobs on a proportionate flowshop'' Journal of the Operational Research Society (2014), 1–4.

Smith, W.E., "Various optimizers for single stage production",Naval Research Logistics Quarterly 3/1, 59-66 (1956).

E. L. Lawler, Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Ann. Discrete. Math. 2, (1978) 75-90.

J. K. Lenstra and A. H. G. RinnooyKan, Complexity of scheduling under precedence constraints. Ops. Res,. 26 (1978) 22-35.

A. H. G. RinnooyKan; B. J. Lageweg and J. K. Lenstra, Minimizing total costs in one-machine scheduling, Oper, Res. 23 (1975) 908-927.

C. N. Potts, A Lagrangean based branch and bound algorithm for single machine sequencing with precedence constraints to minimize total weighted completion time, Management Science, Vol. 31, No. 10, October (1985) 1300-1311.

R. M. Karp, Reducibility among combinatorial problems. In complexity of computer computations, Miller, R. E. and Thatcher, J. W. Eds. Plenum Press, New York (1972) 95-103.

Araibi S.M., "Machine Scheduling Problem to Minimize Two and Three Objectives Function" M.Sc thesis, Dept. of mathematics, college of Education for Pure Sciences, Thi-Qar University (2012).

Husein, N.A.,'' Machine Scheduling Problem to Minimize Multiple Objective Function'', M.Sc thesis, Dept. of Mathematics College of Education (Ibn AL-Haitham), Baghdad University (2012).

Abdul-Razaq, T.S., Potts C.N. and Van Wassenhove, ''A survey of algorithms for the single machine total weighted tardiness scheduling problem'', Discrete App. Math. 26235-253(1990).


Refbacks

  • There are currently no refbacks.


Copyright (c) 2018 Journal of Progressive Research in Mathematics

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Copyright © 2016 Journal of Progressive Research in Mathematics. All rights reserved.

ISSN: 2395-0218.

For any help/support contact us at editorial@scitecresearch.com, jprmeditor@scitecresearch.com.