A genetic algorithm embedded with a concise chromosome representation for distributed and flexible job-shop scheduling problems

This paper proposes a genetic algorithm \(GA\_JS\) for solving distributed and flexible job-shop scheduling (DFJS) problems. A DFJS problem involves three scheduling decisions: (1) job-to-cell assignment, (2) operation-sequencing, and (3) operation-to-machine assignment. Therefore, solving a DFJS problem is essentially a 3-dimensional solution space search problem; each dimension represents a type of decision. The \(GA\_JS\) algorithm is developed by proposing a new and concise chromosome representation \({\varvec{S}}_{{\varvec{JOB}}}\), which models a 3-dimensional scheduling solution by a 1-dimensional scheme (i.e., a sequence of all jobs to be scheduled). That is, the chromosome space is 1-dimensional (1D) and the solution space is 3-dimensional (3D). In \(GA\_JS\), we develop a 1D-to-3D decoding method to convert a 1D chromosome into a 3D solution. In addition, given a 3D solution, we use a refinement method to improve the scheduling performance and subsequently use a 3D-to-1D encoding method to convert the refined 3D solution into a 1D chromosome. The 1D-to-3D decoding method is designed to obtain a “good” 3D solution which tends to be load-balanced. In contrast, the refinement and 3D-to-1D encoding methods of a 3D solution provides a novel way (rather than by genetic operators) to generate new chromosomes, which are herein called shadow chromosomes. Numerical experiments indicate that \(GA\_JS\) outperforms the IGA developed by De Giovanni and Pezzella (Eur J Oper Res 200:395–408, 2010), which is the up-to-date best-performing genetic algorithm in solving DFJS problems.     

A modified genetic algorithm with fuzzy roulette wheel selection for job-shop scheduling problems

The job-shop scheduling problem is one of the most difficult production planning problems. Since it is in the NP-hard class, a recent trend in solving the job-shop scheduling problem is shifting towards the use of heuristic and metaheuristic algorithms. This paper proposes a novel metaheuristic algorithm, which is a modification of the genetic algorithm. This proposed algorithm introduces two new concepts to the standard genetic algorithm: (1) fuzzy roulette wheel selection and (2) the mutation operation with tabu list. The proposed algorithm has been evaluated and compared with several state-of-the-art algorithms in the literature. The experimental results on 53 JSSPs show that the proposed algorithm is very effective in solving the combinatorial optimization problems. It outperforms all state-of-the-art algorithms on all benchmark problems in terms of the ability to achieve the optimal solution and the computational time.     

A machine-order search space for job-shop scheduling problems

This paper proposes a methodology for real‐time job‐shop scheduling problems. It introduces a new classification of the scheduling methods for JSSPs with emphasis on the search methods and the significance of the search space. Subsequently, a machine‐order search space is proposed as a new framework in which different single‐machine scheduling algorithms and search methods can be incorporated to solve JSSPs. An optimization model relating makespan minimization and the proposed machine‐order search space is also described. The proposed methodology finds an optimal solution by searching a proper machine order in the machine‐order search space and scheduling the machines one by one in this order. Such an approach significantly reduces the size of the search space, and hence the computing efforts. As a result, scheduling of large JSSPs in real‐time becomes practicable.     

Deterministic job-shop scheduling problems with capacity focus

In this paper a main point of view is the exhausting of capacity in relation to a capacity focus at every node of the production graph. This exhausting process has a local and a global aspect. Optimality means a homogeneous reservation of the production nets and exhaustion of the capacity in the nodes close to the focus. Under weak conditions an optimal production sequence is achievable constructively. A classical field of application of this result is the assembly, but many other applications are possible.     

柔性作业车间调度中的组合遗传优化研究

