Klaus Jansen
- 1.L. A. Goldberg, M. Paterson, A Srinivasan and E. Sweedyk, Better approximation guarantees for jobshop scheduling, In Proceedings of the 8th Symposium on Discrete Algorithms (1997), pp.599-608. Google Scholar
Digital Library
- 2.L. A. Halt, Approximability of flow shop scheduling, Mathematical Programming 82 (1998), pp.175-190. Google ScholarDigital Library
- 3.L. A. Hall and D. B. Shmoys, Approximation algorithms for constrained scheduling problems, In Proceedings of the IEEE 30th Annual Symposium on Foundations of Computer Science (1989), pp. 134- 139.Google ScholarDigital Library
- 4.L. A. Hall and D. B. Shmoys, Near-optimal sequencing with precedence constraints, In Proceedings of IPCO (1990), pp.249-260. Google ScholarDigital Library
- 5.L. A. Hall and D. B. Shmoys, Jackson's rule for single-machine scheduling: Making a good heuristic better, Mathematics of Operation Research 17 (i992), pp.22-35. Google ScholarDigital Library
- 6.E. L. Lawler, J. K. Lenstra, A. H. G. Rinooy Kan and D. B. Shmoys, Sequencing and scheduling: Algorithms and complexity, In S. C. Graves, A. H. G. Rinooy Kan and P. H. Zipkin, editors, Handbook in Operation Research and Management Science, v. 4, Logistics of Production and Inventory, North-Holland (1993), pp.445-522.Google Scholar
- 7.T. Leighton, B. Maggs and S. Rao, Packet routing and job-shop scheduling in O(Congestion+Dilation) Steps, Combinatorica 14 (1994), pp. 167-186.Google ScholarCross Ref
- 8.T. Leighton, B. Maggs and A. Richa, Fast algorithms for finding O(congestion+dilation) packet routing schedules, to appear in Combinatorica.Google Scholar
- 9.C. N. Potts, Analysis of a linear programming heuristic for scheduling unrelated parallel machines, Discrete Applied Mathematics i0 (1985), pp. 155- 164.Google Scholar
- 10.P. Schuurman and G. J. Woeginger, Approximation algorithms for the multiprocessor open shop scheduling problem, Technical Report COSOR 97- 23, Eindhoven University, The Netherlands.Google Scholar
- 11.S. V. Sevast'janov, Bounding algorithm for the routing problem with arbitrary paths and alternative servers, Cybernetics 22 (1986), pp.773-780.Google ScholarCross Ref
- 12.S. V. Sevast'janov, On some geometric methods in scheduling theory: a survey, Discrete Applied Mathematics 55 (1994), pp.59-82. Google ScholarDigital Library
- 13.S.V. Sevast'janov, Nonstrict vector summation in multi-operation scheduling, Annals of Operations Research 83 (1998), pp. 179-212.Google ScholarCross Ref
- 14.S. V. Sevastianov, G. J. Woeginger, Makespan minimization in open shops' A polynomial time approximation scheme, Mathematical Programming 82 (1998), pp.191-198.Google ScholarCross Ref
- 15.D. B. Shmoys, C. Stein and J. Wein, Improved approximation algorithms for shop scheduling problems, SIAM journal of Computing 23 (1994), pp.617-632. Google ScholarDigital Library
- 16.D. P. Williamson, L. A. Hall, J. A. Hoogeveen, C. A. J. Hurkens, J. K. Lenstra, S. V. Sevast'janov and D. B. Shmoys, Short shop schedules, Operation Research 45 (1997), pp.288-294.Google ScholarDigital Library
Index Terms
- Makespan minimization in job shops: a polynomial time approximation scheme
Recommendations
Makespan Minimization in Job Shops: A Linear Time Approximation Scheme
In this paper we present a linear time approximation scheme for the job shop scheduling problem with a fixed number of machines and fixed number of operations per job. This improves on the previously best $2+\epsilon$, $\epsilon > 0$, approximation ...
Job selection in two-stage shops with ordered machines
We consider job selection problems in shops with ordered machines.We solve the open shop problem in polynomial time.We show that the job shop problem is ordinary NP-hard.We consider the flow shop problem with the total job completion time objective. We ...
A Fluid Heuristic for Minimizing Makespan in Job Shops
We describe a simple online heuristic for scheduling job shops. We assume there is a fixed set of routes for the jobs, and many jobs, say N, on each route. The heuristic uses safety stocks and keeps the bottleneck machine busy at almost all times, while ...
Comments