释放时间和工期同序的单机连续型批调度问题

本文研究的连续型批处理机调度问题, 是在钢铁工业管坯的加热过程中提出来的. 工件带有释放时间和工期, 工件进入和离开机器是按周期依次进行的. 本文针对单机连续型批调度问题中工件释放时间和工期同序的情况, 分析了极小化最大拖期和拖期工件数等问题的计算复杂性, 证明了两类问题都是强NP-难的. 对于工件的释放时间和加工时间、工期都同序的特殊情况, 分别给出了能够获得对应问题的最优解的多项式算法.     

极小化最大完工时间的单机连续型批调度问题

从钢铁工业中加热炉对管坯的加热过程,提出一种新的连续型批处理机调度问题,与传统批处理机调度问题的批进批出方式不同,其主要特征为批中工件的进入、处理和离开都连续进行,批B_i的处理时间与该批的大小|B_i|、批中工件T_j的处理时间p_j及机器的容量C都有关,表示为p^{(i)}=dmax_{T_jin B_i}{p_j}(1+displaystylefrac{|B_i|-1}{C}).对于极小化最大完工时间问题,给出了一个复杂性为O(n^2)的动态规划算法,并证明了这个算法的最优性.     

最小化碳排放的可持续机器调度问题

针对单机器生产系统、允许在生产间歇开关机器的可持续调度问题,以最小化碳排放为目标建立数学规划模型,同时对机器的开关机和产品的生产计划进行决策.利用动态规划算法对模型进行求解分析,提出阶段决策最优性条件,并给出精确算法.通过模拟算例和企业案例的计算分析表明,利用所提出的可持续调度方法可以显著减少生产过程中的碳排放.     

单台批处理机总加权完成时间最小化的启发式算法

批处理机总加权完成时间最小化问题的复杂性目前还没有确定,因此有必要研究该问题的启发式算法．基于对该问题最优解性质的分析,提出了工件分批的最优性质．分别基于WSPT规则和SPT规则对工件进行总排序,利用工件最优分批性质进行分批,提出了两种启发式算法（简称WSPTS和SPTS）．为了检验算法的性能．将提出的算法与此问题的基准算法和常规算法进行了比较,结果表明,启发式算法WSPTS要优于其他的算法,而SPTS算法的性能最优．     

基于总加权完成时间的可重入混合流水车间调度问题

研究以最小化总加权完成时间为目标的可重入混合流水车间调度问题(RHFS-TWC),并构建问题的整数规划模型.根据模型的特点,设计基于二维矩阵组的调度解编码方案,结合NEH启发式算法确定工件初始加工顺序,生成高质量初始调度解群.为避免算法陷入早熟及扩大解的搜索空间,给出IGA的遗传参数自适应调整策略,最终形成NEH-IGA融合求解策略.针对不同规模问题分别用传统GA、基于遗传参数自适应调整的IGA、NEH启发式、NEH-IGA算法进行仿真测试,仿真结果表明NEH启发式和遗传参数自适应动态调整策略的引入有效改善了原有GA的求解能力,NEH-IGA算法在求解RHFS-TWC问题方面优势明显.     

具有提前ö拖期惩罚的热轧钢管批调度问题研究

建立了具有提前／拖期惩罚的热轧钢管批调度问题的混合整数非线性规划模型,提出并证明了给定合同排序下的最优组批方式,从而将原问题转化为易求解的合同排序问题．同时,建立了转化问题的数学模型并设计了遗传算法．仿真实验验证了模型和算法的有效性．     

最小化全局完成时间的成像卫星任务规划算法

成像侦察卫星任务规划问题是一类典型多约束组合优化问题.最小化全局完成时间是任务规划领域时效性要求较高情况下的一种优化目标.提出一种整合整数规划与约束规划方法,在最小化任务规划方案全局完成时间的目标下,求解成像侦察卫星任务规划问题的组合算法.该算法通过应用Benders分解将原约束整数规划模型划分为主问题与子问题两部分,采用软件MOSEK与GECODE对主、子问题分别求解.根据子问题求解结果生成剪枝约束,返回主问题迭代,直到获得优化解.算法有效性通过仿真实验进行了检验并取得预期效果.     

基于最小化传输和完成时间的多DAG调度

针对云计算环境下多个有向无环图(DAG)工作流的调度问题,提出一种基于最小化数据传输时间和任务完成时间(LTCT)的算法,用于处理具有相同优先级的多个DAG工作流之间的调度问题。在多个DAG优先级各不相同时的情况下,给出多优先级多DAG的混合调度算法。实验结果表明,LTCT算法较E-Fairness算法在保证多DAG调度公平性的基础上,能避免额外的数据传输开销,有利于缩短整个工作流的执行Makespan,提高资源的利用率。     

最小化提前和延误惩罚的批处理问题

考虑机器容量有限的同时加工排序问题, 为享有公共交货期窗口[e; d]的n个工件分批并排序以最小化总的赋权提前/延误惩罚. 本文把窗时排序与同时加工排序结合起来研究, 假设每个批的容量是b(< n, 其中n为工件的个数), 而且最早交货期e 和最晚交货期d已知. 但该问题是NP–完备的, 首先给出最优排序的几条性质, 进而解决了两类特殊情况.     

基于优先级和优化完成时间的网格调度算法

