Flexible job shop scheduling with tabu search algorithms

This paper presents a tabu search algorithm that solves the flexible job shop scheduling problem to minimize the makespan time. As a context for solving sequencing and scheduling problems, the flexible job shop model is highly complicated. Alternative operation sequences and sequence-dependent setups are two important factors that frequently appear in various manufacturing environments and in project scheduling. In this paper, we present a model for a flexible job shop scheduling problem while considering those factors simultaneously. The purpose of this paper is to minimize the makespan time and to find the best sequence of operations and the best choice of machine alternatives, simultaneously. The proposed tabu search algorithm is composed of two parts: a procedure that searches for the best sequence of job operations, and a procedure that finds the best choice of machine alternatives. Randomly generated test problems are used to evaluate the performance of the proposed algorithm. Results of the algorithm are compared with the optimal solution using a mathematical model solved by the traditional optimization technique (the branch and bound method). After modeling the scheduling problem, the model is verified and validated. Then the computational results are presented. Computational results indicate that the proposed algorithm can produce optimal solutions in a short computational time for small and medium sized problems. Moreover, it can be applied easily in real factory conditions and for large size problems. The proposed algorithm should thus be useful to both practitioners and researchers.     

Application of chance-constrained programming for stochastic group shop scheduling problem

In this paper, we study a group shop scheduling (GSS) problem subject to uncertain release dates and processing times. The GSS problem is a general formulation including the other shop scheduling problems such as the flow shop, the job shop, and the open shop scheduling problems. The objective is to find a job schedule which minimizes the total weighted completion time. We solve this problem based on the chance-constrained programming. First, the problem is formulated in a form of stochastic programming and then prepared in a form of deterministic mixed binary integer linear programming such that it can be solved by a linear programming solver. To solve the problem efficiently, we develop an efficient hybrid method. Exploiting a heuristic algorithm in order to satisfy the constraints, an ant colony optimization algorithm is applied to construct high-quality solutions to the problem. The proposed approach is tested on instances where the random variables are normally, uniformly, or exponentially distributed.     

Group shop scheduling with uncertain data and a general cost objective

In this paper, a stochastic group shop scheduling problem with a due date-related objective is studied. The group shop scheduling problem provides a general formulation including two other shop scheduling problems, the job shop and the open shop. Both job release dates and processing times are assumed to be random variables with known distributions. Moreover, earliness and tardiness of jobs are penalized at different rates. The objective is to minimize the expected maximum completion cost among all jobs. A lower bound on the objective function is proposed, and then, a hybrid approach following a simulation optimization procedure is developed to deal with the problem. An ant colony optimization algorithm is employed to construct good feasible solutions, while a discrete-event simulation model is used to estimate the performance of each constructed solution that, taking into account its lower bound, may improve the best solution found so far. The proposed approach is then evaluated through computational experiments.     

面向Job Shop调度的算法融合方法研究

提出一种算法融合方法,解决单一算法求解Job Shop调度问题存在的不足,提高这类问题的求解质量。在融合方法中,采用遗传算法和蚁群算法进行并行搜索;根据Job Shop调度问题解的特征,提出基于关键工序的邻域选择方法,并将基于这种邻域选择方法的禁忌搜索算法作为局部搜索算法,加强了遗传算法和蚁群算法的局部搜索能力。采用算法融合方法构造的优化算法对13个难解的benchmarks问题实例进行求解,在较短的时间内,得到的十次实验结果的makespan最优值和平均值优于并行遗传算法(PGA)和TS算法。采用算法融合方法构造的优化算法具有较强的搜索能力,说明提出的算法融合方法是有效的。     

A fuzzy-neural approach for estimating the monthly output of a semiconductor manufacturing factory

