Using Branch and Bound Method to Minimize Bi-Criteria

Mohammed Kadhom Alzwuiani, Asmaa Ali Zeyad

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.

Keywords


Late work; Tardy jobs; Scheduling.

Full Text:

PDF

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


Refbacks

  • There are currently no refbacks.


Copyright (c) 2016 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.