置换流水车间调度问题的中心引力优化算法求解

目前求解置换流水车间调度问题的智能优化算法都是随机型优化方法,存在的一个问题是解的稳定性较差。针对该问题,本文给出一种确定型智能优化算法——中心引力优化算法的求解方法。为处理基本中心引力优化算法对初始解选择要求高的问题,利用低偏差序列生成初始解,提高初始解质量;利用加速度和位置迭代方程更新解的状态;利用两位置交换排序法进行局部搜索,提高算法的优化性能。采用置换流水车间调度问题标准测试算例进行数值实验,并和基本中心引力优化算法、NEH启发式算法、微粒群优化算法和萤火虫算法进行比较。结果表明该算法不仅具有更好的解的稳定性,而且具有更高的计算精度,为置换流水车间调度问题的求解提供了一种可行有效的方法。     

求解零等待流水车间调度问题的改进蝙蝠算法

针对零等待流水车间调度问题特性,设计了一种蝙蝠算法进行求解.算法模拟蝙蝠捕食搜索行为进行寻优,利用基于最小位置值规则的随机键编码方式来表示问题解,采用基于NEH方法的局部搜索策略和随机交换、插入、逆序操作的变邻域搜索策略来提高局部优化性能,进一步根据Metropolis概率准则接受劣解来避免早熟.通过典型算例对所提算法进行仿真测试并与粒子群算法和RAJ启发式算法进行对比,结果表明所设计算法求解零等待流水车间调度问题的有效性和优越性,是求解流水车间生产调度问题的一种有效工具.     

基于混沌量子算法和MAGTD的多目标FJSP求解策略

针对多目标环境下柔性作业车间的调度问题,以最小化最大完工时间和惩罚值为目标,建立调度问题的数学模型,提出了基于混沌理论的量子粒子群算法。针对实际生产交货期不确定的特点,在量子粒子群算法基础上,提出引入混沌机制建立初始群的方法;利用混沌机制的遍历性,提出混沌局部优化策略;为获取最优调度方案提出了引入多指标加权灰靶选择策略。通过典型基准算例和对比测试,验证了所提出的算法获得最满意调度方案的可行性和求解多目标柔性作业车间调度问题的有效性。     

求解柔性作业车间调度的动态群智能优化算法

针对柔性作业车间调度问题,提出一种新型两阶段动态混合群智能优化算法.算法初始阶段采用动态邻域的协同粒子群进行粗搜索,第二阶段提出了基于混沌算子的蜂群进行细搜索,既增强了种群多样性,又提高了算法搜索精度,实现了全局搜索与局部搜索能力的有效平衡.针对柔性作业车间调度问题特点,采用独特的编码方式和位置更新策略来避免不合法解的产生.最后将此算法在不同规模的实例上进行了仿真测试,并与最近提出的其他几种具有代表性的算法进行了比较,验证了算法的有效性和优越性.     

求解高维全局优化问题的改进飞蛾火焰优化算法

针对标准飞蛾火焰优化算法在求解高维全局优化问题时存在收敛速度慢、解精度低和易陷入局部最优等缺点,提出一种改进的飞蛾火焰优化算法(简记为IMFO).该算法首先引入动态惯性权重对飞蛾位置更新方程进行修改以平衡算法的勘探和开采能力.受差分进化算法启发,设计出一种新的随机差分变异策略,以帮助种群跳出局部最优.选取18个高维(100、500和1000维)全局优化问题进行数值测试,结果表明,在相同的适应度函数评价次数下,IMFO在收敛速度和求解精度指标上明显优于基本MFO算法和其他对比算法.     

改进的萤火虫算法求解具有学习退化效应的JSP问题

作业车间调度问题是典型的NP难题,在生产调度领域具有很高的研究价值.一种更为符合实际的作业车间调度问题是加工机器具有学习退化效应,它能够为生产者安排生产计划提供借鉴.为了可以更好的解决具有学习退化效应的作业车间调度问题,本文提出了改进的萤火虫算法(IFA),即在基本的萤火虫算法基础上增加了局部寻优的过程,并融合了布谷鸟算法中生物移动的莱维分布特点.通过MATLAB模拟分析,IFA能够更快速的收敛到JSP的最优解.最后,本文分析了不同学习率与退化效应因子组合对目标函数求解的影响.     

改进回溯搜索算法求解多目标柔性作业车间调度问题

随着绿色制造的到来，在调度问题中考虑能源消耗相关的目标变得至关重要，这已经成为了当下热点研究领域。因此，本文建立以最小化最大完工时间、机器总负荷和总能量消耗为目标的柔性作业车间调度数学模型。就回溯搜索算法的缺点提出改进，该算法通过结合改变个体搜索幅度因子对变异操作进行动态控制，防止种群迭代过程中陷入局部最优，然后通过结合个体引导与随机数扰乱提出一种新的交叉算子，提高后期寻优能力，防止了算法过早收敛。最后，运用基准算例对该算法的求解性进行了验证，并与文献中其他算法从求解精度、求解多样性、求解最优值等方面进行对比，结果表明该改进算法具有优越的求解性能。最后为该问题后续研究提供了三个可行方向：考虑更多约束条件、增加局部搜索算子和考虑实例分析。     

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

