基于混合粒子群算法的汽车零件精冲车间调度研究

针对传统遗传算法在车间作业调度问题难以解决求解约束优化问题时存在难以同时兼顾求解质量和收敛效率这一问题,通过采用了基于工序编码的方式生成可行调度及借鉴遗传算法单点交叉方法,生成基于工件的交叉算子作为粒子的更新方式,将改进后的粒子群优化算法用于求解精冲零件车间调度问题,并在算法中通过利用局部搜索的方式提升粒子群中粒子收敛效率。通过对典型的调度测试问题进行模拟实验,证明了改进后的混合粒子群算法对于求解车间调度问题的适用性及具有不错的求解性能。     

并行机调度问题粒子群优化研究

采用粒子群算法优化并行机调度问题,提出了基于机器和粒子位置取整的粒子编码方法和基于工件和粒子位置次序的粒子编码方法,并给出了两种不同粒子编码方法所对应的粒子群算法的步骤.通过对两个并行机算例的计算说明,基于两种不同编码方法的粒子群算法都能有效地对并行机调度问题进行优化,其中,基于工件和粒子位置次序的粒子编码所对应粒子群算法的优化性能要好些.     

解决无等待流水线调度问题的新算法

提出了解决无等待流水线调度问题的3种新算法,即离散粒子群优化算法、离散差异进化算法和阈值接收算法。离散粒子群优化算法和离散差异进化算法采用了基于工件序列的编码方式和新的个体生成方法,从而使具有连续性质的粒子群优化算法和差异进化算法能直接用于求解调度问题。仿真试验表明了上述算法的有效性。     

置换流水车间调度粒子群优化与局部搜索方法研究

采用粒子群优化算法求解置换流水车间调度问题,提出了一种基于工件次序和粒子位置的二维粒子编码方法.为提高粒子群算法的优化性能,在描述了面向置换流水车间调度问题的粒子邻域结构后,提出了三种基于粒子邻域操作的局部搜索方法,分别是基于互换操作、基于插入操作和基于逆序操作的局部搜索方法.计算结果说明,粒子群算法的优化性能好于遗传算法和NEH启发式算法.三种局部搜索算法均能有效地提高粒子群算法的优化性能,采用基于互换操作局部搜索的粒子群算法的优化性能要好于其它两种局部搜索算法.     

求解无等待流水车间问题的若干算法

提出了解决无等待流水车间问题的离散粒子群优化、离散差异进化、变邻域搜索和阈值接收算法.在离散粒子群优化和离散差异进化中,采用基于工件排列的编码,设计了新的个体生成公式.同时研究了基于串行结构、嵌人结构和协同结构的12种混合算法.仿真计算表明,混合算法具有较高的优化性能.     

不确定环境下再制造加工车间生产调度优化方法

针对再制造加工车间工况兼具随机性与模糊性,采用模糊随机变量表示废旧件加工时间,以描述再制造加工车间工况的双重不确定性;在不确定理论的基础上,建立基于模糊随机机会约束的再制造加工车间生产调度问题模型,并提出求解该问题混合智能优化算法:基于Arena仿真平台应用模糊随机模拟技术产生输入和输出数据,利用粒子群优化算法训练径向基函数神经网络以逼近不确定函数,将训练好的神经网络嵌入至遗传算法中优化再制造加工车间生产调度问题;通过仿真实例验证该混合智能优化算法解决加工时间为模糊随机变量的不确定环境下再制造加工车间生产调度问题的有效性和合理性。     

解决JOB SHOP问题的粒子群优化算法

设计了2种解决Job shop问题的粒子群算法,即实数编码的粒子群调度算法和工序编码的粒子群调度算法。工序编码的粒子群调度算法更符合Job shop问题的特点,优化性能相对高。但粒子群调度算法容易陷入局部最优。为了提高优化性能,将粒子群算法和模拟退火算法结合,得到了粒子群-模拟退火混合调度算法。仿真结果表明了算法的有效性。     

知识化制造环境下模糊调度模型和算法

为解决实际生产中一些不精确调度知识的描述问题,通过引入模糊理论中的测度概念,建立了模糊调度模型和求解该模型的混合模糊遗传算法.首先,在变速并行机生产环境下,针对工件加工时间和交货期的不确定性,基于可能性测度和必然性测度的定义,提出了工件拖期可信度指标,用于衡量工件发生拖期的可能性;然后,基于工件拖期可信度指标,建立了以最小化工件平均拖期可信度为目标的混合整数规划模型,通过分析该调度模型,得到最优模糊调度的相关性质;最后,以上述工作为基础,给出一种混合模糊遗传算法的求解方法,并以某电机制造企业为例,对所提出的算法进行了有效性验证.     