针对柔性作业车间调度问题,提出一种组合遗传算法。该算法在种群初始化、选择、交叉、变异各阶段,组合使用各种不同的策略。针对机器编码部分的交叉,提出一种基于工件的机器交叉算子,用以改进机器分配部分随机交叉引起的对父代优秀基因继承不足的缺陷。通过对典型算例的计算以及与其他文献的研究成果比较,证明该算法的优良性能。     

一种求解车间调度问题的混沌遗传规划方法

作业车间调度问题是制造业的一个经典NP-hard组合优化难题。提出一种基于混沌遗传规划的调度算法,利用遗传规划进行染色体的结构设计,采用混沌序列改善初始种群质量,利用混沌扰动来维持进化群体的多样性,并自适应调整个体权重,使算法具有优良的综合求解性能。实验表明,算法对典型的标准调度测试问题具有较强的全局搜索能力,甘特图表明其获得的最优解优于当前已知的最优解历史记录,对比结果表明了该方法的有效性。     

求解作业车间调度问题的微粒群遗传退火算法

标准微粒群算法（PSO）通常被用于求解连续优化的问题,很少被用于离散问题的优化求解,如作业车间调度问题（JSP）。因此,针对PSO算法易早熟、收敛慢等缺点提出一种求解作业车间调度问题（JSP）的混合微粒群算法。算法将微粒群算法、遗传算法（GA）、模拟退火（SA）算法相结合,既增强了算法的局部搜索能力,降低了算法对参数的依赖,同时改善了PSO算法和GA算法易早熟的缺点。对经典JSP问题的仿真实验表明：与标准微粒群算法相比,该算法不仅能有效避免算法中的早熟问题,并且算法的全局收敛性得到了显著提高。     

An efficient search method for job-shop scheduling problems

We present an efficient search method for job-shop scheduling problems. Our technique is based on an innovative way of relaxing and subsequently reimposing the capacity constraints on some critical operations. We integrate this technique into a fast tabu search algorithm. Our computational results on benchmark problems show that this approach is very effective. Upper bounds for 11 well-known test problems are thus improved. Through the work presented We hope to move a step closer to the ultimate vision of an automated system for generating optimal or near-optimal production schedules. The peripheral conditions for such a system are ripe with the increasingly widespread adoption of enterprise information systems and plant floor tracking systems based on bar code or wireless technologies. One of the remaining obstacles, however, is the fact that scheduling problems arising from many production environments, including job-shops, are extremely difficult to solve. Motivated by recent success of local search methods in solving the job-shop scheduling problem, we propose a new diversification technique based on relaxing and subsequently reimposing the capacity constraints on some critical operations. We integrate this technique into a fast tabu search algorithm and are able to demonstrate its effectiveness through extensive computational experiments. In future research, we will consider other diversification techniques that are not restricted to critical operations.     

生物地理学算法求解柔性车间作业调度问题

针对加工设备和操作工人双资源约束的柔性作业车间调度问题,建立以生产时间和生产成本为目标函数的柔性作业车间调度模型,提出基于模糊Pareto支配的生物地理学算法,采用模糊Pareto支配的方法计算解之间的支配关系并对Pareto解集排序,进行全局最优值的更新,并采用余弦迁移模型来改善生物地理学算法的收敛速度。将该方法应用于某模具车间的柔性作业车间调度中,仿真结果验证了该方法的可行性和有效性。     

An efficient genetic algorithm for job-shop scheduling problems with fuzzy processing time and fuzzy duedate

In this paper, by considering the imprecise or fuzzy nature of the data in real-world problems, job-shop scheduling problems with fuzzy processing time and fuzzy duedate are formulated and a genetic algorithm which is suitable for solving the formulated problems is proposed. On the basis of the agreement index of fuzzy duedate and fuzzy completion time, the formulated fuzzy job-shop scheduling problems are interpreted so as to maximize the minimum agreement index. For solving the formulated fuzzy job-shop scheduling problems, an efficient genetic algorithm is proposed by incorporating the concept of similarity among individuals into the genetic algorithms using the Gannt chart. As illustrative numerical examples, both 6×6 and 10×10 job-shop scheduling problems with fuzzy duedate and fuzzy processing time are considered. Through the comparative simulations with simulated annealing, the feasibility and effectiveness of the proposed method are demonstrated.     

