基于需求优先的多目标柔性车间调度研究

为满足按时提交客户货物的要求,需要优化企业的生产调度,现实的生产调度问题是传统车间调度问题的扩充,具有多目标、柔性等特性。针对柔性作业车间调度的需要,提出了在精益制造下的基于需求优先的多目标柔性车间调度算法。该算法以工件提前／拖期惩罚代价最小,调度最小生产周期为目标,基于规则的改进启发式调度,在调度过程中通过需求日期计算工件的优先级为每道工序分配合适的机器进行加工,可得到满意的较优解。与其他方法进行对比试验的结果表明,该算法在求解柔性作业车间调度问题是有效的。     

差异工件并行批调度问题中遗传算法研究

本文考虑了遗传算法在包含差异工件的并行批处理机调度中的应用问题.工件具有不同的尺寸和到达时间.首先基于问题假设提出了一个数学规划模型,并采用BF、ERT-LPT实现工件的分批排序调度.然后考虑到这是一个NP-Hard问题,设计了新的选择、交叉、变异操作并结合遗传算法进行求解.最后通过仿真实验对比,验证了算法的有效性.     

一种改进的求解约束函数优化问题的演化算法

带约束的函数优化是函数优化中最多,也是较难的问题.针对这个问题提出一种改进的算法,它是基于遗传算法的非参惩罚函数的函数优化.通过改进广义的目标函数,对不可行解恰当地进行惩罚,并引进柯西组合、柯西变异以及高斯变异,极大地提高了算法的全局搜索和局部搜索能力,克服传统遗传算法"爬山能力差"的弱点.     

基于演化策略算法的置换流水车间调度优化研究

采用演化策略算法求解置换流水车间调度问题,提出了一种基于工件次序的二维实数编码方法.设计了一种基于父代个体两点交叉互换的重组算子来生成子代个体,针对个体编码,采用局部基因随机重新生成的变异算子.计算结果说明,演化策略算法能够有效地对置换流水车间调度问题进行优化,其优化性能好于遗传算法和NEH启发式算法以及粒子群算法.     

蚁群优化自适应遗传算法物流车辆调度实现

研究了使用蚁群算法优化遗传算法解决物流车辆调度问题;针对遗传算法在求解车辆调度问题时容易出现早熟,导致求解质量不高的问题;首先,定义了车辆调度问题的数学模型,在此基础上提出了一种对遗传算法中的交叉和变异概率进行自适应调整的方法,通过自适应遗传算法获得最优解;为了实现对其进一步的优化,使用蚁群算法提出一种对遗传算法最优解的进行优化的算法,将从遗传算法获得的最优路径的适应度初始化蚁群算法的各客户点之间的信息素,从而得到了进一步优化的最优路径;仿真实验得到平均最小配送距离仅为40.72,时间为2.11,计算效率较高,且与标准遗传算法、自适应遗传算法和蚁群算法相比,文中方法在最小配送距离、迭代数以及时间都具有较大优越性。     

基于遗传算法的资源均衡优化研究

从多任务的资源优化问题出发,对利用遗传算法对资源受限的多任务调度问题及其资源均衡优化问题进行了研究.对多任务网络计划的资源均衡问题进行了讨论,重点将资源受限的多任务调度问题与资源均衡优化相结合进行均衡优化,提出了一种基于改进遗传算法的求解方法,很好地解决了多任务调度问题并使资源分布更为均衡.该方法在解决较大规模网络计划的多任务调度及资源均衡问题时,具有其它方法无法比拟的优势.     

周期性和事件驱动的JobShop滚动调度策略

为了适应加工的连续性及环境的变化，借用了预测控制中的滚动优化思想提出了周期性和事件驱动的滚动调度策略。调度算法将遗传算法和分派规则相结合，以此来处理与操作序列有关的工件安装时 间和工件到期时间约束的复杂调度问题。     

分布式估计算法在考虑差异工件的并行批处理机调度中的应用

论文考虑包含差异工件的并行批处理机调度问题，优化目标是最小化制造跨度.在不违背机器容量的限制下，所有工件需要被分成不同的批次，然后被安排在机器上进行加工.首先根据问题提出一个混合整数规划模型，并提出一个下界；采用FF-LPT规则实现对工件的分批和排序；然后提出基于4种更新机制的分布式估计算法（EDA）来对问题求解.最后通过实验对各类规模不同的算例进行仿真，并将结果和模拟退火算法（SA）、遗传算法（GA）作对比，验证了算法的有效性.     

