Abstract
We consider the job shop scheduling problem unit-J m, where each job is processed once on each of m given machines. The execution of anyt ask on its corresponding machine takes exactly one time unit. The objective is to minimize the overall completion time, called makespan. The contribution of this paper are the following results: (i) For anyi nput instance of unit-J m with d jobs, the makespan of an optimum schedule is at most m+o(m), for d = o(m 1/2). For d = o(m 1/2), this improves on the upper bound O(m+d) given in [LMR99] with a constant equal to two as shown in [S98]. For d = 2 the upper bound is improved to \( m + \left\lceil {\sqrt m } \right\rceil \). (ii) There exist input instances of unit-J m with d = 2 such that the makespan of an optimum schedule is at least \( m + \left\lceil {\sqrt m } \right\rceil \), i.e., the result (i) cannot be improved for d = 2. (iii) We present a randomized on-line approximation algorithm for unit-J m with the best known approximation ratio for d = o(m 1/2). (iv) A deterministic approximation algorizhm for unit-J m is described that works in quadratic time for constant d and has an approximation ratio of \( 1 + 2^d /\left\lfloor {\sqrt m } \right\rfloor \) for d ≤ 2 log2 m.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Brucker, P.: An Efficient Algorithm for the Job Shop Problem with Two Jobs. Computing, 40:353–359, 1988.
Feige U., Scheideler, C.: Improved Bounds for Acyclic Job Shop Scheduling. Proc. 28th ACM Symposium on Theory of Computing, pp. 624–233, 1998.
Goldberg, L. A., Paterson, M., Srinivasan, A., Sweedyk, E.: Better Approximation Guarantees for Job-shop Scheduling. Proc. 8th ACM-SIAM Symposium on Discrete Algorithms, pp. 599–608, 1997.
Leighton, F. T., Maggs, B. M., Rao, S. B.: Packet Routing and Job-Shop Scheduling in O(Congestion+Dilation) steps. Combinatorica, 14:167–186, 1994.
Leighton, F. T., Maggs, B. M., Richa, A. W.: Fast Algorithms for Finding O(Congestion+Dilation) Packet Routing Schedules. Combinatorica, 19:375–401, 1999.
Lenstra, J. K., Rinnooy Kan A. H. G.: Computational Complexity of Discrete Optimization Problems. Annals of Discrete Mathematics, 4:121–140, 1979.
Scheideler, C.: Universal Routing Strategies for Interconnection Networks. Lecture Notes in Computer Science 1390, Springer Verlag, 1998.
Shmoys, D. B., Stein, C., Wein, J.: Improved Approximation Algorithms for Shop Scheduling Problems. SIAM J. on Computing, 23:617–632, 1994.
Williamson, D. P., Hall, L. A., Hoogeveen, J. A., Hurkens, C. A. J., Lenstra, J. K., Sevast’janov, S. V., Shmoys, D. B.: Short Shop Schedules. Operations Research, 45:288–294, 1997.
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hromkovič, J., Steinhöfel, K., Widmayer, P. (2001). Job Shop Scheduling with Unit Length Tasks: Bounds and Algorithms. In: Theoretical Computer Science. ICTCS 2001. Lecture Notes in Computer Science, vol 2202. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45446-2_6
Download citation
DOI: https://doi.org/10.1007/3-540-45446-2_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42672-1
Online ISBN: 978-3-540-45446-5
eBook Packages: Springer Book Archive