An effective hybrid optimization strategy for job-shop scheduling problems

Simulated annealing is a naturally serial algorithm, but its behavior can be controlled by the cooling schedule. Genetic algorithm exhibits implicit parallelism and can retain useful redundant information about what is learned from previous searches by its representation in individuals in the population, but GA may lose solutions and substructures due to the disruptive effects of genetic operators and is not easy to regulate GA's convergence. By reasonably combining these two global probabilistic search algorithms, we develop a general, parallel and easily implemented hybrid optimization framework, and apply it to job-shop scheduling problems. Based on effective encoding scheme and some specific optimization operators, some benchmark job-shop scheduling problems are well solved by the hybrid optimization strategy, and the results are competitive with the best literature results. Besides the effectiveness and robustness of the hybrid strategy, the combination of different search mechanisms and structures can relax the parameter-dependence of GA and SA.Scope and purposeJob-shop scheduling problem (JSP) is one of the most well-known machine scheduling problems and one of the strongly NP-hard combinatorial optimization problems. Developing effective search methods is always an important and valuable work. The scope and purpose of this paper is to present a parallel and easily implemented hybrid optimization framework, which reasonably combines genetic algorithm with simulated annealing. Based on effective encoding scheme and some specific optimization operators, the job-shop scheduling problems are well solved by the hybrid optimization strategy.     

A genetic algorithm and the Monte Carlo method for stochastic job-shop scheduling

This paper proposes a method for solving stochastic job‐shop scheduling problems using a hybrid of a genetic algorithm in uncertain environments and the Monte Carlo method. First, the genetic algorithm in uncertain environments is applied to stochastic job‐shop scheduling problems where the processing times are treated as stochastic variables. The Roulette strategy is adopted for selecting the optimum solution having the minimum expected value for makespan. Applying crossover based on Giffler and Thompson's algorithm results in two offspring inheriting the ancestor's characteristics as the operation completion times averaged up to the parent's generation. Individuals having very high frequency through all generations are selected as the good solutions. Second, the Monte Carlo method is effectively used for finding out the approximately optimum solution among these good solutions.     

A controlled genetic algorithm by fuzzy logic and belief functionsfor job-shop scheduling

Most scheduling problems are highly complex combinatorial problems. However, stochastic methods such as genetic algorithm yield good solutions. In this paper, we present a controlled genetic algorithm (CGA) based on fuzzy logic and belief functions to solve job-shop scheduling problems. For better performance, we propose an efficient representational scheme, heuristic rules for creating the initial population, and a new methodology for mixing and computing genetic operator probabilities.     

Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems

We solve the multi-objective flexible job-shop problems by using dispatching rules discovered through genetic programming. While Simple Priority Rules have been widely applied in practice, their efficacy remains poor due to lack of a global view. Composite dispatching rules have been shown to be more effective as they are constructed through human experience. In this paper, we evaluate and employ suitable parameter and operator spaces for evolving composite dispatching rules using genetic programming, with an aim towards greater scalability and flexibility. Experimental results show that composite dispatching rules generated by our genetic programming framework outperforms the single dispatching rules and composite dispatching rules selected from literature over five large validation sets with respect to minimum makespan, mean tardiness, and mean flow time objectives. Further results on sensitivity to changes (in coefficient values and terminals among the evolved rules) indicate that their designs are robust.     

Approaches to modeling train scheduling problems as job-shop problems with blocking constraints