基于Web服务的工作流执行优化方法探讨

工作流优化有多种不同的手段,按照优化操作的对象不同,可以分为结构优化和参数优化.资源优化是工作流参数优化领域的热点,优化资源数量可以最大化地改善工作流时间性能.优化算法主要涉及遗传算法、基于Petri网结构的并行优化和与扩展Petri网结合的遗传算法等.工作流验证目的是在过程设计时检验工作流的正确性,避免执行时出现异常.在工作流模型实际实施之前,探测其中可能存在的各种过程异常可以降低工作流运行时的停产、检查和修复的成本,具有重大的经济意义.车间作业调度问题是一类最具一般性的生产调度问题,采用这种新型的扩展Petri网对调度问题进行建模,结合遗传算法对该调度问题进行优化,最后得到了问题的最优解.这种基于扩展Petri网的遗传算法具有较高的通用性.     

基于Hadoop的车辆调度算法优化及应用

随着互联网技术的快速发展,各行各业所产生的信息数据也在以指数级的速度增长.传统的车辆调度算法已经不能够很好地解决车辆调度问题中出现的实时性,大规模等问题.因此,本文构建了一种基于Hadoop的动态车辆调度并行智能优化算法.该算法以传统遗传算法为基础,通过改善遗传算法全局优化能力弱和收敛于局部次优解的问题,并利用Hadoop平台的并行计算机制对传统遗传算法进行改进,使其能够有效应对大规模、快速响应的车辆调度.数值计算结果表明：基于Hadoop的车辆调度算法能够有效提升传统调度算法的优化性能,在处理大规模车辆调度问题时具有良好的加速比.     

复杂并行机调度问题基于分解的优化算法

针对纺织生产过程中广泛存在的带特殊工艺约束的大规模并行机调度问题，提出了一种基于分解的优化算法。首先将原调度问题分解为机台选择和工件排序两个子问题，然后针对机台选择子问题提出一种进化规划算法，并采用一种具有多项式时间复杂度的最优算法求解工件排序子问题，以得到问题特征信息（即每台机器对应拖期工件数的最小值），该问题特征信息用以指导进化规划算法的迭代过程。不同规模并行机调度问题的数值计算结果及实际制造企业应用效果表明，本文提出的算法是有效的。     

知识化制造环境下航空发动机装配线调度及自重构

航空发动机装配工序数量多、工序间装配约束复杂. 当产品需求变化时, 人工调整存在响应速度慢、装配效率低等问题. 以最小化产品完工成本、工序提前期惩罚成本及班组重构成本加权和为目标, 建立了航空发动机装配线调度和装配班组自重构优化模型. 提出一种新的基于工序局部最优排序的分解算法, 将调度问题分解为单个装配组上工序顺序优化问题. 设计了一种工序后向插入搜索策略. 最后提出装配线调度及自重构集成优化算法. 通过数值试验,验证了模型与算法的有效性.     

用GA 求解动态联盟中伙伴选择的多目标优化模型

描述了动态联盟中的伙伴选择问题，针对以活动网络形式组织的项目，建立伙伴选择的多目标优化模型，实现项目失败风险最小化和项目费用与拖期惩罚总额最小化，并利用带自适应移动线技术的遗传算法，求得问题的整个非劣解集合或近似集合。计算结果证明了算法的有效性和模型的实用性。     

公共交货期窗口下提前／拖期惩罚不同的单机调度问题

单机作业下有一系列等待加工的彼此独立的任务需要确定最优交货期及最优加工顺序，运用公共交货期（ＣＯＮ）的方法确定了最优公共交货期，并假设如果任务在交货期窗口内完成，则不受惩罚；否则，将导致提前或拖期惩罚，且惩罚值与该任务是提前完工还是拖期完工有关。三个定理及一个多项式时间算法确定了最优交货期和最优排序，一个数值例子解释了如何运用定理来找到最优解。     

变邻域遗传算法在车间物流调度中的应用

