A randomized algorithm for flow-shop scheduling

Garg, Naveen ; Jain, Sachin ; Swamy, Chaitanya (1999) A randomized algorithm for flow-shop scheduling In: Proceedings of the 19th Conference on Foundations of Software Technology and Theoretical Computer Science, December 13-15, 1999, Chennai, India.

Full text not available from this repository.

Official URL: https://link.springer.com/chapter/10.1007/3-540-46...


Shop scheduling problems are known to be notoriously intractable, both in theory and practice. In this paper we give a randomized approximation algorithm for flow shop scheduling where the number of machines is part of the input problem. Our algorithm has a multiplicative factor of 2(1 + δ) and an additive term of O(mln(m+ n)pmax)/δ2).

Item Type:Conference or Workshop Item (Paper)
Source:Copyright of this article belongs to Springer Verlag.
ID Code:101322
Deposited On:31 Jan 2018 09:34
Last Modified:31 Jan 2018 09:34

Repository Staff Only: item control page