基于模糊关联熵的高维多目标流水车间调度优化

针对现有优化方法在求解高维多目标问题上的弊端,将多目标解映射为模糊集,提出利用表征模糊集间关联相似程度的模糊关联熵方法解决多目标优化问题。建立基于模糊关联熵的多目标优化方法,以模糊关联熵系数的大小衡量Pareto解模糊集与理想解模糊集的相似程度,并以该系数作为粒子群优化算法适应度值引导算法进化,建立基于模糊关联熵的多目标粒子群优化算法。实验表明,基于模糊关联熵的粒子群优化算法可以有效解决高维多目标Flow Shop调度问题,算法在优化解和各性能指标上皆优于基于随机权重的粒子群优化算法,特别在求解较大规模问题时,基于此法的粒子群优化算法表现更佳。     

带多处理器混合流水车间调度问题的混合鱼群算法

针对带多处理器的混合流水车间调度问题(hybrid flow shop scheduling with multiprocessor task problems),以最小化所有工件的最大完成时间(makespan)为优化目标,提出一种融合了改进的人工鱼群算法和禁忌搜索算法的混合算法。首先改进人工鱼群算法相关行为及实验优选算法参数,提高了人工鱼群算法收敛速度和精度;然后结合人工鱼群算法收敛快和禁忌算法局部搜索能力强的特点,利用改进的人工鱼群算法进行全局搜索,获得较好的优化解域,再通过禁忌算法在优化解域内进行局部寻优,得到一个最终满意的优化解。基于180个标准算例,算法实验结果表明混合算法的优化性能明显优于禁忌算法和粒子群算法,并且很接近改进的遗传算法。     

GRASP to minimize makespan for a capacitated batch-processing machine

This paper presents a Greedy Randomized Adaptive Search Procedure (GRASP) to minimize the makespan of a capacitated batch-processing machine. Given a set of jobs and their processing times and sizes, the objective is to group these jobs into batches and schedule the batches on a single batch-processing machine such that the time taken to complete the last batch of jobs (or makespan) is minimized. The batch-processing machine can process a batch of jobs simultaneously as long as the total size of all the jobs in that batch does not exceed the machine capacity. The batch-processing time is equal to the longest processing time for a job in the batch. It has been shown that the problem under study is non-deterministic polynomial-time hard. Consequently, a GRASP approach was developed. The solution quality of GRASP was compared to other solution approaches such as simulated annealing, genetic algorithm, and a commercial solver through an experimental study. The study helps to conclude that GRASP outperforms other solution approaches, especially on larger problem instances.     

考虑不确定加工时间的工艺规划与调度集成问题研究

为使工艺规划与调度集成问题更加符合实际,将不确定加工时间考虑到工艺规划与调度集成问题中,并以三角模糊数表示加工时间,提出一种考虑模糊加工时间的工艺规划与调度集成问题。以最大模糊完工时间最小为目标,对该问题进行建模。提出一种多层编码结构的遗传算法,对该问题进行求解。最后,以实例验证了上述模型的正确性及算法的有效性。     

Lot streaming in a two-machine mixed shop

Most classical scheduling models overlook the fact that products are often produced in job lots and assume that job lots are indivisible single entities, although an entire job lot consists of many identical items. However, splitting an entire lot (process batch) into sublots (transfer batches) to be moved to downstream machines allows the overlapping of different operations on the same product while work needs to be completed on the upstream machine. This approach is known as lot streaming in scheduling theory. In this study, the lot streaming problem of multiple jobs in a two-machine mixed shop where there are two different job types as flow shop and open shop is addressed so as to minimize the makespan. The optimal solution method is developed for the mixed shop scheduling problem in which lot streaming can improve the makespan.     

Makespan minimization in a job shop with a BPM using simulated annealing

A scheduling problem commonly observed in the metal working industry has been studied in this research effort. A job shop equipped with one batch processing machine (BPM) and several unit-capacity machines has been considered. Given a set of jobs, their process routes, processing requirements, and size, the objective is to schedule the jobs such that the makespan is minimized. The BPM can process a batch of jobs as long as its capacity is not exceeded. The batch processing time is equal to the longest processing job in the batch. If no batches were to be formed, the scheduling problem under study reduces to the classical job shop problem with makespan objective, which is known to be nondeterministic polynomial time-hard. A network representation of the problem using disjunctive and conjunctive arcs, and a simulated annealing (SA) algorithm are proposed to solve the problem. The solution quality and run time of SA are compared with CPLEX, a commercial solver used to solve the mathematical formulation and with four dispatching rules. Experimental study clearly highlights the advantages, in terms of solution quality and run time, of using SA to solve large-scale problems.     

A particle swarm optimization algorithm for minimizing makespan of nonidentical parallel batch processing machines

