基于混合粒子群优化算法的置换流水车间调度问题研究

针对最大完工时间最小的置换流水车间调度问题,提出一种粒子群优化算法与变邻域搜索算法结合的混合粒子群优化（hybrid particle swarm optimization,HPSO）算法。在该混合算法中,采用NEH启发式算法进行种群初始化,以提高初始解质量。运用基于随机键的升序排列规则（ranked-or-der-value,ROV）,将连续PSO算法应用于离散置换流水车间调度问题中,提出了一种基于关键路径的变邻域搜索算法,以进一步提高算法的局部搜索能力,使算法在集中搜索和分散搜索之间达到合理的平衡。最后,运用提出的混合算法求解Taillard和Watson基准测试集,并将测试结果与一些代表算法进行比较,验证了该调度算法的有效性。     

基于激素调节机制改进型自适应粒子群算法在置换流水车间调度中的应用研究

研究以最小化最大流程时间为调度目标的离散型生产作业中的置换流水车间调度问题,将基于激素调节机制的改进型自适应粒子群算法应用到其中。在该算法中,粒子群算法的个体最优初始值不再是随机生成,而是由基于启发式信息的贪婪随机自适应算法得到的工件加工顺序转换而成,同时借鉴激素调节机制,引入激素调节因子,根据单个粒子周围的粒子的信息,对粒子的飞行方程进行改进,以提高搜索效率和搜索质量。对置换流水车间调度实例Rec系列基准问题进行测试,结果验证算法的有效性。     

基于混合遗传算法求解分布式流水车间逆调度问题

分布式调度是智能制造的新模式,急需新的调度方法来应对动态多变的市场需求。针对分布式置换流水车间问题,采用逆调度方法优化,通过最小调整加工参数,使得尽可能保证原排序的情况下调度最优。以最小化调整加工时间为目标,建立流水车间逆调度数学模型,针对逆调度问题特征,在遗传算法的框架下提出一种混合遗传优化算法。首先,基于逆调度参数可调的特征,提出基于工序的小数机制双层编码方案,能够实现参数的调整,保证可能解;提出改进启发式方法和基于规则的方法相结合的混合初始化方法;其次,采用适合问题特征的交叉、变异操作执行搜索;为协调全局搜索与局部搜索能力,设计局部搜索策略和学习机制的双种群协同搜索策略。为验证算法性能,基于问题实例采用三种算法进行比较,并且进行统计分析,其结果表明所提算法能更有效求解分布式流水线逆调度问题。     

自适应小生境混合遗传算法在车间调度中的应用研究

针对传统启发式算法早熟,全局搜索能力差等缺点,提出了一种基于自适应小生境混合算法求解作业车间调度问题的新方法。引入了基于共享机制的小生境技术,通过调整种群的适用度值来维持种群的多样性和提高搜索探测能力,从而提高全局搜索能力。于此同时,采用了自适应遗传算子与精英保留策略相结合的算法,保证了算法收敛速度。最后,通过仿真实例说明了该方法的有效性。     

Job shop调度文化进化算法研究

作业车间调度优化问题属典型的NP-hard问题,其求解通常采用智能启发式算法,文化进化算法基于文化算法及文化进化思想,通过上层文化空间的经验知识指导下层个体进化搜索的方向及步长,通过模拟人类社会文化进化的机制实现文化空间的进化与更新,最后将算法应用到Jobshop问题的求解,用matlab编程仿真测试,结果表明此算法解决车间调度优化问题是可行的,而且其搜索性能优于一般GA算法及一种改进的微粒群算法。     

一种基于混合遗传算法的车间生产调度的研究

车间生产调度问题(Job-shop scheduling problem,JSSP)属于NP完全问题,现在多使用现代优化算法来解决此类问题.本文将模拟退火算法、禁忌搜索算法的思想融入到遗传算法中,提出了模拟退火-交叉机制和禁忌搜索-变异机制,形成了一种适用于解决车间调度方面问题的新的混合遗传算法.三种算法取长补短,使得遗传算法局部搜索能力差和易早熟的缺点得以改善.同时运用这种混合遗传算法对经典车间调度问题进行了仿真.     

作业车间类型多机器人制造单元调度算法

针对带多台机器人的作业车间类型机器人制造单元调度问题的特点,研究了以最小化最大完工时间为优化目标、将邻域搜索策略与启发式规则相结合的混合遗传算法,建立了作业车间类型多机器人制造单元调度问题的数学优化模型和析取图模型。基于析取图关键路径,采取移动机床块、交换机器人块、调整任务分配来构建搜索邻域;用启发式搬运工序插入法和启发式搬运任务分配法相结合的三层调度方法初始化种群;将基于邻域结构的局部搜索算法和基于三层调度的遗传算法相结合,有效实现问题的求解。通过基准算例测试表明,混合遗传算法有效并优于其他算法。     

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

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

考虑设备周期性维护的流水车间生产调度优化算法

