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

项目名称： 订单排序模型及其最优性研究

项目编号： No.11471110

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 数理科学和化学

项目作者： 李荣珩

作者单位： 湖南师范大学

项目金额： 66万元

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

中文关键词： 排序问题；排序算法；算法设计与分析；在线算法；竞争比

英文摘要： 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.

英文关键词： scheduling problem;scheduling algorithm;algorithm design and analysis;online algorithm;competitive ratio