针对含有自动引导小车(Automated Guided Vehicle,AGV)的离散化车间物流调度问题,以最小化物流任务时间惩罚成本和最小化运载小车的总行驶距离为优化目标,构建离散化车间多目标物流调度优化模型,设计一种基于Pareto寻优的多目标混合变邻域搜索遗传算法(VNSGA-II).以遗传算法为基础,通过使用NSGA-II的Pareto分层和拥挤度计算方法评估种群优劣实现多目标优化,为了提高算法的寻优能力,避免算法陷入局部最优,通过添加保优记忆库对精英个体进行保护,并利用变邻域搜索算法在搜索过程中的局部寻优能力,针对本文模型特点,设计6个随机邻域结构,来达到算法求解最优值的目标.并提出了基于关键AGV小车的插入邻域和基于关键物流任务的交换邻域调整策略以进一步降低成本.最后,以某离散车间物流调度为实例,分别使用VNSGA-II、带精英策略的快速非支配排序遗传算法Ⅱ(Nondominated Sorting Genetic AlgorithmⅡ,NSGA-II)和强Pareto进化算法(Strong Pareto Evolutionary Algorithm 2,SPEA2)对问题进行求解,计算结果表明,VNSGA-II能得到更好的Pareto解集,验证了算法的有效性和可行性.     

基于遗传算法的退火精确罚函数非线性约束优化方法

提出了一种新的基于遗传算法求解非线性约束优化的方法，通过自适应的退火罚因子和不可微精确罚函数未处理的约束条件，可以使算法逐渐收敛于可行的极值点，仿真结果表明该方法有较刘的求解精度。     

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

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

Decomposition heuristics for minimizing earliness–tardiness on parallel burn-in ovens with a common due date

This paper considers a scheduling problem for parallel burn-in ovens in the semiconductor manufacturing industry. An oven is a batch processing machine with restricted capacity. The batch processing time is set by the longest processing time among those of all the jobs contained in the batch. All jobs are assumed to have the same due date. The objective is to minimize the sum of the absolute deviations of completion times from the due date (earliness–tardiness) of all jobs. We suggest three decomposition heuristics. The first heuristic applies the exact algorithm due to Emmons and Hall (for the nonbatching problem) in order to assign the jobs to separate early and tardy job sets for each of the parallel burn-in ovens. Then, we use job sequencing rules and dynamic programming in order to form batches for the early and tardy job sets and sequence them optimally. The second proposed heuristic is based on genetic algorithms. We use a genetic algorithm in order to assign jobs to each single burn-in oven. Then, after forming early and tardy job sets for each oven we apply again sequencing rules and dynamic programming techniques to the early and tardy jobs sets on each single machine in order to form batches. The third heuristic assigns jobs to the m early job sets and m tardy jobs sets in case of m burn-in ovens in parallel via a genetic algorithm and applies again dynamic programming and sequencing rules. We report on computational experiments based on generated test data and compare the results of the heuristics with known exact solution for small size test instances obtained from a branch and bound scheme.     

Scheduling n jobs on one machine to minimize the maximum tardiness with minimum number

The “one machine” scheduling problem is considered with the dual objective of minimizing the maximum tardiness with minimum number of tardy jobs. A simple procedure is introduced to obtain an optimal schedule with minimum “maximum tardiness” when the set of nontardy jobs is specified. A branch and bound algorithm is presented to obtain the optimal schedule that minimizes the maximum tardiness with minimum number of tardy jobs. A condition is also given to identify an initial set of early jobs. Several theorems are formulated and proved in order to justify the elimination of much branching.     

Video Packet Selection and Scheduling for Multipath Streaming

This paper addresses the problem of choosing the best streaming policy for distortion optimal multipath video delivery, under network bandwidth and playback delay constraints. The streaming policy consists in a joint selection of the network path and of the video packets to be transmitted, along with their sending time. A simple streaming model is introduced, which takes into account the video packet importance, and the dependencies between packets. A careful timing analysis allows to compute the quality perceived by the receiver for a constrained playback delay, as a function of the streaming policy. We derive an optimization problem based on a video abstraction model, under the assumption that the server knows, or can predict accurately the state of the network. A detailed analysis of constrained multipath streaming systems provides helpful insights to design an efficient branch and bound algorithm that finds the optimal streaming strategy. This solution allows to bound the performance of any scheduling strategy, but the complexity of the algorithm becomes rapidly intractable. We therefore propose a fast heuristic-based algorithm, built on load-balancing principles. It allows to reach close to optimal performance with a polynomial time complexity. The algorithm is then adapted to live streaming scenarios, where the server has only a partial knowledge of the packet stream, and the channel bandwidth. Extensive simulations show that the proposed algorithm only induces a negligible distortion penalty compared to the optimal strategy, even when the optimization horizon is limited, or the rate estimation is not perfect. Simulation results also demonstrate that the proposed scheduling solution performs better than common scheduling algorithms, and therefore represents a very efficient low-complexity multipath streaming algorithm, for both stored and live video services