针对流水线车间,在考虑周期预防性维护的基础上,以最小化最大完工时间为优化目标,分别建立了置换车间与非置换车间两种不同情形下的数学优化模型。设计了结合增量式进化策略、局域搜索机制、种群密度管理的混合遗传算法,对问题进行优化求解。提出了以NEH思想为基础的快速启发式算法,该算法结合了邻域搜索与基于解序列破坏重组的广度搜索机制。在不同问题规模下,混合遗传算法的解与CPLEX精确解的对比结果表明:混合遗传算法可有效求解此类问题,而所提出的启发式算法可在保证解的较优性的基础上大幅度提高运算速度。随着工件数量和维护频次的增加,非置换车间的柔性使得其表现相比置换车间更加优异。     

超启发式文化基因算法优化生产与预维修集成调度问题

鉴于传统车间调度通常认为机器始终处于可用状态而有悖于实际生产环境的不确定性,考虑机器使用过程中需要周期性的进行预防性维修的情况,以最大完工时间和预防性维修总成本为目标,建立了机器预防性维修和柔性作业车间调度的集成优化模型。针对该模型设计了年龄模型下的3种不同的集成策略,并开发了一种超启发式文化基因算法,算法采用两层结构,顶层采用文化基因算法的搜索机制,底层是全局搜索算子库和局部搜索算子库,采用基于概率的改进的自适应算子选择机制。实验表明,该算法可以有效求解生产调度与预维修集成优化问题。通过对比可知,同步集成策略表现最优。将役龄模型应用于同步集成策略中,进一步优化了同步集成调度策略,在保证机器可靠性的前提下降低了最大完成时间和预防性维修总成本。     

APPLYING PARTICLE SWARMOPTIM IZATION TO JOB-SHOP SCHEDULING PROBLEM

A new heuristic algorithm is proposed for the problem of finding the minimum makespan in the job-shop scheduling problem. The new algorithm is based on the principles of particle swarm optimization (PSO). PSO employs a collaborative population-based search, which is inspired by the social behavior of bird flocking. It combines local search (by self experience) and global search (by neighboring experience), possessing high search efficiency. Simulated annealing (SA) employs certain probability to avoid becoming trapped in a local optimum and the search process can be controlled by the cooling schedule. By reasonably combining these two different search algorithms, a general, fast and easily implemented hybrid optimization algorithm, named HPSO, is developed. The effectiveness and efficiency of the proposed PSO-based algorithm are demonstrated by applying it to some benchmark job-shop scheduling problems and comparing results with other algorithms in literature. Comparing results indicate that PSO-based a     

An effective hybrid particle swarm optimization for no-wait flow shop scheduling

The no-wait flow shop scheduling that requires jobs to be processed without interruption between consecutive machines is a typical NP-hard combinatorial optimization problem, and represents an important area in production scheduling. This paper proposes an effective hybrid algorithm based on particle swarm optimization (PSO) for no-wait flow shop scheduling with the criterion to minimize the maximum completion time (makespan). In the algorithm, a novel encoding scheme based on random key representation is developed, and an efficient population initialization, an effective local search based on the Nawaz-Enscore-Ham (NEH) heuristic, as well as a local search based on simulated annealing (SA) with an adaptive meta-Lamarckian learning strategy are proposed and incorporated into PSO. Simulation results based on well-known benchmarks and comparisons with some existing algorithms demonstrate the effectiveness of the proposed hybrid algorithm.     

A hybrid algorithm based on particle swarm optimization and simulated annealing for a periodic job shop scheduling problem

Generating schedules such that all operations are repeated every constant period of time is as important as generating schedules with minimum delays in all cases where a known discipline is desired or obligated by stakeholders. In this paper, a periodic job shop scheduling problem (PJSSP) based on the periodic event scheduling problem (PESP) is presented, which deviates from the cyclic scheduling. The PESP schedules a number of recurring events as such that each pair of event fulfills certain constraints during a given fixed time period. To solve such a hard PJSS problem, we propose a hybrid algorithm, namely PSO-SA, based on particle swarm optimization (PSO) and simulated annealing (SA) algorithms. To evaluate this proposed PSO-SA, we carry out some randomly constructed instances by which the related results are compared with the proposed SA and PSO algorithms as well as a branch-and-bound algorithm. In addition, we compare the results with a hybrid algorithm embedded with electromagnetic-like mechanism and SA. Moreover, three lower bounds (LBs) are studied, and the gap between the found LBs and the best found solutions are reported. The outcomes prove that the proposed hybrid algorithm is an efficient and effective tool to solve the PJSSP.     

Hybrid meta-heuristic algorithm for job shop scheduling with due date time window and release time

This study intends to solve the job shop scheduling problem with both due data time window and release time. The objective is to minimize the sum of earliness time and tardiness time in order to reduce the storage cost and enhance the customer satisfaction. A novel hybrid meta-heuristic which combines ant colony optimization (ACO) and particle swarm optimization (PSO), called ant colony–particle swarm optimization (ACPSO), is proposed to solve this problem. Computational results indicate that ACPSO performs better than ACO and PSO.     