The customer order scheduling problem (COSP) is defined as to determine the sequence of tasks to satisfy the demand of customers who order several types of products produced on a single machine. A setup is required whenever a product type is launched. The objective of the scheduling problem is to minimize the average customer order flow time. Since the customer order scheduling problem is known to be strongly NP-hard, we solve it using four major metaheuristics and compare the performance of these heuristics, namely, simulated annealing, genetic algorithms, tabu search, and ant colony optimization. These are selected to represent various characteristics of metaheuristics: nature-inspired vs. artificially created, population-based vs. local search, etc. A set of problems is generated to compare the solution quality and computational efforts of these heuristics. Results of the experimentation show that tabu search and ant colony perform better for large problems whereas simulated annealing performs best in small-size problems. Some conclusions are also drawn on the interactions between various problem parameters and the performance of the heuristics.     

A population-based hybrid ant system for quadratic assignment formulations in facility layout design

The facility layout design problem is an extensively studied research problem and belongs to nonpolynomial hard (NP-hard) combinatorial optimization problem. Quadratic assignment problem (QAP) is one of the formulations that is investigated for facility layout design because of its wide applicability. Ant colony optimization (ACO), a biologically inspired heuristic has centered on solving the QAP by achieving approximation as good as possible. This paper presents a population-based hybrid ant system (PHAS), which is an extension of the hybrid ant system (HAS) in which the size of the ant colony has been fixed. The performance of the proposed ant algorithm for QAP is compared with the existing metaheuristic implementations such as tabu search, reactive tabu search, simulated annealing, genetic hybrid method, HAS, and max–min ant system. The experimental results show that the proposed PHAS perform significantly better than the other existing algorithms of QAP.     

Reentrant two-stage multiprocessor flow shop scheduling with due windows

Reentrant flow shop scheduling allows a job to revisit a particular machine several times. The topic has received considerable interest in recent years; with related studies demonstrating that particle swarm algorithm (PSO) is an effective and efficient means of solving scheduling problems. By selecting a wafer testing process with the due window problem as a case study, this study develops a farness particle swarm optimization algorithm (FPSO) to solve reentrant two-stage multiprocessor flow shop scheduling problems in order to minimize earliness and tardiness. Computational results indicate that either small- or large-scale problems are involved in which FPSO outperforms PSO and ant colony optimization with respect to effectiveness and robustness. Importantly, this study demonstrates that FPSO can solve such a complex scheduling problem efficiently.     

A hybrid scatter search for the partial job shop scheduling problem

This paper presents a special case of the general shop called partial job shop problem. The partial job shop is a more realistic generalization of the mixed shop problem. The problem is formulated as a mixed integer programming model. A scatter search algorithm combined with tabu search and path relinking is used to tackle this problem with makespan criterion. The computational experiments are performed on some problem instances. The results are compared with a lower bound and the effectiveness of the algorithm is shown.     

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.     

Industrial applications of the ant colony optimization algorithm

The ant colony optimization (ACO) algorithm is a fast suboptimal meta-heuristic based on the behavior of a set of ants that communicate through the deposit of pheromone. It involves a node choice probability which is a function of pheromone strength and inter-node distance to construct a path through a node-arc graph. The algorithm allows fast near optimal solutions to be found and is useful in industrial environments where computational resources and time are limited. A hybridization using iterated local search (ILS) is made in this work to the existing heuristic to refine the optimality of the solution. Applications of the ACO algorithm also involve numerous traveling salesperson problem (TSP) instances and benchmark job shop scheduling problems (JSSPs), where the latter employs a simplified ant graph-construction model to minimize the number of edges for which pheromone update should occur, so as to reduce the spatial complexity in problem computation.     

一种改进蚁群算法在车间作业调度问题中的研究与应用

讨论了蚁群算法在车间作业调度问题中的应用，针对传统蚁群算法求解调度问题的不足，将邻域搜索与蚁群算法结合，通过实验验证了该混合算法的有效性和优化性。     

A hybrid two-phase encoding particle swarm optimization for total weighted completion time minimization in proportionate flexible flow shop scheduling

