非线性环境下的排序问题研究

Scheduling is an active branches of combinatorial optimization. This project studies several scheduling problems under nonlinear environment, focus on algorithm design and worst-case analysis. Several kinds of problems are considered, mainly scheduling problem with nonlinear objective function and scheduling problem with nonlinear machine load. The first class includes objectives such as lp norm of machines loads and the sum of (weighted) p-th power of jobs completion time. The second class includes scheduling problems with linear deterioration or exponentially learning effect, and scheduling of unreliable jobs. We will also consider speed scaling problem and peak demand minimization problem in order to minimize the consumption of energy.

排序问题是近年来组合优化研究的热点之一。本项目主要研究几类非线性环境下的排序问题，具体包括以极小化机器负载lp范数和以极小化工件完工时间p次方和等非线性函数为目标的排序问题，因工件加工时间随开工情况变化或涉及不稳定工件而形成的机器负载表达式为非线性函数的排序问题，以及计算机能源消耗和电力使用中的峰值控制问题等源自信息技术的非线性排序问题。上述问题在非线性排序中具有模型上的基础性，方法上的典型性，应用上的前瞻性。我们将应用计算复杂性理论和近似算法的设计与分析技术，结合非线性规划和连续函数分析性质，给出算法最坏情况界的估计。

排序问题是近年来组合优化研究的热点之一。本项目主要研究几类非线性环境下的排序问题。给出了以机器负载的l2范数为社会费用的有等级同型机排序博弈的PoA值。提出了机器可增减的排序博弈模型，给出了LPT，SPT，Makespan，Random等排序机制PoA和PoS的估计。设计了工件有不同大小时，以工件总完工时间为目标函数的单台机批排序问题和多台同型机带运输排序问题的近似算法。丰富发展了非线性环境下排序问题的最坏情况分析的成果与方法。