工时依赖开工时间的作业在线调度策略设计与分析

项目名称： 工时依赖开工时间的作业在线调度策略设计与分析

项目编号： No.71301168

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 管理科学

项目作者： 余昇

作者单位： 中南财经政法大学

项目金额： 20.5万元

中文摘要： 近年来工时依赖开工时间的调度问题倍受研究者关注，其作业处理时长是与作业开始处理时间相关的一个变量。这个重要假设扩大了调度理论对实际问题的研究范围，例如机器除锈迹问题、灾害救援谁先谁后问题和多项贷款依次偿清问题等都能在此框架下建立调度模型。该类问题的现有研究普遍假设作业信息事先完全已知，然而现实中灾害何时何地发生烈度如何却不可预见。针对这种传统优化方法难以解决的在不完全信息下的实时在线决策问题，本项目拟采用在线理论与竞争分析方法对具有工时依赖开工时间的作业在线调度管理问题展开系统的研究。具体将工时依赖开工时间函数分为一般非线性、线性和简单线性三种函数类型；讨论作业按表单到来和按时间到来两种在线模式；考虑处理器和作业的约束限制条件；根据实际需求设立衡量目标准则；为不同模型分别设计在线策略，分析其竞争性能并评价实际执行效果。研究结果将丰富管理领域研究方法，提升我国在此类问题上的管理水平。

中文关键词： 调度优化；在线策略；工时依赖开工时间；竞争分析；

英文摘要： In recent years, more and more researchers have paid attentions to time-dependent scheduling problems, in which the processing time of a job is variable and depends on the starting time of the job. This crucial assumption allows us to apply the scheduling theory to a broader spectrum of problems. For example, in the framework of the time-dependent scheduling theory we may consider the problems of scheduling derusting operations, repayment of multiple loans, and scheduling a single fire-fighting recourse. In the last case when there are several fires to be controlled. The aim is to find such order of suppressing n existing fires that the total damage caused by the fires is minimized. The problem can be modeled as a single machine scheduling problem with time-dependent processing time and the total cost minimization criterion. Current knowledge in this area has been focused on the setting in which all jobs are available for processing at the very beginning. In practice, jobs may be released at arbitrary times. We may also have to make decisions based on the jobs currently presented without information about future jobs. The performance of online algorithms is typically measured by competitive analysis. Based on online theory and competitive analysis technology, this project will carry out a series of studies on d

英文关键词： Machine scheduling；Online algorithm；Time-dependent processing time；Competitive analysis；