Scheduling with fixed delivery dates
成果类型：
Article
署名作者：
Hall, NG; Lesaoana, M; Potts, CN
署名单位：
University System of Ohio; Ohio State University; University of Southampton
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.49.1.134.11192
发表日期：
2001
页码：
134-144
关键词：
摘要：
In most classical scheduling models, it is assumed that a job is dispatched to a customer immediately after its processing completes. In many practical situations, however, a set of delivery dates may be fixed before any jobs are processed. This is particularly relevant where delivery is an expensive or complicated operation, for example, as with heavy machinery. A similar situation arises where customers find deliveries disruptive and thus require them to be made within a limited time interval that repeats periodically. A third possibility is that a periodic business function, for example, the supplier's billing cycle, effectively defines a delivery date, and includes all jobs that have been completed since the previous billing cycle. These situations are not adequately represented by classical scheduling models. We consider a variety of deterministic scheduling problems in which a job is dispatched to a customer at the earliest fixed delivery date that is no earlier than the completion time of its processing. Problems where the number of delivery dates is constant, and others where it is specified as part of data input, are studied. For almost all problems considered, we either provide an efficient algorithm or establish that such an algorithm is unlikely to exist. By doing so, we permit comparisons between the solvability of these fixed delivery date problems and of the corresponding classical scheduling problems.