This research is motivated by our interactions with an electronics manufacturer who assembles and tests printed circuit boards (PCBs) used in consumer products. Environmental stress screening (ESS) chambers are commonly used to test PCBs to detect early failures before they are used in the field. The chambers are capable of testing multiple PCBs simultaneously (i.e., batch processing machines). The minimum testing time of each PCB and their size are known. The objective is to group these PCBs into batches and schedule the batches formed on ESS chambers such that the makespan is minimized. The ESS chambers can process a batch of jobs as long as its capacity is not violated. Each ESS chamber is unique with respect to its capacity. The problem is NP-hard. Consequently, a particle swarm optimization (PSO) algorithm is proposed. The effectiveness of the PSO algorithm is evaluated by comparing its results to a random-key genetic algorithm and a commercial solver used to solve a mixed-integer linear program. A thorough experimental study conducted indicates that the PSO algorithm reports better quality solution in a short time on larger problem instances.     

面向绿色制造的一类模糊调度模型及其算法

绿色制造是一种综合考虑环境影响和资源效率的现代制造模式，由于其生产系统的复杂性和不确定性，使得工序的加工时间和生产成本等数据用模糊数表示更加符合生产实际。为优化调度过程中的产品质量、生产成本、资源消耗、环境污染和生产周期，建立了面向绿色制造的模糊调度模型。将多目标遗传算法与模糊优选技术相结合对该模型求解，并用案例验证了模型的实用性和算法的可行性。     

Minimizing makespan in a single-machine scheduling problem with a learning effect and fuzzy processing times

In scheduling problems with learning effects, most research assumes that processing times are deterministic. This paper studies a single-machine scheduling problem with a position-based learning effect and fuzzy processing times where the objective is to minimize the makespan. The position-based learning effect of a job is assumed to be a function of its position. The processing times are considered to be triangular fuzzy numbers. Two different polynomial-time algorithms are developed for the problem. The first solution methodology is based on the fuzzy chance-constrained programming, whereas the second is based on a method to rank fuzzy numbers. Computational experiments are then conducted in order to evaluate the performance of the algorithms.     

Minimizing makespan in a two-machine no-wait flow shop with batch processing machines

Given a set of jobs and two batch processing machines (BPMs) arranged in a flow shop environment, the objective is to batch the jobs and sequence the batches such that the makespan is minimized. The job sizes, ready times, and processing times on the two BPMs are known. The batch processing machines can process a batch of jobs as long as the total size of all the jobs assigned to a batch does not exceed its capacity. Once the jobs are batched, the processing time of the batch on the first machine is equal to the longest processing job in the batch; processing time of the batch on the second machine is equal to the sum of processing times of all the jobs in the batch. The batches cannot wait between two machines (i.e., no-wait). The problem under study is NP-hard. We propose a mathematical formulation and present a particle swarm optimization (PSO) algorithm. The solution quality and run time of PSO is compared with a commercial solver used to solve the mathematical formulation. Experimental study clearly highlights the advantages, in terms of solution quality and run time, of using PSO to solve large-scale problems.     

基于免疫算法的并行机间歇过程模糊生产调度

研究了一类具有顺序无关模糊产品切换时间和成本以及模糊单位加工时间和成本的并行机间歇过程调度问题,目的是确定每种产品在每个设备上处理的批次数目、批量以及批次顺序,优化目标为最小化总完成时间和最小化总生产成本。根据任意设备上同种产品的所有批次均顺序处理的性质,建立了问题的模糊运输模型。利用加权和方法将多目标函数转化为单目标函数,并使用基于积分值的方法对模糊数进行排序。提出了基于排列边集编码的免疫算法,通过求解不同规模的问题实例证明,免疫算法不仅能获得比遗传算法和免疫遗传算法更好的解,而且比免疫遗传算法更高效,同时具有良好的动态性能。     

Genetic algorithms for minimizing makespan in a flow shop with two capacitated batch processing machines

This paper considers a flow shop with two batch processing machines. The processing times of the job and their sizes are given. The batch processing machines can process multiple jobs simultaneously in a batch as long as the total size of all the jobs in a batch does not exceed its capacity. When the jobs are grouped into batches, the processing time of the batch is defined by the longest processing job in the batch. Batch processing machines are expensive and a bottleneck. Consequently, the objective is to minimize the makespan (or maximize the machine utilization). The scheduling problem under study is NP-hard, hence, a genetic algorithm (GA) is proposed. The effectiveness (in terms of solution quality and run time) of the GA approach is compared with a simulated annealing approach, a heuristic, and a commercial solver which was used to solve a mixed-integer formulation of the problem. Experimental study indicates that the GA approach outperforms the other approaches by reporting better solution.