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

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

解非等同并行多机调度问题的并行遗传算法

针对最小化完工时间的非等同并行多机调度一类问题，提出了一种混合遗传算法。该算法根据问题的特点，采用一种自然编码方案，此编码与调度方案一一对应，并对初始种群、交叉和变异等方法进行了研究。在鉴于遗传算法自然的并行性特点的基础上，实现了主从式控制网络模式下并行混合遗传算法。计算结果表明，并行混合遗传算法是有效的，优于启发式算法和遗传算法，有着较高的并行性，能适用于大规模非等同并行多机调度问题。     

解决并行多机提前/拖后调度问题的混合遗传算法方法

研究了带有公共交货期的并行多机提前/拖后调度问题.提出了一种混合遗传算法 方法,以便于确定公共交货期和每台机器上加工的任务代号及其加工顺序,即找到一个最优 公共交货期和最优调度,使加工完所有任务后交货期安排的成本、提前交货成本和拖后交货 成本的总和最小.数值计算结果表明了该混合遗传算法优于启发式算法,并能适用于较大规 模并行多机提前/拖后调度问题.算法计算量小,鲁棒性强.     

一种新的遗传算法在并行机调度问题中的应用

针对相同交货期窗口非等同并行机提前/拖后调度问题,设计了一个基于向量组编码的遗传算法.此算法的编码方法简单,能有效地反映实际调度方案,收敛速度快.为适应调度实时性和解大型此类问题的需要,基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行遗传算法.仿真结果表明,此算法是有效的,优于普通的遗传算法,具有较高的并行性.     

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

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

基于递阶遗传算法的并行多机调度优化

针对最小化完工时间的等同和非等同并行多机调度一类问题，提出了一种递阶遗传算法。该算法根据问题的特点，采用一种递阶编码方案，此编码与调度方案一一对应。用递阶遗传算法优化并行多机调度不需设计专门的遗传算子，操作简单。计算结果表明，递阶遗传算法是有效的，能适用于大规模等同和非等同并行多机调度问题。     

解特殊工艺约束拖后调度问题的并行遗传算法

非等同拖后调度问题作为家纺企业的车间调度问题重要组成部分,有着独特的特点,一方面生产设备非等同,另一方面受特殊工艺的约束。针对该问题的特点,设计了一个基于向量编码的遗传算法。此算法编码方法简单,能有效地反映实际调度方案,并能保证满足约束条件,收敛速度快。同时为更好地适应调度实时性和解大型企业此类问题的需要,在基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行遗传算法。仿真结果表明,此算法是有效的,优于普通的遗传算法,具有较高的并行性。     

特殊工艺约束下最小完工时间调度问题的新并行遗传算法

针对在特殊工艺约束下非等同并行机最小完工时间调度问题,设计了一个基于向量组编码的新的遗传算法。此算法的编码方法简单,能有效地反映实际调度方案,并能保证交叉和变异后染色体满足约束条件,收敛速度快。同时为更好地适应调度实时性和解决大型企业此类问题的需要,在基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行遗传算法。仿真结果表明,此算法是有效的,优于普通的遗传算法,具有较高的并行性。     

基于AGA的最小加权完成时间并行机调度

针对最小化加权完工时间的等同和非等同并行多机调度问题,通过一种新的扩展顺序表达方式编码,采用自适应遗传算法来优化.此编码与调度方案一一对应,并且适于用多种交叉算子.计算结果表明,基于该编码方式的自适应遗传算法是有效的,能适用于大规模等同和非等同并行多机调度问题,且算法操作简单,收敛速度快.     

用并行遗传算法解决带约束并行多机调度问题

遗传算法是一种全局优化的数值计算方法。它存在自然并行性。本文提出一种解带约束并行多机调度问题的主从式控制网络并行遗传算法,并在PVM环境下实现。计算结果表明,并行遗传算法是有效的,且能适用于大规模并行多机调度问题。     

Genetic algorithms for the optimal common due date assignment and the optimal scheduling policy in parallel machine earliness/tardiness scheduling problems

Earliness/tardiness scheduling problems with undetermined common due date which have wide application background in textile industry, mechanical industry, electronic industry and so on, are very important in the research fields such as industry engineering and CIMS. In this paper, a kind of genetic algorithm based on sectional code for minimizing the total cost of assignment of due date, earliness and tardiness in this kind of scheduling problem is proposed to determine the optimal common due date and the optimal scheduling policy for determining the job number and their processing order on each machine. Also, simulated annealing mechanism and the iterative heuristic fine-tuning operator are introduced into the genetic algorithm so as to construct three kinds of hybrid genetic algorithms with good performance. Numerical computational results focusing on the identical parallel machine scheduling problem and the general parallel machine scheduling problem shows that these algorithms outperform heuristic procedures, and fit for larger scale parallel machine earliness/tardiness scheduling problem. Moreover, with practical application data from one of the largest cotton colored weaving enterprises in China, numerical computational results show that these genetic algorithms are effective and robust, and that especially the performance of the hybrid genetic algorithm based on simulated annealing and the iterative heuristic fine-tuning operator is the best among them.     

考虑能耗成本和拖期成本的非同等并行机调度

针对橡胶轮胎硫化车间能源消耗大,浪费严重的现象,提出一类考虑能耗成本与拖期成本的非等同并行机调度问题,建立基于硫化机正常运行、空闲、停机三种运行状态的能源消耗成本与拖期成本的调度模型。设计了基于优先调度规则的启发式算法、基于能耗优化的启发式算法、组合启发式算法用于模型求解,并通过仿真实验分析、比较了各种算法的有效性与适用环境。同时,仿真实验结果也表明本文提出的考虑能耗成本和拖期成本的非同等并行机调度问题具有一定的理论与实践意义。     

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.     

公共交货期窗口下提前/拖期问题的多机调度算法

提出了求公共交货期窗口下提前／拖期都有惩罚的单机零件排序问题最优解的新算法,建立了相应多机零件排序问题的数学模型。在证明关于单机问题最优排序和最优公共交货期性质的若干定理的基础上,给出了求解多机问题的一个启发式算法。数值例子表明,该算法有较为理想的优化效果和工程实用价值。     

Parallel machine earliness and tardiness scheduling with proportional weights

In this paper we study the problem of scheduling n jobs with a common due date and proportional early and tardy penalties on m identical parallel machines. We show that the problem is NP-hard and propose a dynamic programming algorithm to solve it. We also propose two heuristics to tackle the problem and analyze their worst-case error bounds.Scope and purposeScheduling problems to minimize the total weighted earliness and tardiness (WET) arise in Just-in-time manufacturing systems, where one of the objectives is to complete each job as close to its due date as possible. The earliness and tardiness weights of a job in WET tend to increase with the value of the job. Because processing time is often a good surrogate for the value of a job, it is reasonable to consider weights that are proportional to job processing times. In this paper we study the parallel identical machine WET problem with proportional weights. We propose both exact and approximation algorithms to tackle the problem.