针对现实生产制造系统中存在的时间参数模糊化问题,采用梯形模糊数表征时间参数,给出了一种具有模糊加工时间与模糊批次间隔的,以最小化制造跨度为目标的差异作业平行机批调度问题模型。在问题求解方面,给出了一种基于粒子群优化和差异进化的混合优化算法,避免求解过程陷入局部最优,并通过改进的Batch First Fit算法获得优化的分批。仿真实验验证了该算法具有可行性和有效性。     

一种求解TSP问题的多策略改进蚁群算法

蚁群算法是一种求解复杂组合优化问题的启发式仿生进化算法,并是求解TSP问题行之有效的一种随机算法.但此算法仍存在求解精度低、易陷入局部最优及求解效率低的问题,针对该问题提出一种多策略改进蚁群算法.采用最近邻法影响初始信息素的分布,达到降低算法初期较短路径上信息素浓度的目的,并在转移规则变异调整的基础上,结合路径的均值交叉进化策略,增强算法探索全局解空间和避免陷入局部最优的能力.然后,结合迭代和精英策略对信息素更新机制进行改进,进一步提高化算法的求解性能及求解效率,最后,对从TSPLIB数据库选出的8个实例进行求解并与其他算法进行对比,实验结果表明,改进算法在求解旅行商问题时的高效性,且具有较高的运算性能.     

具有模糊行程的城市物流动态费用多车型车辆调度问题研究

针对城市物流配送中广泛存在的多车型问题,以及由于交通路况等因素导致的配送行程模糊化现象,给出了一种基于梯形模糊数的,以最小化行程费用为目标的具有模糊行程的动态费用多车型车辆调度问题模型.在问题求解方面,针对基本粒子群算法容易陷入局部最优的情况,引入混沌局部搜索策略,给出了一种基于混沌优化技术的混合粒子群算法.仿真实验表明,该算法具有可行性和有效性.     

Flow shop scheduling jobs with position-dependent processing times

The paper is devoted to some flow shop scheduling problems, where job processing times are defined by functions dependent on their positions in the schedule. An example is constructed to show that the classical Johnson's rule is not the optimal solution for two different models of the two-machine flow shop scheduling to minimize makespan. In order to solve the makespan minimization problem in the two-machine flow shop scheduling, we suggest Johnson's rule as a heuristic algorithm, for which the worst-case bound is calculated. We find polynomial time solutions to some special cases of the considered problems for the following optimization criteria: the weighted sum of completion times and maximum lateness. Some furthermore extensions of the problems are also shown.     

基于遗传算法的多目标柔性工作车间调度问题求解

本文针对柔性工作车间调度问题给出了一个有意义的综合目标尽可能缩短制造周期的同时尽可能的减少机器负荷。由于传统遗传算法在多目标柔性工作车间调度问题上的局限性，我们提出了一种改进遗传算法：首先，我们给出了针对综合目标的工序调度算法获得初始集合；接着，针对柔性工作车间调度问题的特点，我们在常用的基于工序顺序的编码方法上融入了基于机器分配的编码方法，并据此设计了相应的交叉变异操作；最后借鉴了物种进化现象中的环境迁移思想设计了解决多目标优化问题的迁移操作。实验结果表明，改进的遗传算法在多目标柔性工作车间调度问题的解决上要优于传统遗传算法。     

An Ant Colony Optimization Algorithm for Shop Scheduling Problems

We deal with the application of ant colony optimization to group shop scheduling, which is a general shop scheduling problem that includes, among others, the open shop scheduling problem and the job shop scheduling problem as special cases. The contributions of this paper are twofold. First, we propose a neighborhood structure for this problem by extending the well-known neighborhood structure derived by Nowicki and Smutnicki for the job shop scheduling problem. Then, we develop an ant colony optimization approach, which uses a strong non-delay guidance for constructing solutions and which employs black-box local search procedures to improve the constructed solutions. We compare this algorithm to an adaptation of the tabu search by Nowicki and Smutnicki to group shop scheduling. Despite its general nature, our algorithm works particularly well when applied to open shop scheduling instances, where it improves the best known solutions for 15 of the 28 tested instances. Moreover, our algorithm is the first competitive ant colony optimization approach for job shop scheduling instances.     

Multi-population interactive coevolutionary algorithm for flexible job shop scheduling problems

In this paper, it proposes a multi-population interactive coevolutionary algorithm for the flexible job shop scheduling problems. In the proposed algorithm, both the ant colony optimization and genetic algorithm with different configurations were applied to evolve each population independently. By the interaction, competition and sharing mechanism among populations, the computing resource is utilized more efficiently, and the quality of populations is improved effectively. The performance of our proposed approach was evaluated by a lot of benchmark instances taken from literature. The experimental results have shown that the proposed algorithm is a feasible and effective approach for the flexible job shop scheduling problem.     

Genetic algorithm-based subproblem solution procedures for a modified shifting bottleneck heuristic for complex job shops

