Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the makespan. (English) Zbl 0953.90029

Summary: This paper deals with the problem of assigning a set of \(n\) jobs, with release dates and tails, to either one of two unrelated parallel machines and scheduling each machine so that the makespan is minimized. This problem will be denoted by \(R2|r_i,q_i|C_{\max}\). The model generalizes the problem on one machine \(1|r_i,q_i|C_{\max}\), for which a very efficient algorithm exists. In this paper we describe a branch and bound procedure for solving the two machine problem which is partly based on Carlier’s algorithm for the \(1|r_i,q_i|C_{\max}\). An \(O(n\log n)\) heuristic procedure for generating feasible solutions is given. Computational results are reported.


90B35 Deterministic scheduling theory in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
Full Text: DOI


[1] Barcia, P.; Jörnsten, K., Improved Lagrangean decomposition: an application to the generalized assignment problem, European journal of operational research, 46, 84-92, (1990) · Zbl 0711.90055
[2] Carlier, J., The one-machine sequencing problem, European journal of operational research, 11, 42-47, (1982) · Zbl 0482.90045
[3] Carlier, J., Scheduling jobs with release dates and tails on identical machines to minimize the makespan, European journal of operational research, 29, 298-306, (1987) · Zbl 0622.90049
[4] Coffman, E.G.; Yannakakis, M.; Magazine, M.J.; Santos, C., Batch sizing and job sequencing on a single machine, Annals of operations research, 26, 135-147, (1990) · Zbl 0712.90035
[5] M.R. Garey, D.S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 · Zbl 0411.68039
[6] Jörnsten, K.; Näsberg, M., A new Lagrangian relaxation approach to the generalized assignment problem, European journal of operational research, 27, 313-323, (1986) · Zbl 0617.90068
[7] E.L. Lawler, Recent results in the theory of machine scheduling, in: A. Bachem, M. Grötschel, B. Korte (Eds.), Mathematical Programming, The State of the Art-Bonn 1982, Springer, Berlin, 1982, pp. 202-231
[8] E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys, Sequencing and Scheduling: Algorithms and Complexity, Handbooks in OR and MS, 4, Elsevier, New York, 1993
[9] Lageweg, B.J.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Minimizing maximum lateness on one machine: computational experience and some applications, Statistica nederlandica, 30, 25-41, (1976) · Zbl 0336.90029
[10] J.K. Lenstra, A.H.G, Rinnooy Kan, Sequencing and Scheduling, in: M. O’h Eigeartaigh, J.K. Lenstra, A.H.G. Rinnooy Kan (Eds.), Combinatorial Optimization: Annotated Bibliographies, Wiley, New York, 1985 · Zbl 0557.90044
[11] Mc Mahon, G.B.; Florian, M., On scheduling with ready times and due dates to minimize maximum lateness, Operations research, 23, 475-482, (1975) · Zbl 0301.90024
[12] S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, Chirchester, 1990
[13] Potts, C.N., Analysis of a linear programming heuristic for scheduling unrelated parallel machines, Discrete applied mathematics, 10, 155-164, (1985) · Zbl 0571.90035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.