一类两阶段杂交流水作业的近似算法

讨论了一类两台机流水作业要求最后完工工件完工时间最早的排序问题.问题中每个工件包含两个加工任务:第1个任务可以在任何一台机器上加工,第2个任务只能在第1个任务完成后在第2台机器上加工.如果要求在加工同一个工件的两个任务时,两个任务之间不能有停顿,则称其为不可等待的模型,记作NSHFS.如果第2个任务可以在第1个任务完成后的任意时间加工,则称其为允许等待的模型,记作SHFS.对于SHFS模型,在魏麒和何勇工作的基础上给出了一种改进的最坏情况界为8/5的多项式时间近似算法.对于NSHFS模型,首先证明它是NP-难的,并且给出了一种最坏情况界为5/3的多项式时间近似算法.     

用户QOS及系统指标指导的计算网格任务调度

针对网格环境中的动态性特点,特别是用户服务质量（QoS）需求的动态变化性,通过定义任务的效益函数来评估任务的多维QoS需求。同时为了兼顾任务完成时间、负载平衡等系统指标,引入系统效益的概念,给出负载平衡度的定义用来指导调度及评价调度性能。针对一组具有QoS需求的相互独立的计算任务提出一种用户QoS及系统指标指导的计算网格任务调度算法——UQSI。模拟实验结果显示,该算法能较好地满足用户的多维QoS需求,更加适合开放复杂的网格环境。     

求解置换流水车间调度问题的混合鸟群算法

针对置换流水车间调度问题（PFSP）,提出了一种混合鸟群算法（HBSA）以更加有效地最小化最大完工时间。首先,为了改善初始种群的质量和多样性,结合一种基于NEH（Nawaz-Enscore-Ham）的启发式算法和混沌映射提出了一种新的种群初始化方法;其次,为了使算法能够处理离散的调度问题,采用最大排序值（LRV）规则将连续的位置值转换为离散的工件排序;最后,为了强化算法对解空间的探索能力,借鉴变邻域搜索（VNS）和迭代贪婪（IG）算法的思想针对个体最佳工件排序和种群最佳工件排序分别提出了局部搜索方法。针对广泛使用的Rec标准测试集进行了仿真测试,并与目前有效的元启发式算法——刘等提出的混合差分进化算法（L-HDE）、混合共生生物搜索算法（HSOS）、离散狼群算法（DWPA）、多班级教学优化算法（MCTLBO）相比较,结果表明,HBSA取得的最佳相对误差（BRE）、平均相对误差（ARE）的平均值比上述四种算法至少下降了73.3%、76.8%,从而证明HBSA具有更强的寻优能力和更好的稳定性。尤其是针对测试算例Rec25和Rec27,仅HBSA的求解结果达到了目前已知最优解,进一步证明了其优越性。     

求解混合流水车间调度问题的离散布谷鸟算法

为求解混合流水车间调度问题,提出一种离散布谷鸟算法。针对常规解码方法难以获得最优解的缺点,提出一种改进的解码方法,基于工件数与并行机数,按概率随机分配机器;根据标准布谷鸟算法中莱维飞行和巢寄生行为两种位置更新策略的核心思想,提出基于位置交叉和个体距离的离散莱维飞行,设计基于最优插入和最优交换的巢寄生策略。最后算例对比实验结果显示,采用基于改进解码方法的离散布谷鸟算法求解所得结果的平均值最小,验证了改进解码方法能提高解的质量;实例测试所得结果均获得了当前最优解,验证了离散布谷鸟算法求解该类问题的优越性。     

基于动态关键路径的云工作流调度算法

为了提高资源行为动态异构的云环境中工作流任务的调度效率,提出了一种基于动态关键路径的工作流调度算法CWS-DCP。算法将工作流任务结构定义为有向无循环图DAG模型,改进了传统关键路径的一次性搜索模式,结合云资源可用性动态可变的特征,以动态自适应方式搜索关键路径,并确定关键任务。同时,在关键任务调度后,局部DAG的关键路径搜索根据资源可用性再次迭代更新,从而动态决策任务与资源间的调度方案。通过仿真实验,构建了三种不同类型的工作流结构作为测试数据源,并与其他六种同类型的启发式和元启发式算法进行了性能比较。实验结果表明,在资源可用性动态改变和工作流规模不断增大的情况下,CWS-DCP算法在多数工作流结构中均能得到执行跨度更好的调度方案和更少的调度开销。     

