Efficient dispatching rules for dynamic job shop scheduling

This study attempts to provide efficient dispatching rules for dynamic job shop scheduling by combining different dispatching rules. A dispatching rule is used to select the next job to be processed from a set of jobs awaiting service. A job shop will be treated as dynamic, when conditions such as continuously arriving new jobs and deviations from current schedule need to be accommodated, and a job shop should be treated as an integrated part of a manufacturing system. The discussion includes a simulation technique which uses ARENA 4.0. software to simulate the dynamic model of a job shop under various rules and performance measures . Results of the simulation show that, for most of the performance measures, combined rules perform well. In this study, the combined rules MWKR_FIFO and TWKR_SPT do well under most conditions.     

Ant colony system for job shop scheduling with time windows

Scheduling for a job shop production system is an integral aspect of production management. Scheduling operations must minimize stock, waste, and idle time and ensure on-time delivery of goods in a time window problem. In this study, due date is considered as an interval instead of a time point. This study addresses scheduling with a time window of job shop scheduling problem (JSP) and yields a solution that is close to the time window. The total penalty due to earliness and tardiness is minimized. As the problem is NP-hard, a mathematical model of the JSP with a time window is initially constructed, and data are then simulated. Solutions are obtained by ant colony optimization (ACO) programs written in C-language and are compared with the best solution obtained using LINGO 7.0 to determine the efficiency and robustness. Test results indicate that ACO is extremely efficient. Solution time using ACO is less than that using LINGO. Hence, ACO is both effective and efficient, which are two qualities stressed in business management.     

Learning iterative dispatching rules for job shop scheduling with genetic programming

This study proposes a new type of dispatching rule for job shop scheduling problems. The novelty of these dispatching rules is that they can iteratively improve the schedules by utilising the information from completed schedules. While the quality of the schedule can be improved, the proposed iterative dispatching rules (IDRs) still maintain the easiness of implementation and low computational effort of the traditional dispatching rules. This feature makes them more attractive for large-scale manufacturing systems. A genetic programming (GP) method is developed in this paper to evolve IDRs for job shop scheduling problems. The results show that the proposed GP method is significantly better than the simple GP method for evolving composite dispatching rules. The evolved IDRs also show their superiority to the benchmark dispatching rules when tested on different problem instances with makespan and total weighted tardiness as the objectives. Different aspects of IDRs are also investigated and the insights from these analyses are used to enhance the performance of IDRs.     

New dispatching rules for scheduling in a job shop — An experimental study

We present two new dispatching rules for scheduling in a job shop. These rules combine the process-time and work-content in the queue for the next operation on a job, by making use of additive and alternative approaches. An extensive and rigorous simulation study has been carried out to evaluate the performance of the proposed dispatching rules compared with those by the SPT rule, the WINQ rule, a random rule based on the SPT and WINQ rules, and the best existing rule. The important aspects of the results of the experimental investigation are also discussed in detail.     

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.     

Ant colony optimization for unrelated parallel machine scheduling

Meeting due dates is a major issue in most manufacturing systems, and one effective measure for due dates is total weighted tardiness. In this research, we consider an ant colony optimization (ACO) algorithm incorporating a number of new ideas (heuristic initial solution, machine reselection step, and local search procedure) to solve the problem of scheduling unrelated parallel machines to minimize total weighted tardiness. The problem is NP-hard in the strong sense, because the single machine case is already NP-hard in the strong sense. Computational results show that the proposed ACO algorithm outperforms other existing algorithms in terms of total weighted tardiness.     

多目标柔性作业车间调度优化研究

提出了一种集成权重系数变化法和小生境技术的混合遗传算法,建立了包括时间、成本、交货期满意度和设备利用率在内的多目标优化模型。采用基于工序的编码方式和“间隙挤压法”活动化解码方法;遗传算子包括选择、交叉、变异3种类型;选择操作采用轮盘赌选择方式。为了保证解的收敛性和多样性,采用了精英保留策略和小生境技术。交叉操作采用线性次序交叉方式;变异操作采用互换操作变异方法。染色体的适应度是各个目标函数的随机加权和。仿真实验证明,提出的混合遗传算法可以有效解决柔性作业车间多目标调度优化问题。     

基于PSO的车间柔性调度计算

在不确定车间信息环境下的调度策略问题中,提出多目标车间柔性调度的规划模型,并应用粒子群算法进行求解,给出具体的算法应用过程.实验结果验证该模型和算法的有效性及实用性.     

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

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

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.     

Ant colony optimization technique for the sequence-dependent flowshop scheduling problem

In the real world, production scheduling systems, usually optimal job scheduling, requires an explicit consideration of sequence-dependent setup times. One of the most important scheduling criteria in practical systems is makespan. In this paper, the author presents an ant colony optimization (ACO) algorithm for the sequence-dependent permutation flowshop scheduling problem. The proposed ACO algorithm benefits from a new approach for computing the initial pheromone values and a local search. The proposed algorithm is tested on randomly generated problem instances and results indicate that it is very competitive with the existing best metaheuristics.     

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

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

改进细菌觅食算法求解柔性作业车间调度问题

针对柔性作业车间调度问题的NP难特性,提出一种改进的细菌觅食优化算法。采用集成法策略同时求解柔性作业车间调度问题的机器分配和工序调度子问题。将细菌个体表示为工序串,建立问题和算法的映射关系;分别针对普通细菌个体和当前最优个体设计了多重趋化操作,以增强算法的局部搜索能力;复制操作设置繁殖阈和死亡阈,以提高对历史经验的继承程度;迁移/驱散操作中,结合改进的LPT启发式规则,提出带倾向性的迁移/驱散操作方式。采用正交试验对算法的重要参数进行了优化配置,通过搜索算子优化效果对比实验证明了正交试验的结论;进行了收敛性能对比实验,证明算法具有优秀的全局开发能力和局部探索能力;典型算例实验结果表明,该算法能够有效求解柔性作业车间调度问题。     

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.     