网格由大量的异构资源组成,具有复杂性、动态性和自治性特点。高效的网格调度算法可以充分利用网格系统资源,提高网格处理应用程序的能力。Min min算法是一个简单、快速、有效的调度算法,但由于总是先分配小任务而不能确保负载平衡。文中首先对网格系统中任务的数据传输和执行进行分析,计算并优化Min min算法的任务完成时间,再根据任务需求赋予任务优先级,通过优先级安排任务调度,提高算法负载平衡能力,最后在上述分析基础上提出POTE Min min(Priority and Overlap Transmission and Execution Min min)调度算法。     

Minimizing Total Completion Time Subject to Job Release Dates and Preemption Penalties

Extensive research has been devoted to preemptive scheduling. However, little attention has been paid to problems where a certain time penalty must be incurred if preemption is allowed. In this paper, we consider the single-machine scheduling problem of minimizing the total completion time subject to job release dates and preemption penalties, where each time a job is started, whether initially or after being preempted, a job-independent setup must take place. The problem is proved to be strongly NP-hard even if the setup time is one unit. We also study a natural extension of a greedy algorithm, which is optimal in the absence of preemption penalty. It is proved that the algorithm has a worst-case performance bound of 25/16, even when the maximum completion time, i.e., makespan, criterion is considered simultaneously.     

SMART: Speedup Job Completion Time by Scheduling Reduce Tasks

Journal of Computer Science and Technology - Distributed computing systems have been widely used as the amount of data grows exponentially in the era of information explosion. Job completion time...     

Multipurpose批处理过程短期调度的滚动时域方法*

提出了一种利用滚动时域方法进行Ｍｕｌｔｉｐｕｒｐｏｓｅ批处理过程短期调度的方法，这种方法不仅可以大大缩短计算时间，而且可以考虑在生产过程中发生的动态变化，仿真计算结果证明了本方法有的效和实用性。     

Minimizing Mean Completion Time in a Batch Processing System

We consider batch processing jobs to minimize the mean completion time. A batch processing machine can handle up to $B$ jobs simultaneously. Each job is represented by an arrival time and a processing time. Jobs processed in a batch have the same completion time, i.e., their common starting time plus the processing time of their longest job. For batch processing, non-preemptive scheduling is usually required and we discuss this case. The batch processing problem reduces to the ordinary uniprocessor system scheduling problem if $B=1$. We focus on the other extreme case $B=+\infty$. Even for this seemingly simple extreme case, we are able to show that the problem is NP-hard for the weighted version. In addition, we establish a polynomial time algorithm for a special case when there are only a constant number of job processing times. Finally, we give a polynomial time approximation scheme for the general case.     

An Experimental Study of Algorithms for Weighted Completion Time Scheduling

We consider the total weighted completion time scheduling problem for parallel identical machines and precedence constraints, P| prec|\sum w _i C _i . This important and broad class of problems is known to be NP-hard, even for restricted special cases, and the best known approximation algorithms have worst-case performance that is far from optimal. However, little is known about the experimental behavior of algorithms for the general problem. This paper represents the first attempt to describe and evaluate comprehensively a range of weighted completion time scheduling algorithms. We first describe a family of combinatorial scheduling algorithms that optimally solve the single-machine problem, and show that they can be used to achieve good performance for the multiple-machine problem. These algorithms are efficient and find schedules that are on average within 1.5\percent of optimal over a large synthetic benchmark consisting of trees, chains, and instances with no precedence constraints. We then present several ways to create feasible schedules from nonintegral solutions to a new linear programming relaxation for the multiple-machine problem. The best of these linear programming-based approaches finds schedules that are within 0.2\percent of optimal over our benchmark. Finally, we describe how the scheduling phase in profile-based program compilation can be expressed as a weighted completion time scheduling problem and apply our algorithms to a set of instances extracted from the SPECint95 compiler benchmark. For these instances with arbitrary precedence constraints, the best linear programming-based approach finds optimal solutions in 78\percent of cases. Our results demonstrate that careful experimentation can help lead the way to high quality algorithms, even for difficult optimization problems. Received October 30, 1998; revised March 28, 2001.     

求解考虑机器调整时间的并行机分批优化调度问题

基于目前车间调度问题是以单个或整批进行生产加工的并行机调度模型已不再符合实际工况下的车间生产。提出以最小化最大完工时间为优化目标,对遗传差分进化混合算法,灰狼差分进化混合算法进行了比较。为提高加工工件进行分批及分批之后子批的分配与排序效率,该问题是对不同规模的经典并行机调度问题进行求解并展示两种算法的求解,证明了灰狼差分进化混合算法在寻优性能上优于遗传差分进化混合算法,不仅具有更好的解的稳定性,而且具有更高的寻优精度。     

任务具有链约束的平行机调度问题

研究任务间具有链约束的平行机调度问题,目标是在满足任务间链约束的条件下任务的总完工时间最小,这类问题是NP-难的.通过对问题的分析,对于一般情况给出了最优解的必要条件,对于特殊情况给出了问题的最优解算法.     

基于动态规划的分批排序算法

研究了在给定截止期限（deadline）下的单机分批（batch）排序问题,目标函数是最大提前完工时间。由于工件不能延迟,因此先讨论了问题可行解的存在。当问题有可行解时,证明了工件按最早截止期限（Earliest Deadline,ED）规则的排序是一个最优排序,接着给出一个时间复杂度为O（n³）的动态规划算法来获得最优分批。     

化工批处理过程调度

阐述了化工批处理过程调度问题的基本框架，综述了近年来这一领域取得的进展和存在的问题，并讨论今后的发展方向。