多目标批量生产柔性作业车间优化调度

研究批量生产中以生产周期、最大提前/最大拖后时间、生产成本以及设备利用率指标(机床总负荷和机床最大负荷)为调度目标的柔性作业车间优化调度问题。提出批量生产优化调度策略,建立多目标优化调度模型,结合多种群粒子群搜索与遗传算法的优点提出具有倾向性粒子群搜索的多种群混合算法,以提高搜索效率和搜索质量。仿真结果表明,该模型及算法较目前国内外现有方法更为有效和合理。最后,从现实生产实际出发给出多目标批量生产柔性调度算例,结果可行,可对生产实践起到一定的指导作用。     

A hybrid particle swarm optimization algorithm for a no-wait flow shop scheduling problem with the total flow time

This paper proposes a particle swarm optimization (PSO) algorithm based on memetic algorithm (MA) that hybridizes with a local search method for solving a no-wait flow shop scheduling problem. The main objective is to minimize the total flow time. Within the framework of the proposed algorithm, a local version of PSO with a ring-shape topology structure is used as global search. In addition, a self-organized random immigrant's scheme is extended into our proposed algorithm in order to further enhance its exploration capacity for new peaks in search space. The experimental study over the moving peaks benchmark problem shows that the proposed PSO-based MA is robust. Finally, the analysis of the computational results and conclusion are given.     

MULTI-SHOP SCHEDULING PROBLEM

A new concept of multi-shop (M ) is put forward which contains all basic shops including open shop (O), job shop (J ), flow shop (F ) and hybrid flow shop (H ) so that these basic shop can be scheduled together. Several algorithms including ant colony optimization (ACO), most work remaining (MWR), least work remaining (LWR), longest processing time (LPT) and shortest processing time (SPT) are used for scheduling the M. Numerical experiments of the M adopting data of some car and reC series benchmark instances are tested. The results show that the ACO algorithm has better performance for scheduling the M than the other algorithms, if minimizing the makespan ( C m*ax) is taken as the objective function. As a comparison, the separate shops contained in the M are also scheduled by the ACO algorithm for the same objective function, when the completing time of the jobs in the previous shop is taken as the ready time of these jobs in the following shop. The results show that the M has the advantage of shortening the makespan upon separate shops.     

A simultaneous planning of production and scheduling operations in flexible flow shops: case study of tile industry

The aim of this paper is to study a simultaneous lot-sizing and scheduling in multi-product, multi-period flexible flow shop environments. A new mixed integer programming (MIP) model is proposed to formulate the problem. The objective function includes the total cost of production, inventory, and external supply. In this study, in case of not meeting the demand of customers, this demand should be met by foreign suppliers in higher price. Due to the high computational complexity of the studied problem, a rolling horizon heuristic (RHH) and particle swarm optimization algorithm (PSO) are implemented to solve the problem. These algorithms find a feasible and near-optimal from production planning and scheduling. Additionally, Taguchi method is conducted to calibrate the parameters of the PSO algorithm and select the optimal levels of the influential factors. The computational results show that the algorithms are capable of achieving results with good quality in a reasonable time and PSO has better objective values in comparison with RHH. Also, the real case study for tile industry with real features is applied. Sensitivity analysis is used to evaluate the performance of the model.     

A hybrid discrete particle swarm optimization algorithm for solving fuzzy job shop scheduling problem

In this paper, a hybrid algorithm combining particle swarm optimization (PSO) and tabu search (TS) is proposed to solve the job shop scheduling problem with fuzzy processing time. The object is to minimize the maximum fuzzy completion time, i.e., the fuzzy makespan. In the proposed algorithm, PSO performs the global search, i.e., the exploration phase, while TS conducts the local search, i.e., the exploitation process. The global best particle is used to direct other particles to optimal search space. Therefore, in the proposed algorithm, TS-based local search approach is applied to the global best particle to conduct find-grained exploitation. In order to share information among particles, one-point crossover operator is embedded in the hybrid algorithm. The proposed algorithm is tested on sets of the well-known benchmark instances. Through the analysis of experimental results, the highly effective performance of the proposed algorithm is shown against the best performing algorithms from the literature.     

A simulated annealing for hybrid flow shop scheduling with multiprocessor tasks to minimize makespan

This paper studies a hybrid flow shop scheduling problem (hybrid FSSP) with multiprocessor tasks, in which a set of independent jobs with distinct processor requirements and processing times must be processed in a k-stage flow shop to minimize the makespan criterion. This problem is known to be strongly nondeterministic polynomial time (NP)-hard, thus providing a challenging area for meta-heuristic approaches. This paper develops a simulated annealing (SA) algorithm in which three decode methods (list scheduling, permutation scheduling, and first-fit method) are used to obtain the objective function value for the problem. Additionally, a new neighborhood mechanism is combined with the proposed SA for generating neighbor solutions. The proposed SA is tested on two benchmark problems from the literature. The results show that the proposed SA is an efficient approach in solving hybrid FSSP with multiprocessor tasks, especially for large problems.