Job Shop Scheduling with Unit Length Tasks: Bounds and Algorithms

Authors

  • Juraj Hromkovič Department of Informatics, ETH Zurich, ETH Zentrum, CH-8092 Zürich, Switzerland
  • Tobias Mömke Department of Informatics, ETH Zurich, ETH Zentrum, CH-8092 Zürich, Switzerland
  • Kathleen Steinhöfel King’s College London, Department of Computer Science, Strand, WC2R 2LS London, UK and FIRST – Fraunhofer Institut für Rechnerarchitektur und Softwaretechnik, Kekul#xE9;straße 7, 12489 Berlin, Germany
  • Peter Widmayer Department of Informatics, ETH Zurich, ETH Zentrum, CH-8092 Zürich, Switzerland

Keywords:

Scheduling, Makespan, Multiple machines, Approximation Algorithms, Online Algorithms, Competitive ratio

Abstract

We consider the job shop scheduling problem unit–Jm, where each job is processed once on each of m given machines. Every job consists of a permutation of tasks for all machines. The execution of any task 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 any input instance of unit–Jm with d jobs, the makespan of an optimum schedule is at most m + o(m), for d = o(m1/2). This improves on the upper bound O(m + d) given in [5] where O hides a constant equal to two as shown in [7]. For d = 2 the upper bound is improved to m+ ⌈ √m ⌉. (ii) There exist input instances of unit–Jm with d = 2 such that the makespan of an optimum schedule is at least m + ⌈ √m ⌉, i.e., our upper bound for d = 2, see result (i), cannot be improved. (iii) We present a randomized on-line approximation algorithm for unit–Jm with the best known approximation ratio for d = o(m1/2). (iv) There is no deterministic on-line algorithm with a competitive ratio better than 4/3 for unit–Jm with two jobs, and for three or more jobs, there is no deterministic on-line algorithm which is better than 1.5 competitive. Compared with the expected competitive ratio of (iii) which tends to 1, this shows that for unit–Jm randomization is very powerful compared with determinism. For two and three jobs, deterministic on-line algorithms with competitive ratios tending to 4/3 and 1.5 respectively are presented. (v) A deterministic approximation algorithm for unit–Jm is described that works in quadratic time for constant d and has an approximation ratio of 1 + 2d/⌊√m⌋ for d ≤ 2 log2m. Key words: Scheduling, Makespan, Multiple machines, Approximation Algorithms, Online Algorithms, Competitive ratio

Downloads

Published

2007-02-07

How to Cite

Hromkovič, J., Mömke, T., Steinhöfel, K., & Widmayer, P. (2007). Job Shop Scheduling with Unit Length Tasks: Bounds and Algorithms. Algorithmic Operations Research, 2(1). Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/2729

Issue

Vol. 2 No. 1 (2007)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.