A fluid approach to job shop scheduling : theory, software and experimentation

Y. Nazarathy, G. Weiss

Onderzoeksoutput: Boek/rapportRapportAcademic

1 Downloads (Pure)


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 asymptoticaly 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 asymptoitc 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.
Originele taal-2Engels
Plaats van productieEindhoven
UitgeverijTechnische Universiteit Eindhoven
Aantal pagina's34
StatusGepubliceerd - 2009

Publicatie series

NaamSE report
ISSN van geprinte versie1872-1567


Duik in de onderzoeksthema's van 'A fluid approach to job shop scheduling : theory, software and experimentation'. Samen vormen ze een unieke vingerafdruk.

Citeer dit