A hybrid genetic algorithm for the job shop scheduling problems

The Job Shop Scheduling Problem (JSSP) is one of the most general and difficult of all traditional scheduling problems. The goal of this research is to develop an efficient scheduling method based on genetic algorithm to address JSSP. We design a scheduling method based on Single Genetic Algorithm (SGA) and Parallel Genetic Algorithm (PGA). In the scheduling method, the representation, which encodes the job number, is made to be always feasible, the initial population is generated through integrating representation and G&T algorithm, the new genetic operators and selection method are designed to better transmit the temporal relationships in the chromosome, and island model PGA are proposed. The scheduling methods based on genetic algorithm are tested on five standard benchmark JSSP. The results are compared with other proposed approaches. Compared to traditional genetic algorithm, the proposed approach yields significant improvement in solution quality. The superior results indicate the successful incorporation of a method to generate initial population into the genetic operators.     

Approximation algorithms for shop scheduling problems with minsum objective: A correction

We present a correction to the paper, “Approximation algorithms for shop scheduling problems with minsum objective” (Journal of Scheduling 2002; 5:287–305) by Queyranne and Sviridenko. This correction provides a correct derivation of its 2eρ approximation result. Wenhua Li and Jinjiang Yuan: Project supported by NNSFC (Grant 10371112) and NSFHN (Grant 0411011200). Maurice Queyranne: Supported by research grants from NSERC, the Natural Sciences and Engineering Research Council of Canada.     

A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardinessobjective

In modern manufacturing systems, due date related performance is becoming increasingly important in maintaining a high service reputation. However, compared with the extensive research on makespan minimization, research on the total weighted tardiness objective is comparatively scarce, partly because this objective function is more difficult and complex to optimize. In this paper, we focus on the job shop scheduling problem with the objective of minimizing total weighted tardiness. First, we discuss the mathematical programming model and its duality when the processing orders for each machine are fixed. Then, a block-based neighborhood structure is defined and its important properties are shown. Finally, a simulated annealing algorithm is designed which directly utilizes the features of this neighborhood. According to the computational results, the new neighborhood considerably promotes the searching capability of simulated annealing and helps it converge to high-quality solutions.     

一种求解双目标job shop问题的混合进化算法

提出一种求解双目标job shop排序问题的混合进化算法．该算法采用改进的精英复制策略,降低了计算复杂性;通过引入递进进化模式,避免了算法的早熟;通过递进过程中的非劣解邻域搜索,增强了算法局部搜索性能．采用该算法和代表性算法NSGA-Ⅱ,MOGLS对82个标准双目标job shop算例进行优化对比,所得结果验证了该算法求解双目标job shop排序问题的有效性．     

相关工件车间调度问题的拓扑算法

针对加工装配型离散制造企业实际生产的特点,提出了一类用于表示工序之间偏序关系的相关工件车间调度问题。为了利用已有的求解表示工序之间的线序关系的传统车间调度算法求解相关工件车间调度问题,设计了一种拓扑算法,该算法能够将工序之间的偏序关系转化为线序关系,将相关工件车间调度问题转化为传统的车间调度问题,通过实证研究,结果表明了拓扑算法是可行和高效的。     

A hybrid immune simulated annealing algorithm for the job shop scheduling problem

A hybrid simulated annealing algorithm based on a novel immune mechanism is proposed for the job shop scheduling problem with the objective of minimizing total weighted tardiness. The proposed immune procedure is built on the following fundamental idea: the bottleneck jobs existing in each scheduling instance generally constitute the key factors in the attempt to improve the quality of final schedules, and thus, the sequencing of these jobs needs more intensive optimization. To quantitatively describe the bottleneck job distribution, we design a fuzzy inference system for evaluating the bottleneck level (i.e. the criticality) of each job. By combining the immune procedure with a simulated annealing algorithm, we design a hybrid optimization algorithm which is subsequently tested on a number of job shop instances. Computational results for different-sized instances show that the proposed hybrid algorithm performs effectively and converges fast to satisfactory solutions.     

A new hybrid genetic algorithm for job shop scheduling problem

Job shop scheduling problem is a typical NP-hard problem. To solve the job shop scheduling problem more effectively, some genetic operators were designed in this paper. In order to increase the diversity of the population, a mixed selection operator based on the fitness value and the concentration value was given. To make full use of the characteristics of the problem itself, new crossover operator based on the machine and mutation operator based on the critical path were specifically designed. To find the critical path, a new algorithm to find the critical path from schedule was presented. Furthermore, a local search operator was designed, which can improve the local search ability of GA greatly. Based on all these, a hybrid genetic algorithm was proposed and its convergence was proved. The computer simulations were made on a set of benchmark problems and the results demonstrated the effectiveness of the proposed algorithm.     

Integrating simulation and genetic algorithm to schedule a dynamic flexible job shop

