Tight bounds for the identical parallel machine scheduling problem

We address the problem of minimizing makespan on identical parallel machines. We propose new lower bounding strategies and heuristics for this fundamental scheduling problem. The lower bounds are based on the so‐called lifting procedure. In addition, two optimization‐based heuristics are proposed. These heuristics require iteratively solving a subset‐sum problem. We present the results of computational experiments that provide strong evidence that the new proposed lower and upper bounds consistently outperform the best bounds from the literature.     

A genetic algorithm application using fuzzy processing times in non-identical parallel machine scheduling problem

There are many scheduling problems which are NP-hard in the literature. Several heuristics and dispatching rules are proposed to solve such hard combinatorial optimization problems. Genetic algorithms (GA) have shown great advantages in solving the combinatorial optimization problems in view of its characteristic that has high efficiency and that is fit for practical application [1]. Two different scale numerical examples demonstrate the genetic algorithm proposed is efficient and fit for larger scale identical parallel machine scheduling problem for minimizing the makespan. But, even though it is a common problem in the industry, only a small number of studies deal with non-identical parallel machines. In this article, a kind of genetic algorithm based on machine code for minimizing the processing times in non-identical machine scheduling problem is presented. Also triangular fuzzy processing times are used in order to adapt the GA to non-identical parallel machine scheduling problem in the paper. Fuzzy systems are excellent tools for representing heuristic, commonsense rules. That is why we try to use fuzzy systems in this study.     

基于NSGA2算法的并行机多目标调度问题研究

针对并行机多目标调度问题,以完工时间和总延迟时间最小为目标函数建立了数学模型,从而将具有解决复杂组合优化问题的非劣排序遗传算法NSGA2应用于求解多目标并行机调度问题。文中详细描述了用NSGA2算法求解并行机调度问题的步骤,并通过Matlab仿真,表明YhqNSGA2算法求解多目标并行机调度问题的可行性和有效性。     

Hybrid tabu search and a truncated branch-and-bound for the unrelated parallel machine scheduling problem

We consider the problem of scheduling a number of jobs on a number of unrelated parallel machines in order to minimize the makespan. We develop three heuristic approaches, i.e., a genetic algorithm, a tabu search algorithm and a hybridization of these heuristics with a truncated branch-and-bound procedure. This hybridization is made in order to accelerate the search process to near-optimal solutions. The branch-and-bound procedure will check whether the solutions obtained by the meta-heuristics can be scheduled within a tight upper bound. We compare the performances of these heuristics on a standard dataset available in the literature. Moreover, the influence of the different heuristic parameters is examined as well. The computational experiments reveal that the hybrid heuristics are able to compete with the best known results from the literature.     

并行任务图的优化调度算法

科学与工程计算中的很多复杂应用问题需要使用科学工作流技术,超算领域中的科学工作流常以并行任务图建模,并行任务图的有效调度对应用的高效执行有重要意义。给出了资源限制条件下并行任务图的调度模型;针对Fork-Join类并行任务图给出了若干最优化调度结论;针对一般并行任务图提出了一种新的调度算法,该算法考虑了数据通信开销对资源分配和调度性能的影响,并对已有的CPA算法在特定情况下进行了改进。通过实验与常用的CPR和CPA算法做比较,验证了提出的新算法能够获得很好的调度效果。本文提出的调度算法和得到的最优调度结论对工作流应用系统的高性能调度功能开发具有借鉴意义。     

解并行机模糊调度问题的自适应遗传算法

针对家纺企业车间调度的实际情况,建立了一种产品优先级约束的模糊车间调度模型。在模型中,完工时间和交货期都是模糊的,交货期平均满意度最大为调度目标。基于此模型,提出了一种自适应的遗传算法,该算法通过比例选择及局部搜索保证种群的优良特性,并通过自动调节变异率和交叉率的方式保证种群的多样性,有效跳出局部收敛。仿真结果表明,自适应遗传算法能有效求解,并优于免疫遗传算法。     

解优先级约束并行机调度问题的人工免疫算法

