订单排序模型及其最优性研究

In an order scheduling problem, a job customer propose his requests in form of order and the scheduler of machine agents should determine his strategies according to the order parameters. This project will examine the establishment of model, combinatorial structural characteristics, algorithm design, the theoretical analysis of algorithm performance and simulation verification for order scheduling problem. (1) In modeling, consider the responding time strategies of the machine agents in accordance with the order. Introduce cost function (such as manpower, capital and other costs) which can impact the job parameters and machinery costs. Establish the mechanism to refuse or to accept an order. Consider the agency collaboration or competition mode in an order scheduling system. Study game model of multi-agent.(2) Analyze the combinatorial structural characteristics of some special order scheduling problems by methods of algebraic structure theory. Based on the understanding of such combinatorial features to explore the complexity theory.(3) Design high performance algorithms and theoretically analyze and simulate its performance verification. Analyze how the nature of the benefit function can impact scheduling decision sensitivity. The purpose of this project is to provide a theoretical basis and technical guidance for solving practical problems.

订单排序问题是工件客户向机器代理以订单方式提出加工请求，机器代理方根据订单参数确定加工策略。本课题将深入研究订单排序模型的建立、组合结构特性分析、算法设计及算法性能的理论分析和模拟验证。 (1) 模型方面，考虑机器方依据订单模式建立回应时间策略，引入影响工件参数费用函数(如人力、资金等费用)及机器费用，建立订单的接受或拒绝决策机制，考虑订单系统内各方代理的协作或竞争方式,研究多方代理的博弈模式。(2) 以代数结构理论方法分析一些特殊订单排序的组合结构特性，基于这种代数组合特性来探讨复杂性理论。(3) 设计高性能算法并进行理论分析和模拟验证，分析效益函数性质对排序决策的灵敏性。本课题的目的是为解决实际问题提供理论依据和技术上的指导性方案。

本项目研究的问题具有广泛的实际应用背景并且在组合优化领域具有重要的理论价值。根据项目计划，我们主要研究有：1. 对于在ｍ台平行机上工件有单调非减的到达时间和单调非增的加工时间的半在线排序问题，目标函数是最小化最大完工时间时，证明 了3/2-1/2m为LS算法的最坏性能比,并猜想紧界为4/3-1/3m，也研究了LPT算法在工件具有相似加工时间的最坏性能比，得到部分紧界结果。2. 研究了m台相同平行机上工件有预约到达时间，目标函数为最小化最大完工时间的ordinal半在线排序问题，给出了近似算法，并证明了近似算法的最坏性能比的上界。3. 研究了一致平行机上订单排序的问题，分别给出了最坏性能比为12和7.461的近似算法。4. 对机器和工件多方代理都有自私性的博弈排序问题，我们考虑了双向纳什均衡的POA(Price of Anarchy)，给出并证明了两台机上当工件有相似加工长度时的紧界，此紧界是关于相似度的一个很复杂的分段线性函数。当机器台数m大于2 且小于10时的紧界是4/3. 当机器台数大或等于10时，我们给出了比现有界更紧的界。5. 通过对组合结构性质的研究，对布尔可满足性问题(SAT)引入了一类可分离 SAT 问题,即 3-正则可分离可满足性问题(3-RSSAT),证明了 3-RSSAT 是 NP 完全问题,给出了一般 SAT 问题 3-正则可分离性的 O(1.890^n)判定算法. 然后,利用矩阵相乘算法的研究成果,给出了 3-RSSAT 问题的 O(1.890^n)精确算法,该算法与子句长度无关. 6. 研究了进化算法收敛性问题，我们假定适应值函数为非单射的，借助于 Markov 链，通过对状态空间的合理划分和状态的适当排序，获得了多基因系统中变异算子的良好性质．基于所建立的一般性 Markov 模型和转移矩阵的结构特征，分别在两种衡量方式下证明了算法呈现指数级收敛速度，其估计式无需对变异率额外施加条件．