A fluid approach to large volume job shop scheduling

Search Swinburne Research Bank

Home

List of Titles

Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.3/158850

Check Swinburne's subscriptions for full text availability

Title: A fluid approach to large volume job shop scheduling
Author(s): Nazarathy, Yoni; Weiss, Gideon
Abstract: We consider large volume job shop scheduling problems, in which there is a fixed number of machines, a bounded number of activities per job, and a large number of jobs. In large volume job shops it makes sense to solve a fluid problem and to schedule the jobs in such a way as to track the fluid solution. There have been several papers which used this idea to propose approximate solutions which are asymptotically optimal as the volume increases. We survey some of these results here. In most of these papers it is assumed that the problem consists of many identical copies of a fixed set of jobs. Our contribution in this paper is to extend the results to the far more general situation in which the many jobs are all different. We propose a very simple heuristic which can schedule such problems. We discuss asymptotic optimality of this heuristic, under a wide range of previously unexplored situations. We provide a software package to explore the performance of our policy, and present extensive computational evidence for its effectiveness.
Publication type: Journal article
Source: Journal of Scheduling: incorporating selected papers from the 'New challenges in scheduling theory' workshop, Marseille, France, 12-16 May 2008 / Michael Bender, Jacek Blazewicz, Erwin Pesch, Denis Trystram and Guochuan Zhang (eds.), Vol. 13, no. 5 (Oct 2010), pp. 509-529
Publication year: 2010
FOR Code(s): 0102 Applied Mathematics; 0103 Numerical and Computational Mathematics
Keyword(s): Approximate solution; Asymptotic analysis; Asymptotic optimality; Asymptotically optimal; Fixed numbers; Fluid approximation; Fluid problem; Fluid solutions; Fluid tracking policy; Fluids; General situation; Job shop scheduling problems; Makespan; Stochastic scheduling; Scheduling; Scheduling algorithms; Stochastic systems
Publisher: Springer
ISSN: 1094-6136
Publisher URL: http://dx.doi.org/10.1007/s10951-010-0174-0
Peer reviewed