The Branch and Bound Method for Solving the One-Machine Scheduling Problem

N. I. Yusupova; O. N. Smetanina; A. A. Akhtariev

Computer Science and Information Technologies, Computer Science and Information Technologies 2006

N. I. Yusupova, O. N. Smetanina, A. A. Akhtariev

Last modified: 2020-12-26

Abstract

The one-machine problem of the schedule theory isNP-complete in the strong case. The algorithm ofbranch and bound type, which solve this problem,is introduced further.

Keywords

Bound Method; Solving the One-Machine Scheduling Problem; Branch Method

References

1. Adams J., Balas E., Zawack D. “The shiftingbottleneck procedure for job shop scheduling”Management Science, 1988; 34(3): 391-401.

2. Yussupova N.L, Schmeck H., Smetanina O.N.,Branke J., Akhtariev A.A. “Job Shop Scheduling withEvolutionary Algorithms Based on the ShiftingBottleneck Heuristic’. In: Proc. of the 6thInternational Workshop on Computer Science andInformation Technologies, (CSIT'2004), Vol. 1.Budapest, Hungary, 2004, pp. 202-207.

3. Carlier J. “The one-machine sequencing problem"‘opean Journal of Operational Research, 1982;11: 42-47.

4. Fischer H. and Thompson G.L. “ProbabilisticLeaming Combinations of Local Job SchedulingRules”. In; Muth JF, and Thompson G.L. (eds.)Industrial Scheduling. Prentice Hall, EnglewoodCliffs, New Jersey, USA, 1963, pp. 225-251

5. Nemeti L. “Das Reihenfolgeproblem in dieFertigungsprogrammierung und Linearplanung mit Logischen Bedingungen”, Mathematica (Cluj), 19646: pp. 474-479.

6. Fischer H., Lageweg B.J., Lenstra J.K. and RinnooyKan A.H.G. “Surrogate Duality Relaxation for Job Shop Scheduling”. Discrete Applied Mathematic,1983; 5: 65-75.

7. Balas E., “On the Facial Structure of Scheduling Polyhedra, Mathematical Programming Study, 1985;24:178-218.

8. Applegate D. and Cook W. “A Computional Study of the Job-Shop Scheduling Problem”. ORSA Journal onComputing, 1991; 3: 149-156,

9, Giffler B. and Thompson G.L. “Algorithms for Solving Production Scheduling Problems”. Operation Research, 1960; 8: 487-503

10.Carlier J. and Pinson E. “An algorithm for Solving the Job-Shop Problem”. Management Science, 1989;35: 164-176.

11.Haupt R. “A Survey of Priority Rule-Based Scheduling”. OR Spektrum, 11: 3-16.

12. Sevast’janov S.V. “On Some Geometric Methods in Scheduling Theory: a Survey”. Discrete Applied Mathematics, 1994; 55: 59-82.

13. Vaessens RJM. Aarts EH.L., Lenstra LK. “Jobshop scheduling by local search”. INFORMS: J.Comput, 1996; 8(3): 302-317.

Full Text: PDF