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.     

求解卫星任务调度问题的时间片蚁群算法

为更好地求解卫星任务调度问题,提出一种时间片蚁群算法.在算法中引入任务时间片,使算法可分辨任务在不同时间窗内的执行情况;在任务分配中设计了带偏好的卫星片切割策略,改变了以往的任务分配搜索模式,极大地提高了算法的执行速度.相对于传统的蚁群算法和遗传算法,所提方法在求解卫星任务调度时具有较大优势.     

Multi-objective artificial bee colony for interval job shop scheduling with flexible maintenance

In scheduling problem with uncertainty, flexible preventive maintenance (PM) and multiple objectives are seldom investigated. In this study, interval job shop scheduling problem with non-resumable jobs and flexible maintenance is considered and an effective multi-objective artificial bee colony (MOABC) is proposed, in which an effective decoding procedure is used to build the schedule and handle PM operation. The objective is to minimize interval makespan and a newly defined objective called total interval tardiness. In each cycle, a dominance-based greedy principle is adopted, a dominance-based tournament is utilized to choose solution for onlooker bee, and the non-dominated ranking is applied to update the non-dominated set. A solution with the highest rank is replaced with a non-dominated solution every certain cycle. Computational results show the good performance of MOABC on the considered problem.     

考虑运输时间窗的批—离散混合流水车间调度

为提高船舶分段生产效率,研究从分段涂装作业中提炼出的考虑运输时间窗的两阶段混合流水车间调度问题。其中第一阶段含多台批处理机、第二阶段含多台离散机。批处理机能同时处理多个工件,因而同一批次的工件在批处理阶段具有相同的开始作业和完成作业时间。两阶段之间存在有限等待时间和运输能力约束,并且阶段间的运输过程只能发生在特定运输时间窗内。以最小化最大完工时间为优化目标,同时考虑分段在冲砂车间的排布建立数学模型,提出一种混合多种启发式规则的差分进化算法。实例验证和数值分析表明,所提算法能在可接受运行时间内获得较满意的近优解,为分段涂装调度问题提供有效的解决方案。     

Hybridizing tabu search with ant colony optimization for solving job shop scheduling problems

The manufacturing industry continues to be a prime contributor and it requires an efficient schedule. Scheduling is the allocation of resources to activities over time and it is considered to be a major task done to improve shop-floor productivity. Job shop problem comes under this category and is combinatorial in nature. Research on optimization of the job shop problem is one of the most significant and promising areas of optimization. This paper presents an application of the global optimization technique called tabu search that is combined with the ant colony optimization technique to solve the job shop scheduling problems. The neighborhoods are selected based on the strategies in the ant colony optimization with dynamic tabu length strategies in the tabu search. The inspiring source of ant colony optimization is pheromone trail that has more influence in selecting the appropriate neighbors to improve the solution. The performance of the algorithm is tested using well-known benchmark problems and is also compared with other algorithms in the literature.     

Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems

This paper presents a hybrid Pareto-based discrete artificial bee colony algorithm for solving the multi-objective flexible job shop scheduling problem. In the hybrid algorithm, each solution corresponds to a food source, which composes of two components, i.e., the routing component and the scheduling component. Each component is filled with discrete values. A crossover operator is developed for the employed bees to learn valuable information from each other. An external Pareto archive set is designed to record the non-dominated solutions found so far. A fast Pareto set update function is introduced in the algorithm. Several local search approaches are designed to balance the exploration and exploitation capability of the algorithm. Experimental results on the well-known benchmark instances and comparisons with other recently published algorithms show the efficiency and effectiveness of the proposed algorithm.     

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.     

一种基于多agent的柔性车间调度系统研究

针对柔性车间调度的特点,提出了一种分布式多agent柔性车间调度系统.系统由工件a-gent,生产单元agent和一个全局agent组成.生产单元agent根据三类agent相互协商得到总评价指数选择工件,工件agent根据特定规则选择加工设备进行加工.最后用Arena仿真软件建立模型,对柔性车间调度加权滞后和问题进行仿真实验,与传统的分派规则比较,结果显示基于多agent的柔性车间调度方法明显优于传统的分派规则.     

考虑运输时间柔性作业车间调度问题的快速寻优方法

为了快速获得考虑运输时间的柔性生产调度问题的近优解,进行了快速寻优方法研究。采用运输时间矩阵对析取图模型进行改进,建立了设备选择的多阶段决策方法。建立了考虑运输时间的关键链优化方法,通过邻域搜索快速获得近优解。开发了调度实验系统对上述工作进行验证。实验结果表明,该方法可较稳定地获得近优调度解,并具有较好的计算效率。     

Interval job shop scheduling problems

