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

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 design and evaluation of algorithms for online scheduling problems with time-dependent processing time. Specifically, among many different functions describing time-dependent processing time, the three generally accepted classifications are non-linear, linear and simple linear. Two online models are commonly introduced. The first one assumes that jobs arrive in a list, while another assumes that jobs arrive over time. The constraints of machines and jobs are also need to be considered. According to practical demands, new criteria on measuring goals should be set. After the modeling, different strategies are designed to different online scheduling models. Competitive ratios are proved to measure the performance of these online algorithms. This research project is of great worth, and research results will improve the research methods and promote the management level.

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

本项目研究了当作业的时长为一般线性函数并存在多个速率可调整行为（经过一次调整，可以提高处理器生产效率）的单处理器调度模型，提出了一个相较与前人研究更合理的作业时长，并考虑存在多个调整行为。模型的求解目标是最小化最大完成时间。针对该问题设计了一个同余调度策略，并且可以在多项式时间内得到解决。另外，对于更一般的作业线性时长的多处理器问题，给出了该问题最优解的几个基本性质。在作业的基本处理时间只有有限的两个值可取的情形下，给出了最优的调度策略。对于在线调度问题，考虑了有服务质量（quality of service）要求的模型，构建了具有完成度阈值限制的可中断在线作业处理模型。 . 由于企业在租赁和购买设备时采用不同的计税方式导致实际设备使用费发生变化，研究了企业在租赁和购买设备时采用不同的计税方式（可理解为一种变相的工时依赖开工时间）导致实际设备使用费发生变化，因此需要在市场环境下考虑所得税对企业设备租赁行为决策的影响，提出了基于所得税的在线设备赁购问题。给出了该问题的离线最优解，设计了赁购策略RBS和租赁策略RS并进行竞争分析得到策略竞争比和问题下界，证明在一定情形下策略RS是最优在线策略，通过策略比较分析证实所得税税率高低会影响企业的设备赁购决策，对不同策略的竞争比影响程度也不同。. 研究结果丰富了管理领域研究方法，具有一定的管理科学意义。