Aarhus University Seal / Aarhus Universitets segl

Erland Hejn Nielsen

A (Small) Complexity Performance Contest: SPT versus LBFS

Research output: Working paperResearch

  • Department of Business Studies
  • CORAL - Centre for Operations Research Applications in Logistics
When discussing the nature of loading rules relevant to continuous dynamic job/flow shop systems, the general understanding is that results obtained in simpler structures of 2 to 4 machines are invariant to scaling and can be generalised without problems to more complex structures. The SPT (Shortest Processing Time) loading rule has to a great extent gained its reputation of superiority that way. However, emphasis on the element of job re-entrance and its possible consequence on the choice of loading rule have not really been present until the early nineties, when a series of interesting results on pure re-entrant flow shop structures emerges. It now seems that alternative loading rules as for instance the LBFS (Last Buffer First Served) due to its strong long run stabilising property attracts quite some interest. To be more precise about the complexity aspect, complexity in job/flow shops besides scaling also consists of re-entrance, limited resources on the operation of the machines in the shop as well as production stations connected in a network with binding limitations on the buffer space between the individual stations. Preliminary results seem to indicate that the LBFS scheduling rule in some cases undoubtedly are to be preferred to the famous SPT dispatching rule. The purpose of this paper is therefore to establish more evidence as to whether these preliminary findings can be supported or not. I shall present results for a class of re-entrant structures, which are not entirely only of theoretical interest, as well as results from a standard serial job/flow shop set-up, but with resource limitations that prevent the independent operations of the individual stations in the system.
Original languageEnglish
Publication statusPublished - 2002

    Research areas

  • Queuing theory, Re-entrant systems, Discrete-event simulation, Logistics

See relations at Aarhus University Citationformats

ID: 32303235