Priority Rules for Multi-Task Due-Date Scheduling under Varying Processing Costs

• 成果类型: Article
• 署名作者: Xu, Yunjian; Shi, Cong; Duenyas, Izak
• 署名单位: Singapore University of Technology & Design; University of Michigan System; University of Michigan; University of Michigan System; University of Michigan
• 刊物名称: PRODUCTION AND OPERATIONS MANAGEMENT
• ISSN/ISSBN: 1059-1478
• DOI: 10.1111/poms.12606
• 发表日期: 2016
• 页码: 2086-2102
• 关键词: multi-task due-date scheduling; varying processing costs; make-to-order; priority rule

摘要

We study the scheduling of multiple tasks under varying processing costs and derive a priority rule for optimal scheduling policies. Each task has a due date, and a non-completion penalty cost is incurred if the task is not completely processed before its due date. We assume that the task arrival process is stochastic and the processing rate is capacitated. Our work is motivated by both traditional and emerging application domains, such as construction industry and freelance consulting industry. We establish the optimality of Shorter Slack time and Longer remaining Processing time (SSLP) principle that determines the priority among active tasks. Based on the derived structural properties, we also propose an effective cost-balancing heuristic policy and demonstrate the efficacy of the proposed policy through extensive numerical experiments. We believe our results provide operators/managers valuable insights on how to devise effective service scheduling policies under varying costs.