工作量
计算机科学
地铁列车时刻表
集合(抽象数据类型)
数学优化
分配问题
运筹学
数学
操作系统
程序设计语言
作者
Alessandro Agnetis,Stefano Smriglio
标识
DOI:10.1002/1520-6750(200008)47:5<359::aid-nav1>3.0.co;2-j
摘要
This paper addresses the problem of finding a feasible schedule of n jobs on m parallel machines, where each job has a deadline and some jobs are preassigned to some machine. This problem arises in the daily assignment of workload to a set of flight dispatchers, and it is strongly characterized by the fact that the job lengths may assume one out of k different values, for small k. We prove the problem to be NP-complete for k = 2 and propose an effective implicit enumeration algorithm which allows efficiently solution a set of real-life instances. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 359–376, 2000
科研通智能强力驱动
Strongly Powered by AbleSci AI