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

Hussein Kamil Taher; Al- Zuwaini Mohammed Kadhim

Hussein Kamil Taher Department of Mathematics, College of Computer Sciences and Mathematics Thi-Qar University, Thi-Qar, Iraq
Al- Zuwaini Mohammed Kadhim Department of Mathematics, College of Computer Sciences and Mathematics Thi-Qar University, Thi-Qar, Iraq

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

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.

Downloads

Download data is not yet available.

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).