In this paper, we consider a modified shifting bottleneck heuristic for complex job shops. The considered job shop environment contains parallel batching machines, machines with sequence-dependent setup times and reentrant process flows. Semiconductor wafer fabrication facilities (Wafer Fabs) are typical examples for manufacturing systems with these characteristics. Our primary performance measure is total weighted tardiness (TWT). The shifting bottleneck heuristic uses a disjunctive graph to decompose the overall scheduling into scheduling problems for single tool groups. The scheduling algorithms for these scheduling problems are called subproblem solution procedures (SSPs). In previous research, only subproblem solution procedures based on dispatching rules have been considered. In this paper, we are interested in how much we can gain in terms of TWT if we apply more sophisticated subproblem solution procedures like genetic algorithms for parallel machine scheduling. We conduct simulation experiments in a dynamic job shop environment in order to assess the performance of the suggested subproblem solution procedures. It turns out that using near to optimal subproblem solution procedures leads in many situations to improved results compared to dispatching-based subproblem solution procedures.     

An iterated greedy metaheuristic for the blocking job shop scheduling problem

In this paper we consider a job shop scheduling problem with blocking (BJSS) constraints. Blocking constraints model the absence of buffers (zero buffer), whereas in the traditional job shop scheduling model buffers have infinite capacity. There are two known variants of this problem, namely the blocking job shop scheduling with swap allowed (BWS) and the one with no swap allowed (BNS). This scheduling problem is receiving an increasing interest in the recent literature, and we propose an Iterated Greedy (IG) algorithm to solve both variants of the problem. IG is a metaheuristic based on the repetition of a destruction phase, which removes part of the solution, and a construction phase, in which a new solution is obtained by applying an underlying greedy algorithm starting from the partial solution. A comparison with recent published results shows that the iterated greedy algorithm outperforms other state-of-the-art algorithms on benchmark instances. Moreover it is conceptually easy to implement and has a broad applicability to other constrained scheduling problems.     

基于启发式Q学习的汽车涂装车间作业排序优化

针对汽车涂装车间中的作业优化排序问题,提出一种基于启发式Q学习的优化算法。首先,建立包括满足总装车间生产顺序和最小化喷枪颜色切换次数的多目标整数规划模型。将涂装作业优化排序问题抽象为马尔可夫过程,建立基于启发式Q算法的求解方法。通过具体案例,对比分析了启发式Q学习、Q学习、遗传算法三种方案的优劣。结果表明:在大规模问题域中,启发式Q学习算法具有寻优效率更高、效果更好的优势。本研究为机器学习算法在汽车涂装作业优化排序问题的应用提出了新思路。     

Constraint Propagation and Problem Decomposition: A Preprocessing Procedure for the Job Shop Problem

In recent years, constraint propagation techniques have been shown to be highly effective for solving difficult scheduling problems. In this paper, we present an algorithm which combines constraint propagation with a problem decomposition approach in order to simplify the solution of the job shop scheduling problem. This is mainly guided by the observation that constraint propagation is more effective for small problem instances. Roughly speaking, the algorithm consists of deducing operation sequences that are likely to occur in an optimal solution of the job shop scheduling problem (JSP).The algorithm for which the name edge-guessing procedure has been chosen – since with respect to the job shop scheduling problem (JSP) the deduction of machine sequences is mainly equivalent to orienting edges in a disjunctive graph – can be applied in a preprocessing step, reducing the solution space, thus speeding up the overall solution process. In spite of the heuristic nature of edge-guessing, it still leads to near-optimal solutions. If combined with a heuristic algorithm, we will demonstrate that given the same amount of computation time, the additional application of edge-guessing leads to better solutions. This has been tested on a set of well-known JSP benchmark problem instances.     

A contribution to the stochastic flow shop scheduling problem

This paper deals with performance evaluation and scheduling problems in m machine stochastic flow shop with unlimited buffers. The processing time of each job on each machine is a random variable exponentially distributed with a known rate. We consider permutation flow shop. The objective is to find a job schedule which minimizes the expected makespan. A classification of works about stochastic flow shop with random processing times is first given. In order to solve the performance evaluation problem, we propose a recursive algorithm based on a Markov chain to compute the expected makespan and a discrete event simulation model to evaluate the expected makespan. The recursive algorithm is a generalization of a method proposed in the literature for the two machine flow shop problem to the m machine flow shop problem with unlimited buffers. In deterministic context, heuristics (like CDS [Management Science 16 (10) (1970) B630] and Rapid Access [Management Science 23 (11) (1977) 1174]) and metaheuristics (like simulated annealing) provide good results. We propose to adapt and to test this kind of methods for the stochastic scheduling problem. Combinations between heuristics or metaheuristics and the performance evaluation models are proposed. One of the objectives of this paper is to compare the methods together. Our methods are tested on problems from the OR-Library and give good results: for the two machine problems, we obtain the optimal solution and for the m machine problems, the methods are mutually validated.     

An Algorithm for the Job Shop Scheduling Problem based on Global Equilibrium Search Techniques

The job shop scheduling problem is considered, and an algorithm based on the global equilibrium search method is proposed for its solution. Computational experiments using well-known benchmark problems are presented. Several new upper bounds for these problems are obtained.Research partially supported by NSF and AirForce grants.