A proportionate flow shop (PFS) is a special case of the m machine flow shop problem. In a PFS, a fixed sequence of machines is arranged in s stages (s?>?1) with only a single machine at each stage, and the processing time for each job is the same on all machines. Notably, PFS problems have garnered considerable attention recently. A proportionate flexible flow shop (PFFS) scheduling problem combines the properties of PFS problems and parallel-identical-machine scheduling problems. However, few studies have investigated the PFFS problem. This study presents a hybrid two-phase encoding particle swarm optimization (TPEPSO) algorithm to the PFFS problem with a total weighted completion time objective. In the first phase, a sequence position value representation is designed based on the smallest position value rule to convert continuous position values into job sequences in the discrete PFFS problem. During the second phase, an absolute position value representation combined with a tabu search (TS) is applied starting from the current position of particles that can markedly improve swarm diversity and avoid premature convergence. The hybrid TPEPSO algorithm combines the cooperative and competitive characteristics of TPEPSO and TS. Furthermore, a candidate list strategy is designed for the TS to examine the neighborhood and concentrate on promising moves during each iteration. Experimental results demonstrate the robustness of the proposed hybrid TPEPSO algorithm in terms of solution quality. Moreover, the proposed hybrid TPEPSO algorithm is considerably faster than existing approaches for the same benchmark problems in literature.     

求解液压阀块加工车间调度的多作用力微粒群算法

为有效地解决液压阀块加工车间调度问题,考虑工序间和机器间的约束关系,以最大完成时间最小为目标,给出了液压阀块加工车间调度优化模型。为平衡算法的全局和局部搜索能力,提出了多作用力微粒群(MFPSO)算法,采用多作用力阶段性搜索策略,将搜索过程划分为前期、中期、后期3个阶段,并对应构造单一斥力、平衡引斥力、单一引力3种作用力规则,在不同搜索阶段采用不同的作用力规则,提高了算法的搜索机制和寻优性能。将MFPSO算法用于求解液压阀块加工车间调度问题,利用矩阵变量来处理约束条件,给出了一种基于矩阵的微粒编码、解码方法。通过液压阀块加工车间调度优化实例,将MFPSO算法与微粒群算法、中值导向微粒群算法、扩展微粒群算法、蚁群算法进行了对比,结果表明,提出的MFPSO算法结果最优,从而验证了该算法的有效性。     

模糊分布式柔性作业车间调度优化

针对考虑工件加工时间不确定性的模糊分布式柔性作业车间调度问题(fuzzy Distributed Flexible Job Shop Scheduling Problem, fDFJSP),将加工时间用三角模糊数表示,以最小化最大模糊完工时间为优化目标,提出一种改进的人工蜂群算法进行求解。针对fDFJSP的分布式特点,设计了基于车间-工序-机器的三层编码方式,针对不同编码层,采用多种混合搜索策略,以提升算法的邻域和全局搜索能力。为测试算法的性能,设计了2组实验对5个算例进行测试,并与代表性算法进行对比。结果表明,所提算法结果总体优于其他对比算法,能够有效求解具有模糊加工时间的模糊分布式柔性作业车间调度问题。     

基于混合遗传鲸鱼优化算法的柔性作业车间自动导引车融合调度方法

针对柔性作业车间调度问题,考虑自动导引车(AGV)在车间制造过程中只参与装卸和搬运工作,提出一种实现AGV路径规划与柔性作业车间调度集成优化的融合调度模型。采用基于工序排序与机器选择两个子问题的二维向量编码方案,并在解码过程中提出基于最先服务原则的AGV安排策略。对鲸鱼优化算法进行离散化改进,针对性地设计了多种种群初始化策略,引入遗传算法的交叉、变异操作以提升鲸鱼优化算法的全局搜索能力,并嵌入局部搜索算法以达到全局搜索和局部搜索的平衡,构建了一种混合遗传鲸鱼优化算法（HGWOA）来求解该融合调度模型。通过经典测试算例验证了算法性能,并使用正交试验优化了算法参数。研究结果表明,HGWOA算法用于求解柔性作业车间AGV融合调度问题可以获得较好的效果。     

一类解决Job Shop问题的禁忌搜索算法