Multi-contextual ant colony optimization of intermediate dynamic job shop problems

Myopic scheduling uses information without correct context. Because job shops with dynamic job arrival are NP-hard, real-world planners often resort to myopic dispatching rules that produce schedules with unsatisfactory makespans and mean flow times. If metaheuristic scheduling does not use context properly, it can produce unsatisfactory schedules. This study proposes a new theory of context-dependent and multi-contextual scheduling functions in dynamic job shops. Three multi-contextual ant colony (MCAC) scheduling methods, SPT_MIT_JWT, MRT_MIT, and LRT_MIT_JWT, were designed to combine several context-dependent functions so that each ant had an independent, artificially intelligent model of what might happen in the future. These three MCACs scheduled 27 dynamic job shops. Each job shop had three parameters (number of operations per job, processing time per operation, and utilization level) at one of three levels. The results were compared to schedules from dispatching rules. Schedules from MRT_MIT had the best makespans for all 27 combinations of factors. For five cases in which utilization and operations per job were both high, schedules from longest processing time had the best mean flow time; in the other 22 cases, either SPT_MIT_JWT or LRT_MIT_JWT produced the schedule with the best mean flow time. These results indicate that the new theory can be used to design multi-contextual methods that produce effective schedules.     

作业车间区间型多属性瓶颈识别方法

针对扰动情形下作业车间瓶颈识别时机器的特征属性难以用确定值表示的问题,采用区间形式描述机器特征属性,构建了区间型多属性瓶颈识别模型,提出了区间TOPSIS多属性瓶颈识别方法.考虑瓶颈识别与瓶颈利用的紧密关系,提出了先进行瓶颈利用再进行瓶颈识别的统一框架.其中瓶颈利用层基于Plant-Simulation 仿真平台设置了机器故障等随机扰动,采用遗传算法对扰动情形下的调度问题进行了优化仿真,获得了适应扰动情形的最优调度优化方案;瓶颈识别层基于调度优化方案,综合考虑了瓶颈的多维特征属性,采用区间TOPSIS多属性瓶颈识别方法识别了瓶颈机器.通过与机器利用率、瓶颈出现率和移动瓶颈识别法等进行比较,验证了所提方法的有效性.最后,分析了制造成本和原材料成本两个参数对瓶颈识别的影响.     

Parallel line job shop scheduling using genetic algorithm

Parallel line job shop scheduling involves the optimal allocation and scheduling of jobs in multiple processing lines. Each job is allocated to a particular line and is processed to completion in that line. Also, all jobs allocated to a line are processed in a particular order. The objective of this paper is to find the optimal allocation of jobs to lines and also the optimal order of jobs processed in each line based on individual processing times and set up times. The optimal schedule gives the minimum makespan for the completion of all jobs. The optimization technique used is genetic algorithm.     

柔性工作车间调度问题的多目标优化方法研究

针对各工件日标不同的多目标柔性作业车间调度问题,构建了以加工成本、加工质量及制造工期为目标函数的柔性作业车间调度多日标优化数学模型.针对传统的加权系数遗传算法不能很好地解决柔性作业车间调度多目标优化问题,提出采用改进的强度Pareto进化算法,对柔性作业车间调度问题进行多目标优化,从而得出柔性车间调度问题的Pareto综合最优解.最后,结合项目实施,以某大型空分装备企业的车间调度为例,证明了文中提出的方法能很好地解决柔性工作车间调度的多目标优化问题.     

Pareto archive particle swarm optimization for multi-objective fuzzy job shop scheduling problems

This paper addresses multi-objective job shop scheduling problems with fuzzy processing time and due-date in such a way to provide the decision-maker with a group of Pareto optimal solutions. A new priority rule-based representation method is proposed and the problems are converted into continuous optimization ones to handle the problems by using particle swarm optimization. The conversion is implemented by constructing the corresponding relationship between real vector and the chromosome obtained with the new representation method. Pareto archive particle swarm optimization is proposed, in which the global best position selection is combined with the crowding measure-based archive maintenance, and the inclusion of mutation into the proposed algorithm is considered. The proposed algorithm is applied to eight benchmark problems for the following objectives: the minimum agreement index, the maximum fuzzy completion time and the mean fuzzy completion time. Computational results demonstrate that the proposal algorithm has a promising advantage in fuzzy job shop scheduling.     

A neural network meta-model for identification of optimal combination of priority dispatching rules and makespan in a deterministic job shop scheduling problem

Selection of appropriate priority dispatching rules (PDRs) is a major concern in practical scheduling problems. Earlier research implies that using one PDR does not necessarily yield to an optimal schedule. Hence, this paper puts forward a novel approach based on discrete event simulation (DES) and artificial neural networks (ANNs) to decide on the optimal PDR for each machine from a set of rules so as to minimize the makespan in job shop scheduling problems. Non-identical PDRs are considered for each machine. Indeed, for a given number of machines, all permutations of PDRs are taken into account which could lead to nondeterministic polynomial-time hardness of the problem when the number of machines increases. To address this issue, DES and ANNs are employed as a meta-model. First, the problem is modeled and quite a number of feasible solutions are obtained from DES on its own. Afterward, a back-propagation neural network is developed in accordance with the results of DES to calculate the makespan based on all potential permutations of PDRs. The performance of the proposed approach is investigated through a set of test-bed problems.