Performance of an ant colony optimisation algorithm in dynamic job shop scheduling problems

The goal of the current study is to identify appropriate application domains of Ant Colony Optimisation (ACO) in the area of dynamic job shop scheduling problem. The algorithm is tested in a shop floor scenario with three levels of machine utilisations, three different processing time distributions, and three different performance measures for intermediate scheduling problems. The steady-state performances of ACO in terms of mean flow time, mean tardiness, total throughput on different experimental environments are compared with those from dispatching rules including first-in-first-out, shortest processing time, and minimum slack time. Two series of experiments are carried out to identify the best ACO strategy and the best performing dispatching rule. Those two approaches are thereafter compared with different variations of processing times. The experimental results show that ACO outperforms other approaches when the machine utilisation or the variation of processing times is not high.     

遗传算法的双目标柔性作业车间调度研究

研究了FMS环境下先进制造车间路径柔性的优化调度问题.同时考虑现代生产准时制的要求,建立了柔性作业车间调度问题的双目标数学优化模型,并给出了求解模型的遗传算法的具体实现过程;针对模型的特殊性,提出了染色体两层编码结构,将AOV网络图应用到解码和适应度函数的计算中,通过一个调度实例进行验证,给出了相应的选择、交叉、变异操作设计方案.     

A hybrid artificial bee colony algorithm for flexible job shop scheduling with worker flexibility

The traditional flexible job shop scheduling problem (FJSP) considers machine flexibility but not worker flexibility. Given the influence and potential of human factors in improving production efficiency and decreasing the cost in practical production systems, we propose a mathematical model of an extended FJSP with worker flexibility (FJSPW). A hybrid artificial bee colony algorithm (HABCA) is presented to solve the proposed FJSPW. For the HABCA, effective encoding, decoding, crossover and mutation operators are designed, and a new effective local search method is developed to improve the speed and exploitation ability of the algorithm. The Taguchi method of Design of Experiments is used to obtain the best combination of key parameters of the HABCA. Extensive computational experiments carried out to compare the HABCA with some well-performing algorithms from the literature confirm that the proposed HABCA is more effective than these algorithms, especially on large-scale FJSPW instances.     

A hybrid artificial bee colony algorithm for a flexible job shop scheduling problem with overlapping in operations

Overlapping in operations is an effective technology for productivity improvement in modern manufacturing systems. Thus far, however, there are still rare works on flexible job shop scheduling problems (FJSPs) concerning this strategy. In this paper, we present a hybrid artificial bee colony (hyABC) algorithm to minimise the total flowtime for a FJSP with overlapping in operations. In the proposed hyABC, a dynamic scheme is introduced to fine-tune the search scope adaptively. In view of poor exploitation ability of artificial bee colony algorithm, a modified migrating birds optimisation algorithm (MMBO) is developed and integrated into the search process for better balancing global exploration and local exploitation. In MMBO, a forward share strategy with one-job based crossover is designed to make good use of valuable information from behind solutions. Besides, an improved downward share scheme is adopted to increase diversification of the population, and thus alleviate the premature convergence. Extensive experiments based on benchmark instances with different scales are carried out and comparisons with other recent algorithms identify the effectiveness of the proposed hyABC.     

基于蚁群算法的试验流程优化研究

水中兵器的海上试验涉及许多人员、兵力、被试产品、测量设备等，试验周期长、消耗大，因此如何缩短试验周期是亟待研究解决的问题．文中首先将试验流程优化问题转化为车间调度问题，建立了相应的数学模型，再应用蚁群算法转移规则得到中间结果并进行排队以对各种资源约束进行处理．最后将结果利用局部搜索算法优化后作为蚁群算法信息素更新的基础．实例计算结果表明，该方法优化效果良好．     

Ant colony optimisation algorithms for two-stage permutation flow shop with batch processing machines and nonidentical job sizes