This paper focuses on the design and development of an expert system for on-line detection of various control chart patterns so as to enable the quality control practitioners to initiate prompt corrective actions for an out-of-control manufacturing process. Using this expert system developed in Visual BASIC 6, all the nine most commonly observed control chart patterns, e.g., normal, stratification, systematic, increasing trend, decreasing trend, upward shift, downward shift, cyclic, and mixture can be recognized well, employing an optimal set of seven shape features. Based on an observation window of 32 data points, it can plot the control chart, compute the control limits, identify the control chart pattern, calculate the process capability index, determine the maximum run length, and identify the starting point of the maximum run length. After pattern recognition, it can also inform the users about various root assignable causes associated with a particular pattern along with the necessary pre-emptive actions. It opens up wide opportunities for quality improvement and real-time applications in diverse manufacturing processes. This developed expert system is built for a vertical drilling process and its recognition performance is tested using simulated process data.     

Controllable processing time policies for job shop manufacturing system

The research presented concerns the policy to manage a job shop in which the machines have controllable processing times. A controllable processing time means that it can be reduced processing time by using additional resources. The model proposed is based on a multi-agent architecture that supports the manufacturing system. The policy proposed concerns the evaluation of the workload of the resources. It is necessary to define the following issues for the controllable time process of a resource: the condition of start and the duration of the process time reduction. Two approaches are proposed to assign the resources to the machines. The first approach concerns the reduction of the processing time one machine at time, while the second approach distributes the additional resources proportionally among the machines. A simulation environment is developed to test the proposed approach in several dynamic conditions. The simulation results show that the control of the processing times proposed allows to improve significantly the performance.     

Solving job shop scheduling problems using artificial immune system

The n-job, m-machine job shop scheduling (JSS) problem is one of the general production scheduling problems. Many existing heuristics give solutions for small size problems with near optimal solutions. This paper deals with the criterion of makespan minimization for the job shop scheduling of different size problems. The proposed computational method of artificial immune system algorithm (AIS) is used for finding optimal makespan values of different size problems. The artificial immune system algorithm is tested with 130 benchmark problems [10 (ORB1-ORB5 & ARZ5-ARZ9), 40 (LA01-LA40) and 80 (TA01-TA80)]. The results show that the AIS algorithm is an efficient and effective algorithm which gives better results than the Tabu search shifting bottleneck procedure (TSSB) as well as the best solution of shifting bottleneck procedure ( SB-GLS1 ) of Balas and Vazacopoulos.     

制造系统通用作业计划与蚁群算法优化

分析了基本作业方式的“通用-特例”关系,提出了全面研究上述基本作业方式的通用作业计划的概念,建立了通用作业计划非连接图模型及基于蚁群算法的优化方法。算例研究假定一制造系统包含开放作业、异顺序作业、混杂流水作业三种作业方式,将其按照通用作业计划方式采用蚁群算法进行优化,所得的近优加工流程时间显著优于采用穷举法对三种作业方式分别优化所得的最优解。     

An intelligent operations scheduling system in a job shop

Scheduling jobs effectively under the consideration of actual loads on machines is one of the most complicated tasks in production control. The conventional scheduling methods fail because of the complexity of the tasks. To deal with the complexity, knowledge-based approaches to job shop scheduling have been attempted. This paper presents an interactive scheduling expert system, IOSS (Intelligent Operations Scheduling System), which performs both predictive and reactive scheduling. IOSS combines the knowledge-based scheduling method with the interactive scheduling method to generate a feasible schedule and to revise the existing schedule. It is based on opportunistic and interactive repair based problem solving within a blackboard architecture. To handle conflicting events, heuristics are applied from the order point of view. Flexible reaction management is possible while keeping the changes in the generated schedule to a minimum by adjusting the schedule for tardy operations or changes in job shop status. The effectiveness of the proposed concept is demonstrated by applying the developed system to an example case.     

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.     

单件小批量生产作业计划的倒排产算法研究

提出一种用于单件小批量生产中编制作业计划的算法模型———倒排产算法 ,并建立一套包含此模型的作业计划及调度监控集成系统。在科龙等企业的生产部门进行实施 ,获得良好效果     

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.     

Genetic algorithm with new encoding scheme for job shop scheduling

In so many combinatorial optimization problems, job shop scheduling problems have earned a reputation for being difficult to solve. Genetic algorithm has demonstrated considerable success in providing efficient solutions to many nonpolynomial-hard optimization problems. In the field of job shop scheduling, genetic algorithm has been intensively researched, and nine methods were proposed to encode a chromosome to represent a solution. In this paper, we proposed a novel genetic chromosome-encoding approach; in this encoding method, the operation of crossover and mutation was done in three-dimensional coded space. Some big benchmark problems were tried with the proposed three-dimensional encoding genetic algorithm for validation and the results are encouraging.     

Integrated and events-oriented job shop scheduling

When events such as rush orders or machine breakdown occurs during the production process in a job shop, the delivery date of order may be delayed. To solve this problem, an events-oriented job shop scheduling process is built, and a scheduling model integrated with an enterprise information system (EIS), including Enterprise Resource Planning (ERP), Product Data Management/Computer Aided Process Planning (PDM/CAPP), etc., is proposed and analyzed in detail. A genetic algorithm and a hybrid allocation-based method are used in scheduling. Lastly, an events-oriented job shop scheduling simulation system is presented .