Makespan-related criteria for comparing schedules in stochastic environments
- PDF / 238,840 Bytes
- 8 Pages / 595 x 842 pts (A4) Page_size
- 118 Downloads / 187 Views
#1998 Operational Research Society Ltd. All rights reserved. 0160-5682/98 $12.00 http://www.stockton-press.co.uk/jor
Makespan-related criteria for comparing schedules in stochastic environments V Portougal and D Trietsch University of Auckland, New Zealand The ultimate goal of stochastic modelling in shop scheduling is to select the sequence with the best statistical distribution and use it to book capacity and quote delivery dates. For tractability reasons, stochastic models usually employ the expected value of the makespan as the criterion (instead of really looking at the whole distribution). In practice, this criterion is much harder to satisfy than solving for the (already strongly NP-hard) deterministic makespan. Therefore, other criteria have been proposed, and it is important to ask which one is best for long-term expected bene®ts. This paper analyses and compares several existing criteria for that purpose. We also suggest adding a variance minimisation objective, so that the quoted lead time required to satisfy a given service level will be minimised. Keywords: scheduling; stochastic schedules
Introduction Sequencing and scheduling play a crucial role in manufacturing management. In the current competitive environments like lean production and agile manufacturing, effective scheduling has become a survival necessity.1 Companies have to meet committed shipping dates and schedule the use of resources in the most ef®cient manner, and thus capacity management is now a major focus of competitive advantage. Therefore, the need for ef®cient scheduling procedures was never so strong. Nevertheless, after nearly four decades of development, scheduling theory still has little impact on practical scheduling. One of the major recognised reasons for this is the ubiquitous (failed) attempt to use deterministic scheduling in highly stochastic environments.2 Sequencing and scheduling theory branched into deterministic and stochastic models at an early stage of its development. Since then the major research effort was dedicated to deterministic models.1 Concentrating on deterministic models is theoretically justi®ed by the complexity of the stochastic problems, especially since deterministic problems are also very complex. At present, there is no doubt that real sequencing and scheduling practice is mainly deterministic: In terms of planning, it often utilises expected values as input into a deterministic solution model. In terms of results, it usually provides static sequences and deterministic completion time estimates. The latter are used to book capacity on key resources and to make delivery promises. Meanwhile, planners are well aware that the basic quantitative property of all scheduling models, namely Correspondence: Dr V Portougal, MSIS Department, University of Auckland, Private Bag 92019, Auckland, New Zealand E-mail: [email protected]
operational processing time, is random. Therefore, the actual realisation of a given solution is also random. At best, we can ®nd its statistical distribution, or a good
Data Loading...