This paper focuses on minimising the maximum completion time for the two-stage permutation flow shop scheduling problem with batch processing machines and nonidentical job sizes by considering blocking, arbitrary release times, and fixed setup and cleaning times. Two hybrid ant colony optimisation algorithms, one based on job sequencing (JHACO) and the other based on batch sequencing (BHACO), are proposed to solve this problem. First, max-min pheromone restriction rules and a local optimisation rule are embedded into JHACO and BHACO, respectively, to avoid trapping in local optima. Then, an effective lower bound is estimated to evaluate the performances of the different algorithms. Finally, the Taguchi method is adopted to investigate and optimise the parameters for JHACO and BHACO. The performances of the proposed algorithms are compared with that of CPLEX on small-scale instances and those of a hybrid genetic algorithm (HGA) and a hybrid discrete differential evolution (HDDE) algorithm on full-scale instances. The computational results demonstrate that BHACO outperforms JHACO, HDDE and HGA in terms of solution quality. Besides, JHACO strikes a balance between solution quality and run time.     

Scheduling job shop problems with sequence-dependent setup times

In this work we consider job shop problems where the setup times are sequence dependent under minimisation of the maximum completion time or makespan. We present a genetic algorithm to solve the problem. The genetic algorithm is hybridised with a diversification mechanism, namely the restart phase, and a simple form of local search to enrich the algorithm. Various operators and parameters of the genetic algorithm are reviewed to calibrate the algorithm by means of the Taguchi method. For the evaluation of the proposed hybrid algorithm, it is compared against existing algorithms through a benchmark. All the results demonstrate that our hybrid genetic algorithm is very effective for the problem.     

Quantum-inspired ant colony optimisation algorithm for a two-stage permutation flow shop with batch processing machines

This paper studied two-stage permutation flow shop problems with batch processing machines, considering different job sizes and arbitrary arrival times, with the optimisation objective of minimising the makespan. The quantum-inspired ant colony optimisation (QIACO) algorithm was proposed to solve the problem. In the QIACO algorithm, the ants are divided into two groups: one group selects the largest job in terms of job size as the initial job for each batch and the other group selects the smallest job as the initial job for each batch. Each group of ants has its own pheromone matrix. In the computational experiment, our novel algorithm was compared with the hybrid discrete differential evolution (HDDE) algorithm and the batch-based hybrid ant colony optimisation (BHACO) algorithm. Although the HDDE algorithm has a shorter run time, the quality of the solution for large-scale jobs is not good, while the BHACO algorithm always obtains a better solution but requires a longer run time. The computational results show that the QIACO algorithm embedded in the quantum information has advantages in terms of both solution quality and running time.     

Ant colony optimisation with parameterised search space for the job shop scheduling problem

The job-shop scheduling problem (JSSP) is known to be NP-hard. Due to its complexity, many metaheuristic algorithm approaches have arisen. Ant colony metaheuristic algorithm, lately proposed, has successful application to various combinatorial optimisation problems. In this study, an ant colony optimisation algorithm with parameterised search space is developed for JSSP with an objective of minimising makespan. The problem is modelled as a disjunctive graph where arcs connect only pairs of operations related rather than all operations are connected in pairs to mitigate the increase of the spatial complexity. The proposed algorithm is compared with a multiple colony ant algorithm using 20 benchmark problems. The results show that the proposed algorithm is very accurate by generating 12 optimal solutions out of 20 benchmark problems, and mean relative errors of the proposed and the multiple colony ant algorithms to the optimal solutions are 0.93% and 1.24%, respectively.     

Solving a time constrained two-crane routing problem for material handling with an ant colony optimisation approach: an application in the roof-tile industry

This paper presents an ant colony optimisation (ACO)-based solution approach for a real-world two-crane routing problem, where a number of different load carriers must be moved within a given cycle time by two gantry cranes in a continuous production process for roof tiles. The cranes have to transport the roof-tile batches and to return the load carriers and intermediate pads for subsequent batches. A feasible solution has to observe workflow-, space-, collision-, and machine-cycle constraints. The objective is to find a feasible schedule that minimises the working time for both cranes. The authors compare different solution approaches in terms of learning – and visibility strategies based on ACO in extensive numerical studies. A visibility concept is used to both partition and balance workload between the cranes.     