Improving the migrating birds optimization metaheuristic for the permutation flow shop with sequence-dependent set-up times

This paper addresses the problem of scheduling a set of independent jobs with set-up times on a set of machines in a permutation flow shop environment. A metaheuristic known as the Migrating Birds Optimization (MBO) is adapted for the minimization of the makespan. Two versions of the algorithm are presented. The first is a basic MBO and the second introduces additional features. An extensive computational study is conducted to analyse the efficiency of the two methods on a benchmark of instances that can be found in Sistemas de Optimizacion Aplicada (http://soa.iti.es/problem-instances). The second version outperforms by far the first one. Moreover, the results that are produced by the latter show that it is suitable for solving real-world scheduling problems.     

A branch and bound algorithm for scheduling unit size jobs on parallel batching machines to minimize makespan

In this paper, we present a branch and bound algorithm for the parallel batch scheduling of jobs having different processing times, release dates and unit sizes. There are identical machines with a fixed capacity and the number of jobs in a batch cannot exceed the machine capacity. All batched jobs are processed together and the processing time of a batch is given by the greatest processing time of jobs in that batch. We compare our method to a mixed integer program as well as a method from the literature that is capable of optimally solving instances with a single machine. Computational experiments show that our method is much more efficient than the other two methods in terms of solution time for finding the optimal solution.     

Modelling and solving algorithm for two-stage scheduling of construction component manufacturing with machining and welding process

This paper focuses on a two-stage machining and welding scheduling problem based on an investigation at a structural metal manufacturing plant, aiming to minimise the total makespan. Several parts processed at Stage one according to classical job-shop scheduling are grouped into a single construction component at the second welding stage. Fabrication of the construction component cannot begin until all comprising parts have been completed at Stage one. This paper establishes a novel mathematic model to minimise the total makespan by mainly considering the dominance relationship between the construction component and the corresponding parts. In order to solve this two-stage problem, we propose an improved harmony search algorithm. A local search method is applied to the best vector at each iteration, so that a more optimal vector can be subsequently realised. The average value, minimum value, relative percentage deviation and standard deviation are discussed in the experimental section, and the proposed local best harmony search algorithm outperforms the genetic algorithm, immune algorithm and harmony search algorithm without local search. Moreover, six optimal solutions are given as Gantt charts, which vividly illustrate that the mathematical model established in this paper can facilitate the development of a better scheduling scheme.     

A competitive memetic algorithm for the distributed two-stage assembly flow-shop scheduling problem

This article addresses the distributed two-stage assembly flow-shop scheduling problem (DTSAFSP) with makespan minimisation criterion. A mixed integer linear programming model is presented, and a competitive memetic algorithm (CMA) is proposed. When designing the CMA, a simple encoding scheme is proposed to represent the factory assignment and the job processing sequence; and a ring-based neighbourhood structure is designed for competition and information sharing. Moreover, some knowledge-based local search operators are developed to enhance the exploitation ability. The influence of parameter setting on the CMA is investigated using the analysis of variance method. Extensive computational tests and comparisons are carried out, which demonstrate the effectiveness of the proposed CMA in solving the DTSAFSP.     

Minimizing makespan in a no-wait flowshop with two batch processing machines using estimation of distribution algorithm

This paper studies the problem of minimising makespan in a no-wait flowshop with two batch processing machines (comprised of a parallel batch processing machine and a serial batch processing machine), non-identical job sizes and unequal ready times. We propose a population-based evolutionary method named estimation of distribution algorithm (EDA). Firstly, the individuals in the population are coded into job sequences. Then, a probabilistic model is built to generate new population and an incremental learning method is developed to update the probabilistic model. Thirdly, the best-fit heuristic is used to group jobs into batches and a least idle/waiting time approach is proposed to sequence the batches on batch processing machines. In addition, some problem-dependent local search heuristics are incorporated into the EDA to further improve the searching quality. Computational simulation and comparisons with some existing algorithms demonstrate the effectiveness and robustness of the proposed algorithm. Furthermore, the effectiveness of embedding the local search method in the EDA is also evaluated.