The problem of scheduling a set of trains traveling through a given railway network consisting of single tracks, sidings and stations is considered. For every train a fixed route and travel times, an earliest departure time at the origin and a desired arrival time at the destination are given. A feasible schedule has to be determined which minimizes total tardiness of all trains at their destinations. This train scheduling problem is modeled as a job-shop scheduling problem with blocking constraints, where jobs represent trains and machines constitute tracks or track sections. Four MIP formulations without time-indexed variables are developed based on two different transformation approaches of parallel tracks and two different types of decision variables leading to job-shop scheduling problems with or without routing flexibility. A computational study is made on hard instances with up to 20 jobs and 11 machines to compare the MIP models in terms of total tardiness values, formulation size and computation time.     

Investigation of Ant System parameter interactions by using design of experiments for job-shop scheduling problems

In recent years, one of the most important and promising research fields has been metaheuristics to find optimal or near-optimal solutions for NP-hard combinatorial optimization problems. Improving the quality of the solution or the solution time is basic research area on metaheuristics. Modifications of the existing ones or creation of hybrid approaches are the focus of these efforts. Another area of improving the solution quality of metaheuristics is finding the optimal combination of algorithm control parameters. This is usually done by design of experiments or one-at-a-time approach in genetic algorithms, simulated annealing and similar metaheuristics. We observe that, in studies which use Ant Colonies Optimization (ACO) as an optimization technique; the levels of control parameters are determined by some non-systematic initial experiments and the interactions of the parameters are not studied yet.In this study, the parameters of Ant System have been investigated on different sized and randomly generated job-shop scheduling problems by using design of experiments. The effects and interactions of the parameters have been interpreted with the outputs of the experiments. Referring to the statistical analysis it is observed that none of the interactions between the Ant System parameters has a significant effect on makespan value. A specific fractional experimental design is suggested instead of the full factorial design. Depending on the findings from the benchmark problems it will be a reliable approach to use the suggested design for saving time and effort in experiments without sacrificing the solution quality.     

An effective genetic algorithm for the flexible job-shop scheduling problem

In this paper, we proposed an effective genetic algorithm for solving the flexible job-shop scheduling problem (FJSP) to minimize makespan time. In the proposed algorithm, Global Selection (GS) and Local Selection (LS) are designed to generate high-quality initial population in the initialization stage. An improved chromosome representation is used to conveniently represent a solution of the FJSP, and different strategies for crossover and mutation operator are adopted. Various benchmark data taken from literature are tested. Computational results prove the proposed genetic algorithm effective and efficient for solving flexible job-shop scheduling problem.     

协同混合粒子群算法求解车间作业调度问题

针对如何有效解决车间作业优化调度问题,提出一种协同粒子群和引力搜索的混合算法。新算法在粒子群算法进化停滞时引入引力搜索算法,利用引力搜索算法进化后期快速寻优的能力,及时跳出局部最优,保证全局最优。同时采用协同原理简化算法结构,提高算法收敛速度。将提出算法对车间作业调度典型测试用例进行仿真,仿真结果表明该算法较PSO和GA等算法在求解车间作业调度问题上更具优越性。     

A neural network approach to job-shop scheduling

A novel analog computational network is presented for solving NP-complete constraint satisfaction problems, i.e. job-shop scheduling. In contrast to most neural approaches to combinatorial optimization based on quadratic energy cost function, the authors propose to use linear cost functions. As a result, the network complexity (number of neurons and the number of resistive interconnections) grows only linearly with problem size, and large-scale implementations become possible. The proposed approach is related to the linear programming network described by D.W. Tank and J.J. Hopfield (1985), which also uses a linear cost function for a simple optimization problem. It is shown how to map a difficult constraint-satisfaction problem onto a simple neural net in which the number of neural processors equals the number of subjobs (operations) and the number of interconnections grows linearly with the total number of operations. Simulations show that the authors' approach produces better solutions than existing neural approaches to job-shop scheduling, i.e. the traveling salesman problem-type Hopfield approach and integer linear programming approach of J.P.S. Foo and Y. Takefuji (1988), in terms of the quality of the solution and the network complexity.