Solving coupled task assignment and capacity planning problems for a job shop by using a concurrent genetic algorithm

The problems of task assignment and capacity planning of manufacturing systems have been researched for many years. However, in the existing literature, these two types of problems are researched independently. Namely, when solving the task assignment problem, it is usually assumed that the production capacity of the manufacturing systems has been determined. On the other hand, when solving the capacity planning problem, the production tasks assigned to the workstations in the manufacturing system have also been determined. Actually, the task assignment problem and the capacity planning problem are coupled with each other. When we assign production tasks to workstations, production capacities of these workstations should be regulated so that they are enough for completing the tasks. At the same time, when planning the production capacity, we must know what production tasks are assigned to what workstations. This research focuses on the coupling relations between the two problems for a closed job shop, in which the total work-in-process (WIP) is assumed to be constant. The objective of the task assignment problem is to balance the workloads of the workstations and the objectives of the capacity planning problem are maximising the throughput and minimising total costs of machine purchasing and WIP inventory. We construct the fundamental system architecture for controlling the two coupled optimisation processes, and propose a concurrent genetic algorithm (CGA) to solve the two coupled optimisation problems. The influences of the decision variables of one problem on the objective function of the other problem are taken into consideration when the fitness functions of the CGA are constructed. Numerical experiments are done to verify the effectiveness of the algorithm.     

改进的蚁群算法及其在卫星网络路由计算中的应用

介绍了蚁群算法的原理，然后对现有蚁群算法进行了一些改进，使它能够快速地收敛以满足高速变化的卫星网络拓扑结构．采用改进的虚拟拓扑策略解决了卫星网络拓扑高速变换的问题．将改进的蚁群算法应用于其上，并给出了相应的性能评估．所提出的改进的虚拟拓扑策略，能够大大减少一个系统周期内卫星网的时间片个数．应用于此基础上的改进的蚁群算法也体现了较好的性能．     

改进蚁群算法在物流配送路径中的应用

针对物流配送路径优化问题的特点,分析了基本蚁群算法的不足之处,并对原有蚁群算法进行改进.同时引入"扰动因子"和"奖惩"机制,建立数学模型,进而对物流配送车辆路径问题进行了实验仿真.结果表明,改进后的蚁群算法提高了全局寻优能力与收敛速度,取得了较好的效果.     

A heuristic model for dynamic flexible job shop scheduling problem considering variable processing times

In real scheduling problems, unexpected changes may occur frequently such as changes in task features. These changes cause deviation from primary scheduling. In this article, a heuristic model, inspired from Artificial Bee Colony algorithm, is proposed for a dynamic flexible job-shop scheduling (DFJSP) problem. This problem consists of n jobs that should be processed by m machines and the processing time of jobs deviates from estimated times. The objective is near-optimal scheduling after any change in tasks in order to minimise the maximal completion time (Makespan). In the proposed model, first, scheduling is done according to the estimated processing times and then re-scheduling is performed after determining the exact ones considering machine set-up. In order to evaluate the performance of the proposed model, some numerical experiments are designed in small, medium and large sizes in different levels of changes in processing times and statistical results illustrate the efficiency of the proposed algorithm.     

Bi-objective partial flexible job shop scheduling problem: NSGA-II,NRGA, MOGA and PAES approaches