针对Job shop问题，设计了一种改进的禁忌搜索算法（MTS算法）。MTS算法从多个初始解开始，将传统禁忌搜索算法由串行搜索结构变为并行搜索结构；采用互换和交叉两种邻域搜索函数，既有利于新邻域的探索又有利于交换信息；基于目标值的禁忌表保证了群体的多样性。实验表明，MTS算法克服了传统禁忌搜索算法的缺陷，具有较高的求解质量和鲁棒性。     

A hybrid intelligent algorithm and rescheduling technique for job shop scheduling problems with disruptions

In most real manufacturing environment, schedules are usually inevitable with the presence of various unexpected disruptions. In this study, a new rescheduling technique based on a hybrid intelligent algorithm is developed for solving job shop scheduling problems with random job arrivals and machine breakdowns. According to the dynamic feature of this problem, a new initialization method is proposed to improve the performance of the hybrid intelligent algorithm, which combines the advantage of genetic algorithm and tabu search. In order to solve the difficulty of using the mathematical model to express the unexpected disruptions, a simulator is designed to generate the disruptions. The performance measures investigated respectively are: mean flow time, maximum flow time, mean tardiness, maximum tardiness, and the number of tardy jobs. Moreover, many experiments have been designed to test and evaluate the effect of different initializations in several disruption scenarios. Finally, the performance of the new rescheduling technique is compared with other rescheduling technologies in various shop floor conditions. The experimental results show that the proposed rescheduling technique is superior to other rescheduling techniques with respect to five objectives, different shop load level, and different due date tightness. The results also illustrate that the proposed rescheduling technique has a good robustness in the dynamic manufacturing environment.     

Ant colony optimization for job shop scheduling using multi-attribute dispatching rules

This paper proposes a heuristic method based on ant colony optimization to determine the suboptimal allocation of dynamic multi-attribute dispatching rules to maximize job shop system performance (four measures were analyzed: mean flow time, max flow time, mean tardiness, and max tardiness). In order to assure high adequacy of the job shop system representation, modeling is carried out using discrete-event simulation. The proposed methodology constitutes a framework of integration of simulation and heuristic optimization. Simulation is used for evaluation of the local fitness function for ants. A case study is used in this paper to illustrate how performance of a job shop production system could be affected by dynamic multi-attribute dispatching rule assignment.     

面向云计算环境任务调度的改进蚁群算法

云计算环境下的任务调度问题是一个NP完全问题,其目的是在各个处理节点上合理分配任务,优化调度策略以保证有效完成任务。以总任务完成时间最短和计算成本最低为优化目标,针对蚁群优化算法易陷入局部最优的缺陷,提出了一种求解该问题的改进蚁群算法。该算法将遗传算法的二点交叉算子融入到蚁群优化算法中,以提高蚁群优化算法的局部搜索能力。通过在云仿真平台Cloud Sim上进行仿真实验,结果表明改进蚁群算法缩短了总任务完成时间,降低了计算成本,从而证明了该算法能有效地解决云计算环境下的任务调度问题,并且其优化能力和收敛速度优于蚁群优化算法和改进离散粒子群算法。     

An ant colony algorithm for scheduling in flowshops with sequence-dependent setup times of jobs

The problem of scheduling in flowshops with sequence-dependent setup times of jobs is considered and solved by making use of ant colony optimization (ACO) algorithms. ACO is an algorithmic approach, inspired by the foraging behavior of real ants, that can be applied to the solution of combinatorial optimization problems. A new ant colony algorithm has been developed in this paper to solve the flowshop scheduling problem with the consideration of sequence-dependent setup times of jobs. The objective is to minimize the makespan. Artificial ants are used to construct solutions for flowshop scheduling problems, and the solutions are subsequently improved by a local search procedure. An existing ant colony algorithm and the proposed ant colony algorithm were compared with two existing heuristics. It was found after extensive computational investigation that the proposed ant colony algorithm gives promising and better results, as compared to those solutions given by the existing ant colony algorithm and the existing heuristics, for the flowshop scheduling problem under study.