针对家纺企业车间调度的实际情况,建立了优先级特殊工艺约束下并行多机拖后调度模型,并提出一种新颖的人工免疫算法对其求解。该算法是依据生物的免疫机理,将目标函数作为抗原,将问题的解作为抗体,对抗体采用向量组编码的方式进行编码,通过克隆、变异及一种新颖的基于浓度的种群多样性更新选择方法,提高了种群多样性,并通过局部搜索改善了种群质量,加快了收敛速度。仿真结果表明,与遗传算法相比较,该算法能更快更准确地收敛到全局最优解。     

Size-reduction heuristics for the unrelated parallel machines scheduling problem

In this paper we study the unrelated parallel machines problem where n independent jobs must be assigned to one out of m parallel machines and the processing time of each job differs from machine to machine. We deal with the objective of the minimisation of the maximum completion time of the jobs, usually referred to as makespan or C_max. This is a type of assignment problem that has been frequently studied in the scientific literature due to its many potential applications. We propose a set of metaheuristics based on a size-reduction of the original assignment problem that produce solutions of very good quality in a short amount of time. The underlying idea is to consider only a few of the best possible machine assignments for the jobs and not all of them. The results are simple, yet powerful methods. We test the proposed algorithms with a large benchmark of instances and compare them with current state-of-the-art methods. In most cases, the proposed size-reduction algorithms produce results that are statistically proven to be better by a significant margin.     

并行机实时调度问题的LR&CG算法

研究了目标函数为最小化总加权完成时间的并行机实时调度问题.建立该问题混合整数规划模型,并提出融合拉格朗日松弛(LR)和列生成(CG)的 LR & CG 混合算法.该算法包含双重迭代,在内环以次梯度法作为下界求解器和列生成器,在外环通过求解限制主问题来获得影子价格以调节拉格朗日乘子.计算实验结果表明,在相同的计算时间内, LR & CG 能够比常规的 LR 算法获得更好的上界和下界,表明了前者具有更好的收敛性能.     

含换模时间的平行机调度问题研究

在工厂实际生产中,模具的换模时间在生产调度中不可忽略。为了更合理地研究平行机车间调度问题,本文将存在序依赖的换模时间考虑进调度模型之中,同时以最小完工时间和最小拖期时间为目标,在经典遗传算法的基础上,对算法选择算子以及交叉变异概率进行改进,避免早熟现象的发生。通过计算结果的比较,证明本文中调度模型更符合实际生产情况,改进后的算法能够得出更高质量的解,且求解效率更高。     

混合并行机调度问题的多目标优化模型及算法

针对生产工序的合并造成一种串并联共存的生产布局,研究了一种特殊的混合并行机调度问题,并考虑以最小化总流水时间和最小化总延迟工件数量为目标的多目标调度问题,建立了混合整数规划模型.针对模型特点,设计了一种改进的非支配排序遗传算法进行求解,采用基于启发式方法的初始种群生成方式以提高种群的质量和多样性,并引入一种局域搜索策略以改善求解算法所获得的非支配解的质量及分布性.通过对大量数值算例进行仿真实验,并与典型的多目标优化算法进行比较,结果表明所提出的模型和算法在收敛性、分布性及极端点质量方面均具有优势,能够较好的解决多目标混合并行机调度问题.     

A two-stage stochastic programming model for the parallel machine scheduling problem with machine capacity

This paper proposes a two-stage stochastic programming model for the parallel machine scheduling problem where the objective is to determine the machines' capacities that maximize the expected net profit of on-time jobs when the due dates are uncertain. The stochastic model decomposes the problem into two stages: The first (FS) determines the optimal capacities of the machines whereas the second (SS) computes an estimate of the expected profit of the on-time jobs for given machines' capacities. For a given sample of due dates, SS reduces to the deterministic parallel weighted number of on-time jobs problem which can be solved using the efficient branch and bound of M’Hallah and Bulfin [16]. FS is tackled using a sample average approximation (SAA) sampling approach which iteratively solves the problem for a number of random samples of due dates. SAA converges to the optimum in the expected sense as the sample size increases. In this implementation, SAA applies a ranking and selection procedure to obtain a good estimate of the expected profit with a reduced number of random samples. Extensive computational experiments show the efficacy of the stochastic model.     

Parallel machine scheduling with fuzzy processing times using a robust genetic algorithm and simulation