This paper deals with a problem of partial flexible job shop with the objective of minimising makespan and minimising total operation costs. This problem is a kind of flexible job shop problem that is known to be NP-hard. Hence four multi-objective, Pareto-based, meta-heuristic optimisation methods, namely non-dominated sorting genetic algorithm (NSGA-II), non-dominated ranked genetic algorithm (NRGA), multi-objective genetic algorithm (MOGA) and Pareto archive evolutionary strategy (PAES) are proposed to solve the problem with the aim of finding approximations of optimal Pareto front. A new solution representation is introduced with the aim of solving the addressed problem. For the purpose of performance evaluation of our proposed algorithms, we generate some instances and use some benchmarks which have been applied in the literature. Also a comprehensive computational and statistical analysis is conducted in order to analyse the performance of the applied algorithms in five metrics including non-dominated solution, diversification, mean ideal distance, quality metric and data envelopment analysis are presented. Data envelopment analysis is a well-known method for efficiently evaluating the effectiveness of multi-criteria decision making. In this study we proposed this method of assessment of the non-dominated solutions. The results indicate that in general NRGA and PAES have had a better performance in comparison with the other two algorithms.     

Learning dispatching rules using random forest in flexible job shop scheduling problems

In this paper, we address the flexible job-shop scheduling problem (FJSP) with release times for minimising the total weighted tardiness by learning dispatching rules from schedules. We propose a random-forest-based approach called Random Forest for Obtaining Rules for Scheduling (RANFORS) in order to extract dispatching rules from the best schedules. RANFORS consists of three phases: schedule generation, rule learning with data transformation, and rule improvement with discretisation. In the schedule generation phase, we present three solution approaches that are widely used to solve FJSPs. Based on the best schedules among them, the rule learning with data transformation phase converts them into training data with constructed attributes and generates a dispatching rule with inductive learning. Finally, the rule improvement with discretisation improves dispatching rules with a genetic algorithm by discretising continuous attributes and changing parameters for random forest with the aim of minimising the average total weighted tardiness. We conducted experiments to verify the performance of the proposed approach and the results showed that it outperforms the existing dispatching rules. Moreover, compared with the other decision-tree-based algorithms, the proposed algorithm is effective in terms of extracting scheduling insights from a set of rules.     

A hybrid genetic algorithm and tabu search for a multi-objective dynamic job shop scheduling problem

In most real manufacturing environments, schedules are usually inevitable with the presence of various unexpected disruptions. In this paper, a rescheduling method based on the hybrid genetic algorithm and tabu search is introduced to address the dynamic job shop scheduling problem with random job arrivals and machine breakdowns. Because the real-time events are difficult to express and take into account in the mathematical model, a simulator is proposed to tackle the complexity of the problem. A hybrid policy is selected to deal with the dynamic feature of the problem. Two objectives, which are the schedule efficiency and the schedule stability, are considered simultaneously to improve the robustness and the performance of the schedule system. Numerical experiments have been designed to test and evaluate the performance of the proposed method. This proposed method has been compared with some common dispatching rules and meta-heuristic algorithms that have been widely used in the literature. The experimental results illustrate that the proposed method is very effective in various shop-floor conditions.     

基于蚁群算法的双分区仓库拣货路径的优化

为提高现代仓库作业中拣货这一核心环节的效率,研究了仓库拣货路径的优化,提出了根据双分区仓库中拣货路径的特点,采用蚁群算法优化求解的拣货路径算法,并通过仿真将该算法的性能与传统穿越策略、S形启发式算法进行了比较。比较结果表明,以蚁群算法优化路径问题可以明显减少路径的距离,具有良好的实用性。     

A generalized permutation approach to job shop scheduling with genetic algorithms

In order to sequence the tasks of a job shop problem (JSP) on a number of machines related to the technological machine order of jobs, a new representation technique — mathematically known as permutation with repetition is presented. The main advantage of this single chromosome representation is — in analogy to the permutation scheme of the traveling salesman problem (TSP) — that it cannot produce illegal operation sequences. As a consequence of the representation scheme a new crossover operator preserving the initial scheme structure of permutations with repetition will be sketched. Its behavior is similar to the well known Order-Crossover for simple permutation schemes. Actually theGOX operator for permutations with repetition arises from aGeneralisation ofOX. Computational experiments show, that GOX passes the information from a couple of parent solutions efficiently to offspring solutions. Together, the new representation and GOX support the cooperative aspect of genetic search for scheduling problems strongly.Supported by the Deutsche Forschungsgemeinschaft (Project Parnet)