Much of the research on operations scheduling problems has ignored dynamic events in real-world environments where there are complex constraints and a variety of unexpected disruptions. Besides, while most scheduling problems which have been discussed in the literature assume that machines are incessantly available, in most real life industries a machine can be unavailable for many reasons, such as unanticipated breakdowns (stochastic unavailability), or due to a scheduled preventive maintenance where the periods of unavailability are determined in advance (deterministic unavailability). This paper describes how we can integrate simulation into genetic algorithm to the dynamic scheduling of a flexible job shop with machines that suffer stochastic breakdowns. The objectives are the minimization of two criteria, expected makespan and expected mean tardiness. An overview of the flexible job shops and scheduling under the stochastic unavailability of machines are presented. Subsequently, the details of integrating simulation into genetic algorithm are described and implemented. Consequently, problems of various sizes are used to test the performance of the proposed algorithm. The results obtained reveal that the relative performance of the algorithm for both abovementioned objectives can be affected by changing the levels of the breakdown parameters.     

基于新型帝国竞争算法的高维多目标柔性作业车间调度

针对高维多目标柔性作业车间调度问题(MaOFJSP),提出了一种新型帝国竞争算法(ICA)以同时最小化最大完成时间、最大拖期、最大机器负荷和总能耗,该算法采用新方法构建初始帝国使得大多数殖民国家分配数量相近的殖民地,引入殖民国家的同化,并应用新的革命策略和帝国竞争方法以获得高质量解.最后通过大量实验测试ICA新策略对其性能的影响并将ICA与其他算法对比,实验结果表明新型ICA在求解MaOFJSP方面具有较强的优势.     

柔性作业调度的串并行模型对比与求解

作业处理中的柔性使得作业调度更为灵活,作业中操作的执行顺序满足拓扑排序是作业调度的前提。是否允许没有优先关系的操作在不同的机器上同时执行是区分串行和并行调度的条件。文中以共生进化算法求解一个复杂的作业调度模型为例,给出了算法实现串行调度和并行调度的具体区别,并给出了串行和并行调度的结果。结果表明,并行相对于串行对算法效率的提高与柔性大小相关,与作业的规模成反比。     

A two-stage-priority-rule-based algorithm for robust resource-constrained project scheduling

Traditionally, the resource-constrained project scheduling problem (RCPSP) is modeled as a static and deterministic problem and is solved with the objective of makespan minimization. However, many uncertainties, such as unpredictable increases in processing times caused by rework or supplier delays, random transportation and/or setup, may render the proposed solution obsolete. In this paper, we present a two-stage algorithm for robust resource-constrained project scheduling. The first stage of the algorithm solves the RCPSP for minimizing the makespan only using a priority-rule-based heuristic, namely an enhanced multi-pass random-biased serial schedule generation scheme. The problem is then similarly solved for maximizing the schedule robustness while considering the makespan obtained in the first stage as an acceptance threshold. Selection of the best schedule in this phase is based on one out of 12 alternative robustness predictive indicators formulated for the maximization purpose. Extensive simulation testing of the generated schedules provides strong evidence of the benefits of considering robustness of the schedules in addition to their makespans. For illustration purposes, for 10 problems from the well-known standard set J30, both robust and non-robust schedules are executed with a 10% duration increase that is applied to the same randomly picked 20% of the project activities. Over 1000 iterations per instance problem, the robust schedules display a shorter makespan in 55% of the times while the non-robust schedules are shown to be the best performing ones in only 6% of the times.     

Scheduling a dynamic job shop production system with sequence-dependent setups: An experimental study

This paper presents the salient aspects of a simulation-based experimental study of scheduling rules for scheduling a dynamic job shop in which the setup times are sequence dependent. A discrete event simulation model of the job shop system is developed for the purpose of experimentation. Seven scheduling rules from the literature are incorporated in the simulation model. Five new setup-oriented scheduling rules are proposed and implemented. Simulation experiments have been conducted under various experimental conditions characterized by factors such as shop load, setup time ratios and due date tightness. The results indicate that setup-oriented rules provide better performance than ordinary rules. The difference in performance between these two groups of rules increases with increase in shop load and setup time ratio. One of the proposed rules performs better for mean flow time and mean tardiness measures.     

基于改进粒子群算法求解柔性作业车间批量调度问题

基于工序排序和机器分配的粒子编码方式,提出一种新的粒子位置更新方式,该方式使得粒子群算法更新可以直接在离散域执行.通过对工件工序进行多次机器分配来扩大搜索范围,引入改进的模拟退火算法,用以增强粒子群算法的邻域搜索能力,实现全局搜索与局部搜索能力的有效平衡.最后通过数值算例以及某电声企业纸盆车间批量调度的应用实例验证了所提出算法的有效性和可行性.     

精英进化策略求解柔性作业车间调度问题

柔性作业车间调度问题允许一道工序可以在多个可选机器上进行加工,减少了机器约束,增加了求解难度,是典型的NP难问题。结合其特点,设计了一种精英进化策略遗传算法求解柔性作业车间调度问题。提出了解阀值的指标,使得外部精英库中不仅保留算法每次迭代过程中的最优解,而且保留最优值相等而调度方案不同的解,为调度人员提供更多选择。通过制造企业中的实际案例和其它文献中的案例对提出的精英进化策略遗传算法进行了测试,结果证明提出方法的有效性。     

