Integrating combinatorial optimization with queueing theory for dynamic scheduling

各种各样的行业和服务都面临着将一系列传入的工作分配给一组复杂资源的决策。例如，为了提供化疗，医院需要考虑以下事实：患者可能早到或晚到，药物方案的不同保质期和特异性对按时制备和/或储存药物造成挑战，治疗患者所需的时间、设备（如床、椅子）、房间和工作人员可能会根据患者的病情而改变。类似的问题也出现在制造业中，生产、维护和交付操作必须进行计划；在电信行业，带宽的分配必须满足用户的需求；在交通运输应用中，比如跑道调度。在所有这些问题中，常见的是随机到达的不同请求，必须通过分配复杂的资源组合来满足。

A wide variety of industries and services are faced with making decisions about the assignment of a stream of incoming jobs to a complex set of resources. For example, to deliver chemotherapy, a hospital needs to take into account the fact that patients may arrive early or late for their appointments, that differing shelf-lives and specificities of drug regimens create a challenge for on-time drug preparation and/or storage, and that the time, equipment (e.g., beds, chairs), rooms, and staff required for the treatment of a patient may change based on the patient's condition. Similar problems arise in manufacturing, where production, maintenance, and delivery operations must be scheduled; in telecommunications where bandwidth must be allocated to fulfill user needs; and in transportation applications such as runway scheduling. Common among all these problems is the stochastic arrival of a varying requests which must be met by the allocation complex combinations of resources.