带加工集约束的排序问题研究

本课题以计算复杂性理论和近似算法理论为主要工具，研究带加工集约束的排序问题. 所谓带加工集约束, 是指每个工件都对应一个机器子集, 且该工件只能由其所对应的机器子集中的机器来加工。带加工集约束的排序理论在生产调度和服务科学等方面均有应用。本课题拟研究的几个带加工集约束的排序问题，还与排序理论中的一个非常重要的公开问题有紧密的内在联系。本课题的研究结果，有可能为回答这个公开问题提供新的线索。因而，本研究在排序基础理论发展和实际应用方面均有积极的意义。

本项目主要研究带加工集约束的生产排序模型及其在订单选择与生产排序上的推广应用。我们在一些相关的基础模型的研究上取得了一定的进展。首先，在带工件集约束排序模型方面，对工件可被拒绝的情形，我们设计的算法获得了比文献中的更好的性能比。其次，在经典的平行机订单选择与生产排序问题上，我们取得了较好的结果。再次，在考虑顾客服务水平和订单满足率的订单选择与生产排序问题上，我们也完成了两篇高质量的工作论文。最后，我们也研究了一些重要的动态生产批量问题，并取得了较好的成果。