A double-module immune algorithm for multi-objective optimization problems

Multi-objective optimization problems (MOPs) have become a research hotspot, as they are commonly encountered in scientific and engineering applications. When solving some complex MOPs, it is quite difficult to locate the entire Pareto-optimal front. To better settle this problem, a novel double-module immune algorithm named DMMO is presented, where two evolutionary modules are embedded to simultaneously improve the convergence speed and population diversity. The first module is designed to optimize each objective independently by using a sub-population composed with the competitive individuals in this objective. Differential evolution crossover is performed here to enhance the corresponding objective. The second one follows the traditional procedures of immune algorithm, where proportional cloning, recombination and hyper-mutation operators are operated to concurrently strengthen the multiple objectives. The performance of DMMO is validated by 16 benchmark problems, and further compared with several multi-objective algorithms, such as NSGA-II, SPEA2, SMSEMOA, MOEA/D, SMPSO, NNIA and MIMO. Experimental studies indicate that DMMO performs better than the compared targets on most of test problems and the advantages of double modules in DMMO are also analyzed.     

求解有限产能作业车间调度的改进蚂蚁算法

通过对有限产能车间调度问题的分析,提出了基于蚂蚁算法求解该问题的方法。在模型的构建中增加了成本和机器负荷约束。通过产品的BOM表采用蚂蚁算法搜寻节点,做各阶层工序安排,将各阶层工序安排组合成一完整解。对蚂蚁算法进行了改进,在基本蚂蚁算法的基础上,通过修改信息素局域更新规则和全局更新规则,引入自适应信息素挥发系数来提高算法的收敛速度和全局最优解搜索能力。算例分析表明,蚂蚁的正向反馈及探索功能对求解较大工件数的生产计划非常有效。而且在有限产能的环境中根据产能负荷状况产生不同的外包组合,将满足交货期的各种外包组合成本做敏感性分析,供决策者参考。     

A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems

This paper addresses the flexible job shop scheduling problem (fJSP) with three objectives: min makespan, min maximal machine workload and min total workload. We developed a hybrid genetic algorithm (GA) for the problem. The GA uses two vectors to represent solutions. Advanced crossover and mutation operators are used to adapt to the special chromosome structure and the characteristics of the problem. In order to strengthen the search ability, individuals of GA are first improved by a variable neighborhood descent (VND), which involves two local search procedures: local search of moving one operation and local search of moving two operations. Moving an operation is to delete the operation, find an assignable time interval for it, and allocate it in the assignable interval. We developed an efficient method to find assignable time intervals for the deleted operations based on the concept of earliest and latest event time. The local optima of moving one operation are further improved by moving two operations simultaneously. An extensive computational study on 181 benchmark problems shows the performance of our approach.     

A novel hybrid meta-heuristic algorithm for solving multi objective flexible job shop scheduling

Finding feasible scheduling that optimize all objective functions for flexible job shop scheduling problem (FJSP) is considered by many researchers. In this paper, the novel hybrid genetic algorithm and simulated annealing (NHGASA) is introduced to solve FJSP. The NHGASA is a combination of genetic algorithm and simulated annealing to propose the algorithm that is more efficient than others. The three objective functions in this paper are: minimize the maximum completion time of all the operations (makespan), minimize the workload of the most loaded machine and minimize the total workload of all machines. Pareto optimal solution approach is used in NHGASA for solving FJSP. Contrary to the other methods that assign weights to all objective functions to reduce them to one objective function, in the NHGASA and during all steps, problems are solved by three objectives. Experimental results prove that the NHGASA that uses Pareto optimal solutions for solving multi-objective FJSP overcome previous methods for solving the same benchmarks in the shorter computational time and higher quality.     

An efficient memetic algorithm for solving the job shop scheduling problem

The job shop scheduling problem (JSP) is well known as one of the most complicated combinatorial optimization problems, and it is a NP-hard problem. Memetic algorithm (MA) which combines the global search and local search is a hybrid evolutionary algorithm. In this paper, an efficient MA with a novel local search is proposed to solve the JSP. Within the local search, a systematic change of the neighborhood is carried out to avoid trapping into local optimal. And two neighborhood structures are designed by exchanging and inserting based on the critical path. The objective of minimizing makespan is considered while satisfying a number of hard constraints. The computational results obtained in experiments demonstrate that the efficiency of the proposed MA is significantly superior to the other reported approaches in the literature.     

Two-stage hybrid flow shop scheduling with dynamic job arrivals

Motivated by applications in semiconductor manufacturing industry, we consider a two-stage hybrid flow shop where a discrete machine is followed by a batching machine. In this paper, we analyze the computational complexity of a class of two-machine problems with dynamic job arrivals. For the problems belonging to P we present polynomial algorithms. For the NP-complete problems we propose the heuristics, and then establish the upper bounds on the worst case performance ratios of the heuristics. In addition, we give the improved heuristics that can achieve better performances.