V-SHAPED POLICIES FOR SCHEDULING DETERIORATING JOBS

• 成果类型: Article
• 署名作者: MOSHEIOV, G
• 署名单位: City University of New York (CUNY) System; Baruch College (CUNY); Hebrew University of Jerusalem
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.39.6.979
• 发表日期: 1991
• 页码: 979-991
• 关键词: PRODUCTION SCHEDULING; DETERMINISTIC SEQUENCING; single machine

摘要

A set of N jobs has to be processed on a single machine. Jobs have the same basic processing time, but the actual processing time of each job grows linearly with its starting time. A (possibly) different rate of growth is associated with each job. We show that the optimal sequence to minimize flow time is V-shaped: Jobs are arranged in descending order of growth rate if they are placed before the minimal growth rate job, and in ascending order if placed after it. Efficient (0(N log N)) asymptotically optimal heuristics are developed. Their average performance is shown to be extremely good: The average relative error over a set of 20-job problems is on the order of 10(-5).