Using Branch and Bound Method to Minimize Bi-Criteria

Mohammed Kadhom Alzwuiani; Asmaa Ali Zeyad

Mohammed Kadhom Alzwuiani Department of Mathematics, College of Computer Science and Mathematics, Thi-Qar University, Thi-Qar, Iraq
Asmaa Ali Zeyad Mathematic Dept, College of Education for Pure Science, Thi-Qar University, Thi-Qar, Iraq

Keywords: Late work, Tardy jobs, Scheduling.

Abstract

This paper presents a branch and bound algorithm for sequencing a set of n independent jobs on a single machine to minimize sum of total late work and the number of tardy jobs, the type of the problem is NP-hard.Lower bounds were proposed and heuristic method to get an upper bound. Some special cases were proved and some dominancerules were proposed and proved, the problem solved with up to 40 jobs.

Downloads

Download data is not yet available.

References

Potts C. N. and Van Wassenhove L. N.,(1991).Single Machine ToMinimize Total Late Work.Operations Research 40-3(1991)586-595.

Błażewicz, J. (1984). Scheduling preemptible tasks on parallel processors with information loss. Recherche Technique et. Science Informatiques , 3, 415–420.

Hariri, A. M. A., Potts, C. N., & Van Wassenhove, L. N. (1995). Single machine scheduling to minimize total weighted late work. ORSA Journal on Computing, 7, 232–242. doi:10.1287/ ijoc.7.2.232.

Kethley, R. B., &Alidaee, B. (2002). Single machine scheduling to minimize total weighted late work: A comparison of scheduling rules and search algorithms. Computers & Industrial Engineering, 43, 509–528. doi:10.1016/S0360-8352(02)00123-7

Błażewicz, J., Pesch, E., Sterna, M., & Werner, F. (2005a). The two-machine ﬂow-shop problem with weighted late work criterion and common due date. European Journal of Operational Research, 165, 408–415. doi:10.1016/j.ejor.2004.04.011

Błażewicz, J., Pesch, E., Sterna, M., & Werner, F. (2005b). A comparison of solution procedures for two-machine ﬂow shop scheduling with late work criterion. Computers & Industrial Engineering,49,611–624. doi:10.1016/j.cie.2005.09.001

Błażewicz, J., Pesch, E., Sterna, M., & Werner, F. (2007). A note on the two machine job shop with the weighted late work criterion. Journal of Scheduling, 10,87–95. doi:10.1007/s10951006-0005-5

Błażewicz, J., Pesch, E., Sterna, M., & Werner, F. (2008). Metaheuristic approaches for the two-machine ﬂow-shop problem with weighted late work criterion and common due dates. Computers & Operations Research, 35, 574–599. doi:10.1016/j.cor.2006.03.021

Lin, B. M. T., Lin, F. C., & Lee, R. C. T. (2006). Two-machine ﬂow-shop scheduling to minimize total late work. Engineering Optimization, 38, 501–509. doi:10.1080/03052150500420439

AL Zuwaini M.K,(2006). A comparative Study of Local Search Methods for Some Machine Scheduling Problems with the Usage of Hybridization As A Tool. Ph. D. thesis, University of Baghdad, College of Education (Ibn Al-Haitham), Dep. of Mathematics.

Al-Ayoubi M.G.(2012) A single machine scheduling problem to minimize the sum of total late work and total completion time. Mathematic Dept College of science Al- Mustansiriyah University.

Al_Nuaimi. A.A.(2014).Muiticriteria scheduling: Mathematical, Models, Exact and Approximation algorithms.M.Sc. thesis, Dept. of mathematics, college of science university of AL-Mustansiriya.

Moore, J.M., (1968). An n job one machine algorithm for minimizing the number of late jobs. Management Science 15, 102–109.

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

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

P. Baptiste.,(1999). An O(n4) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs Operations Research letters, 24:175-180, (1999).

Potts, C. N. and L. N. Van Wassenhove,(1992).Approximation Algorithms for Scheduling a Single Machine to Minimize Total Late Work, Operations Research Letters 11(1992)261-266

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