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

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

基于自由搜索算法求解单机差异工件批调度问题*

采用自由搜索（free search,FS）算法对单机差异工件批调度问题的制作跨度进行优化。针对该问题的离散优化特征以及自由搜索算法的不足,将自由搜索算法与实数编码遗传算法相结合,在标准FS算法的基础上引入两种杂交算子和精英保留策略,提出混合自由搜索（hybrid free search,HFS）算法。仿真实验结果表明,该算法表现出良好的鲁棒性和收敛性,与标准FS、FFLPT以及BFLPT算法相比,HFS算法提高了寻优精度。     

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

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

转包商选择与单机批调度联合优化

面向多转包商的外包选择是当今制造企业面临的一大运营管理挑战.它与内部作业调度的一体化决策对企业降本增效至关重要.本文针对有多个转包商可供作业外包选择的单机批调度联合优化问题,在外包总成本和外包作业最晚交付期均受上限前提下建立以最小化外包总成本与内部批加工总成本之和为目标的0-1整数规划模型,并为该问题设计了改进型遗传算法和贪婪算法.以某陶瓷企业的外包与批调度联合决策场景为实例,对比分析了这两种算法的求解性能,发现改进型遗传算法在求解质量和时间上具有比较优势.在模型的灵敏度实验分析中发现,外包作业最晚交付期对作业运营总成本有显著影响,而作业外包总成本的给定上限值对作业运营总成本的影响不显著.     

动态自适应加权多态蚁群算法求解差异工件单机批调度问题*

针对差异工件的单机批调度问题,提出了动态自适应加权多态蚁群算法对最大完工时间进行优化,该算法引入了不同种类的蚁群,每种蚁群都有不同的信息素调控机制,并根据批调度问题对不同种类的蚁群的状态转移概率和信息素更新机制进行了改进,同时将局域搜索与全局搜索相结合,从而更符合蚁群的真实信息处理机制。对不同规模的算例进行了仿真,结果验证了该算法的有效性和可行性。     

模糊环境下的差异作业单机批调度优化问题的研究*

针对现实生产制造系统中存在的时间参数模糊化问题,本文用梯形模糊数表征时间参数,给出了一种具有模糊加工时间和模糊批次间隔的、以最小化制造跨度为目标的模糊差异作业单机批调度问题模型。在对模糊差异作业单机批调度问题进行有效求解方面,针对基本粒子群算法容易陷入局部最优的问题,本文给出了一种基于遗传操作的混合粒子群算法,利用遗传算法思想对粒子进行交叉、变异操作,增强了算法跳出局部最优的能力。仿真实验验证了该算法具有可行性和有效性。     

基于DNA进化算法求解工件尺寸不同的单机批调度问题

工件尺寸不同的批调度问题兼具古典调度和批调度的性质,单机环境下该问题的制造跨度为NP完全问题.本文提出一种改进的DNA进化算法对单机问题的制造跨度进行优化,引入分裂、水平选择、变异、垂直选择四种算子,对其中的垂直选择算子做了重新设计,采用概率选择机制对变异个体进行选择,避免进化过程陷入局部最优.在解码时,采用Batch First Fit算法对进化过程产生的解作分批处理.实验中对各类不同规模的算例均进行仿真,结果表明改进的DNA进化算法的有效性.     

考虑作业状态能耗的集装箱码头设备协调调度

绿色港口日渐成为港口发展的必然趋势,为了提高集装箱码头的服务水平及降低其能耗,综合分析了集装箱码头的装卸作业流程,考虑岸桥、场桥、集卡在不同作业状态下的能耗,且以总完工时间和总作业能耗最小为目标建立了多目标混合整数规划模型.使用MATLAB编码改进自适应遗传算法求解所建模型,并分别与CPLEX和原始遗传算法的求解结果作...     

遗传算法在公交调度中的应用

针对泰州市公交智能化建设方面存在的技术问题,提出将遗传算法(Genetic Algorithms,GA)应用到公交调度优化中。以公交公司和乘客费用最少、社会效益最大为目标函数建立公交调度优化的数学模型,并应用遗传算法实现对模型的求解,通过对模型设置不同的参数,利用Matlab模拟实验验证模型的合理性、科学性。实验证明,优化的调度模型可降低公交公司的运营成本,提高乘客的满意度,确保社会效益和经济效益得到最大满足。     

改进的遗传算法在作业调度中的应用

作业调度问题（JSP）是一类典型的NP-hard问题,遗传算法作为一种通用的优化算法在求解JSP中得到了广泛的应用。本文主要针对作业车间调度问题,基于改进的遗传算法 ,根据种群的进化状况,从而确定种群的适应度值,使之能够保持种群的多样化。     

考虑能耗与工时恶化作用下的并行机调度优化

在热处理加工环境中,工件温度随着其开工时刻的延误不断下降,为了能够正常加工不得不保温或重新加热.针对这一现象,本文考虑了能耗与工时恶化作用下的并行机调度问题,以最小化总拖期和能耗为目标构建了混合整数规划模型.由于问题的复杂性,提出了一种遗传变搜索算法,其通过遗传操作获得变邻域搜索操作的解集,而后使用变邻域结构进行寻优操作.算例测试表明：较之传统遗传算法以及数学规划器Gurobi的计算结果,所提出的算法可以有效减少综合能耗和拖期成本.     

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

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

一种基于混合遗传算法的车间调度算法

为了克服单独的遗传算法用于车间作业调度缺点,提出一种遗传算法与启发式算法结合的混合遗传算法,在运用该算法的过程中给出了适合的遗传操作和启发式规则的应用方法。结果表明：混合遗传算法优于两种单独的算法。     

Benefits and Drawbacks of Redundant Batch Requests

Most parallel computing platforms are controlled by batch schedulers that place requests for computation in a queue until access to compute nodes is granted. Queue waiting times are notoriously hard to predict, making it difficult for users not only to estimate when their applications may start, but also to pick among multiple batch-scheduled platforms the one that will produce the shortest turnaround time. As a result, an increasing number of users resort to “redundant requests”: several requests are simultaneously submitted to multiple batch schedulers on behalf of a single job; once one of these requests is granted access to compute nodes, the others are canceled. Using simulation as well as experiments with a production batch scheduler we evaluate the impact of redundant requests on (1) average job performance, (2) schedule fairness, (3) system load, and (4) system predictability. We find that some of the popularly held beliefs about the harmfulness of redundant batch requests are unfounded. We also find that the two most critical issues with redundant requests are the additional load on current middleware infrastructures and unfairness towards users who do not use redundant requests. Using our experimental results we quantify both impacts in terms of the number of users who use redundant requests and of the amount of request redundancy these users employ. This work was supported by the NSF under Award 0546688.