线性或非线性约束下一些排序问题的复杂性和算法

Scheduling problem is a class of classic and fundamental combinatorial optimization problems, including a variety of models. They have important applications in various fields, such as industrial production, computer science, and management science. Depending on the background of the problem, each scheduling problem has its own parameters, e.g., processing time, machine speed and weight. Traditionally, the values of these parameters are often assumed to be known and given. In some real-world applications, the procedure of obtaining these values is always an optimization problem, for example, the parameters should satisfy a series of linear or nonlinear constraints. Based on the existing research on the problem of the identical parallel machine scheduling under linear constraints, this project studies several classic machine scheduling problems under linear or nonlinear constraints, which have more general machine environments or objective functions, and some parameters should satisfy certain given linear or nonlinear constraints. The main purpose is to analyze the computational complexity of these problems, and design algorithms for them. The studied problems have wide range of applications in the real life. Theoretically, they have more complicated and general structures than the related problems studied in the existed research. It is required to significantly improve the known techniques and results or develop new methods. The research of this project will further deepen and expand our knowledge on the combinatorial optimization problems under linear constraints, as well as enriching the field of scheduling.

排序问题是一类经典和基本的组合优化问题，包含各种各样的模型，在工业生产、计算机和管理科学等方面都有重要的应用。根据问题背景的不同，每个排序问题都有自身的参数，比如加工时间、机器速度、权重等。传统上，这些参数的值都假定是已知和给定的。在一些现实应用中，很可能得到它们的过程本身也是一个优化问题，例如从某些参数满足的线性或非线性约束中决定。本项目基于线性约束下的同型平行机排序等问题的已有研究基础，研究几个具有更复杂的机器环境或优化目标的经典排序问题，其中问题的某些参数满足给定的线性约束，或更一般的凸约束或二次约束，分析它们的计算复杂性和设计算法。这些线性或非线性约束下的排序问题在生活中都有广泛应用场景，理论上比已有研究的线性约束下的排序问题具有更复杂和一般的结构，需要对已知的技术和结果加以改进或发展新的方法。本项目将进一步深化和拓展对线性约束下的组合优化问题的认识，并丰富排序领域的研究。

排序问题是一类经典和基本的组合优化问题，包含各种各样的模型，在工业生产、计算机和管理科学等方面都有重要的应用。根据问题背景的不同，每个排序问题都有自身的参数，比如加工时间、机器速度、权重等。传统上，这些参数的值都假定是已知和给定的。在一些现实应用中，很可能得到它们的过程本身也是一个优化问题，例如从某些参数满足的线性或非线性约束中决定。在本青年基金项目支持下，课题组主要研究了以下三类问题：线性约束下的同类机排序问题、线性约束下的车间排序问题和相关的线性约束下的图优化问题，分析这些问题它们的计算复杂性和设计算法。这些问题比已有研究的排序问题和组合优化问题具有更复杂和一般的结构，本项目结合和改进已知的技术，对不同情形下各个研究问题的复杂性有清晰的刻画，再根据不同情形设计了有效的精确算法或近似算法，并进行理论分析和讨论。具体地，对于一些特殊情形，比如线性约束的个数或参数的不同数值总数是已知常数时，这些问题都可以找到多项式时间的算法；对于一般情况，本项目研究发现即使原来的排序问题是简单的，线性约束下的问题都可能是NP-难的,甚至是不可近似的。本项目的研究结果将进一步深化和拓展对线性约束下的排序和其它组合优化问题的认识和理解，丰富排序领域的研究和结果，并为相关问题的现实应用领域提供理论依据和指导。