机器具有维护活动的新兴排序问题研究

Machine scheduling with maintenance activities is a newly developing scheduling model, it is featured with theory and widely applied in modern industrial production and resource management, and so, has attracted extensive and considerable attentions from domestic and overseas scholars. We will study this new model in this project, the machine environments considered in this project include single machine and a single parallel-batching machine, combining with three different maintenance activities and job rejection. In this project, we will determine the computational complexity for various related scheduling problems: either present polynomial-time algorithm, or prove the NP-hardness. Moreover, for NP-hard scheduling problems, we will design polynomial-time approximation algorithms with good performance and efficient heuristic algorithms. This project will construct effective solution methods and basic theories, and make innovative research results in computational complexity analysis and approximation algorithms. As a result, we will provide complete research results for scheduling with maintenance activities.

机器具有维护活动的排序是产生于现代化工业生产及资源管理的一种新兴排序模型，因为其应用的广泛性而被国内外专家学者关注。本项目拟对这一模型开展研究工作，所考虑的是机器具有三类维护活动下的单台机器及单台平行批处理机排序问题并涉及到工件可被拒绝的加工假设。本项目首先确定各类相关排序问题的计算复杂性：或者给出问题的多项式时间算法、或者证明问题的NP-困难性；然后对于NP-困难的相关排序问题，设计出性能良好的多项式时间近似算法及有效的启发式算法。本项目力求建立有效的求解方法和基本理论，在计算复杂性分析和近似算法等方面做出创新性的研究成果，从而丰富和完善了关于机器维护活动的排序理论成果。

在经典排序问题中，通常假设机器在加工工件的过程中是始终可用的。但在实际的工业生产中，经常会因为生产计划的变更或机器的维护，而导致机器在某个时间段不能使用或不能执行当前的加工任务。而合理地对机器进行维护以减少机器失效和机器故障的发生率，已成为制造企业降低运作成本、提高生产率和市场竞争力的有效手段。因此，针对这种实际应用需求，学者们提出了机器具有维护活动的排序模型。在这类新模型中，适时对机器进行维护，合理安排工件的加工次序使得相应的目标函数达到最优。主要研究了机器具有维护活动与工件可拒绝的单机排序问题, 维护活动必须在截止日期前或者在固定的时间段内执行。接受工件的排序目标是最大完工时间, 最大延迟, 最大延误, 最大加权完工时间, 总(加权)完工时间和总(加权)误工工件数。研究目标是寻求接受工件的排序费用与拒绝工件的总拒绝成本的Pareto 优化排序。 证明了研究的排序问题都是NP-困难的。设计了伪多项式时间算法求解问题，并通过研究一些相关的辅助Pareto 排序问题得到问题的时间复杂度结果。还研究了具有退化的维护活动和工件可拒绝的平行机排序问题, 每台机器最多执行一次维护活动, 每个维护活动的维护时长是其开始时刻的线性函数。通过确定维护活动的位置和接受工件的加工顺序, 最小化接受工件的排序成本与拒绝工件的总拒绝成本和。当排序目标为最大完工时间时，我们设计了一个伪多项式时间算法、一个2-近似算法和一个完全多项式时间近似方案；排序目标为总完工时间时，我们给出了一个多项式时间算法；排序目标为是最大延迟和一定条件下的加权总完工时间时，我们分别提出了伪多项式时间算法来解决这两个问题。