This paper addresses parallel machine scheduling problems with fuzzy processing times. A robust genetic algorithm (GA) approach embedded in a simulation model is proposed to minimize the maximum completion time (makespan). The results are compared with those obtained by using the “longest processing time” rule (LPT), which is known as the most appropriate dispatching rule for such problems. This application illustrates the need for efficient and effective heuristics to solve such fuzzy parallel machine scheduling problems (FPMSPs). The proposed GA approach yields good results quickly and several times in one run. Moreover, because it is a search algorithm, it can explore alternative schedules providing the same results. Thanks to the simulation model, several robustness tests are conducted using different random number sets, and the robustness of the proposed approach is demonstrated.     

特殊工艺约束并行多机双目标调度问题的研究

针对在特殊工艺约束下,非等同并行多机总完工时间最小和总拖后惩罚最小双目标调度问题（BOSP）,设计了一个双目标调度模型,进而构造了一个基于向量组编码的遗传算法。此算法的编码方法简单,能有效地反映实际调度方案,收敛速度快。同时为了更好地适应调度实时性和解大型此类问题的需要,在基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行遗传算法。仿真结果表明,此算法是有效的,优于普通的遗传算法,具有较高的并行性,并能适用于解大型此类调度问题。     

解不同交货期并行机调度问题的并行遗传算法

为有效地解决不同交货期窗口下的非等同并行多机提前/拖后调度问题,设计了一种分段编码的混合遗传算法。此编码方式能反映工件的分配序列,并利用调度优先级规则和最好适应值规则相结合的启发式算法对其顺序进行了调整,加快了收敛速度。同时为了更好地适应调度实时性和解大规模此类问题的需要,基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行混合遗传算法。计算结果表明,此算法是有效的,优于遗传算法,有着较高的并行性,并能适用于大规模不同交货期窗口下非等同并行多机提前/拖后调度问题。     

一种求解同等并行机调度的混合量子衍生进化规划算法

针对带顺序相关建立时间的同等并行机调度问题的求解,提出一种新的混合量子衍生进化规划算法.该算法通过定义新的量子个体来表示调度问题中的工件排序,并定义了针对调度问题的量子旋转角,使个体向更好的解靠近.同时,针对并行机问题本身,改进了个体的编码方式和新的变异方法.为了验证算法的有效性和收敛性,采用不同规模的算例进行仿真实验.结果表明,即使在小种群情况下,算法所得解均优于基本进化规划求得的解.     

求解异构并行机调度问题的混合多目标教-学优化算法

以异构并行机调度问题为研究对象,考虑了一类以优化总加权完工时间和加权延误总和的调度问题。首先,基于问题描述构建了该问题的混合整数规划模型。其次,提出了混合多目标教-学优化算法。在算法设计中,结合问题的特点设计序列编码方法,并采用分解技术来实现多目标调度问题的求解。此外,该算法通过融合多种交叉算子来定义个体进化过程,并通过与变邻域搜索算法的混合来提升其优化效果。最后,给出了仿真实验与分析,测试结果验证了多目标教-学优化算法求解该调度问题的优越性。     

Ordinal scheduling problem and its asymptotically optimal algorithms on parallel machine system

Consider a resource allocation problem on the following system. A system consists of m identical parallel machines and is alive only when all the machines are alive. To keep a machine alive, it requires resources (material, fuel, etc.). Resources with various sizes arrive one by one and the goal is to keep the system alive as long as possible. The problem has applications in many areas such as sequencing of maintenance actions for modular gas turbine aircraft engines[1]. Using scheduling term…     

Ordinal algorithms for parallel machine scheduling with nonsimultaneous machine available times

This paper considers ordinal algorithms for parallel machine scheduling with nonsimultaneous machine available times. Two objects of minimizing the latest job completion time and minimizing the latest machine completion time are studied. For the first objective, we present the optimal algorithms for m = 2, 3, 4 machine cases. For m ≥ 5, we propose an algorithm with competitive ratio 2 - 1/(m - 1) while the lower bound is 5/3. For the second objective, the optimal algorithm is also given. Furthermore, for a special case, an algorithm with significantly improved competitive ratio is given.