A mathematical model for integrating lot-sizing and scheduling problem in capacitated flow shop environments

In this paper, a multiproduct multiperiod capacitated production system that has been organized as a flow shop is considered. The main novelty of the paper is proposing a more efficient mathematical model for the problem of integrating lot sizing and scheduling with sequence-dependent setups. In comparison to the former model, because of fewer continuous and binary decision variables and constraints in the proposed model, this model is very easier to solve. Comparison between two models proves the superiority of the proposed model. Two mixed integer programming-based approaches with rolling horizon framework have been used to solve this model. To evaluate the performance of the proposed model and solution method, problems of different scales have been studied. The used algorithms search the solution space for both lot-sizing and scheduling problems and find a combination of production planning and scheduling that is feasible and close to optimum.     

采用多个体交叉的遗传算法求解作业车间问题

为改善目前求解Job-Shop问题中的遗传算法的性能,加快搜索最优调度解的速度,首先分析了目前Job-Shop问题自身的求解难点和遗传算法的特点,并借鉴生物学的依据,提出了多个体交叉的遗传算法。该算法在遗传过程中采用多个体遗传算子,充分利用个体的优良性质,对不可行调度解根据多个体修补原则进行修正,可保证遗传后代的合法性和多样性,能够加快最优调度解的搜索时间。仿真结果充分证明了该算法的有效性。     

新型混合改进遗传算法求解零等待流水车间调度问题

具有零等待约束条件的流水车间调度问题是一类典型的NP难问题,针对该问题提出一种新型混合改进遗传算法进行优化求解.首先,采用改进NEH算法强化初始种群质量,提高种群的多样性.结合关联规则理论挖掘种群中的优势块,借助优势块进行人工染色体组合,以降低问题复杂度.交叉操作采用单段交叉、双段交叉和三段交叉3种交叉机制,改善算法全...     

A novel hybrid genetic algorithm for the open shop scheduling problem

In this paper, a hybrid genetic algorithm is proposed for the open shop scheduling problem with the objective of minimizing the makespan. In the proposed algorithm, a specialized crossover operator is used that preserves the relative order of jobs on machines and a strategy is applied to prevent from searching redundant solutions in the mutation operator. Moreover, an iterative optimization heuristic is employed which uses the concept of randomized active schedules, a dispatching index based on the longest remaining processing time rule and a lower bound to further decrease the search space. Computational results show that the proposed algorithm outperforms other genetic algorithms and is very competitive with well-known metaheuristics available in the literature.     

A class of order-based genetic algorithm for flow shop scheduling

A class of order-based genetic algorithm is presented for flow shop scheduling that is a typical NP-hard combinatorial optimisation problem with a strong engineering background. The proposed order-based genetic algorithm borrows from the idea of ordinal optimisation to ensure the quality of the solution found with a reduction in computation effort and applies the evolutionary searching mechanism and learning capability of genetic algorithms to effectively perform exploration and exploitation. Under the guidance of ordinal optimisation and with an emphasis on order-based searching and elitist-based evolution in the proposed approach, a solution that is "good enough" can be guaranteed with a high confidence level and reduced level of computation. The effectiveness of the proposed algorithm is demonstrated by numerical simulation results based on benchmarks, and its optimisation quality is much better than that of the classic genetic algorithm, the well-known NEH heuristic, as well as being better than a pure blind search. Moreover, the effects of some parameters on optimisation performance are discussed.     

求解作业车间调度问题的多种群杂交遗传算法

提出了多种群杂交改进遗传算法,在约束条件处理中引入可能解空间概念;设计了机床编号可变的基于工序的编码。父代个体和交叉变异得到的个体在选择操作中具有同等选择机会,保证最优个体保留到下一代,又能保持子代的多样性。在遗传过程中引入修正种群,实现多种群杂交,以保持种群的多样性。应用实例分析和工程实践表明,算法稳定可靠,运行效率大大提高。     

求解流水车间调度问题的瓶颈指向启发式算法

针对最小化时间表长的流水车间调度问题,提出一种根据工件加工时间特征构建工件调度的瓶颈指向启发式算法。首先,为构建初始工件排序,充分利用各机器负荷一般不相等的特点,瓶颈阶段前加工时间较短而之后加工时间相对较长的工件优先开始加工;其次,当有工件等待加工时,根据工件在瓶颈机器前或后加工时间的特征调整工件加工顺序;最后,采用邻近工件成对交换和插入的方式改进初始调度。当瓶颈机器趋于中间阶段,或瓶颈机器上工件的加工时间趋于增加时,求解效果较好。数据实验表明算法是有效的。     

求解同顺序加工调度问题的一种启发式方法

为了更加有效地求解同顺序加工调度问题,分析了现有启发式求解方法,发现影响解的质量的主要因素是调整近似解的方法和初始解,其中调整近似解的方法对解的质量影响较大。对此,提出了一种新的启发式方法。新方法中的调整方法考虑了调整对最短总加工时间的影响,调整任意给定的近似解不会降低解的质量,经过迭代运算,可以逐步改善近似解;新方法采用了多起点策略,利用调整方法调整不同初始解,选取最好的近似解作为问题的解,从而减小了初始解对问题解的质量的影响。实验结果表明,这种方法是有效的。     

An effective hybrid genetic algorithm for the job shop scheduling problem

From the computational point of view, the job shop scheduling problem (JSP) is one of the most notoriously intractable NP-hard optimization problems. This paper applies an effective hybrid genetic algorithm for the JSP. We proposed three novel features for this algorithm to solve the JSP. Firstly, a new full active schedule (FAS) procedure based on the operation-based representation is presented to construct a schedule. After a schedule is obtained, a local search heuristic is applied to improve the solution. Secondly, a new crossover operator, called the precedence operation crossover (POX), is proposed for the operation-based representation, which can preserve the meaningful characteristics of the previous generation. Thirdly, in order to reduce the disruptive effects of genetic operators, the approach of an improved generation alteration model is introduced. The proposed approaches are tested on some standard instances and compared with other approaches. The superior results validate the effectiveness of the proposed algorithm.     

A mathematical model and extension algorithm for assembly flexible flow shop scheduling problem

In this paper, a scheduling problem for a two-stage production system including machining operations and assembly operations is studied. In this system, a number of products of different kinds are produced. Each product is assembled with a set of several parts. The first stage is a hybrid flow shop to produce parts. All machines can process all kinds of parts in this stage, but each machine can process only one part at a time. The second stage is a single assembly machine or a single assembly team of workers. The considered objective is to minimize the completion time of all products (makespan). A mathematical modeling is presented, and since this problem has been proved strongly nondeterministic polynomial-time hard, a series of heuristic algorithms based on the basic idea of Johnson algorithm is proposed. Also, two lower bounds is introduced and improved to evaluate the final solution obtained from heuristic algorithms. The numerical experiments are used to evaluate the performance of the proposed algorithms.     

基于改进遗传算法的车间调度问题求解

针对车间调度问题(Job Shop Problem,JSP)的特点,提出一种改进遗传算法。该方法利用剩余作业时间最多(MostWork Remaining,MWR)的工件优先排列的启发式规则来产生初始种群,并且在进化过程中采用分代交叉算子进行操作来避免算法早熟。通过分析算例结果表明,该改进遗传算法可以在进化初期就得到比较理想的调度方案,而且优化收敛速度快、结果优,更适用于解决车间调度问题。     

A hybrid particle swarm optimization algorithm for a no-wait flow shop scheduling problem with the total flow time

This paper proposes a particle swarm optimization (PSO) algorithm based on memetic algorithm (MA) that hybridizes with a local search method for solving a no-wait flow shop scheduling problem. The main objective is to minimize the total flow time. Within the framework of the proposed algorithm, a local version of PSO with a ring-shape topology structure is used as global search. In addition, a self-organized random immigrant's scheme is extended into our proposed algorithm in order to further enhance its exploration capacity for new peaks in search space. The experimental study over the moving peaks benchmark problem shows that the proposed PSO-based MA is robust. Finally, the analysis of the computational results and conclusion are given.     

Discrete harmony search algorithm for the no-wait flow shop scheduling problem with total flow time criterion

In this paper, a discrete harmony search algorithm (DHS) is developed for solving the no-wait flow shop scheduling problem with the objective to minimize total flowtime. Firstly, a harmony is represented as a discrete job permutation, and a new heuristic based on the well-known NEH method is proposed to initialize the harmony memory. Secondly, a novel pitch adjustment rule is employed in the improvisation to produce a new harmony. Thirdly, a local search is presented and embedded to enhance the algorithm's local exploitation ability. Extensive computational experiments are carried out based on a set of well-known benchmark instances. Computational results and comparison show the effectiveness of the presented DHS algorithm in solving the no-wait flow shop scheduling with total flowtime criterion.     

A new algorithm for determining production schedules when solving the multi-product economic lot sizing problem in flow shops

In this paper, we study the generation of production schedules in the multi-product economic lot sizing problem in flow shops (i.e., the FS-ELSP) under the power-of-two policy. To investigate this problem, we first review the mathematical model for the FS-ELSP and Ouenniche and Boctor’s (O&B’s) heuristic, and we comment that there exist several problems in O&B’s heuristic if we try to use it to generate feasible production schedules for the FS-ELSP. Therefore, we propose two new heuristics, namely, the modified O&B’s heuristic and Huang and Yao’s (H&Y’s) heuristic to improve O&B’s heuristic. To compare the performance of these three heuristics, we randomly generate 500 instances for each of the seven levels of utilization rate from 0.4 to 0.75. Based on our numerical experiments, we conclude that H&Y’s heuristic significantly outperforms O&B’s heuristic and the modified O&B’s heuristic.     

Solving a multi-objective no-wait flow shop scheduling problem with an immune algorithm

Flow shop scheduling problems have gained wide attention both in practical and academic fields. In this paper, we consider a multi-objective no-wait flow shop scheduling problem by minimizing the weighted mean completion time and weighted mean tardiness simultaneously. Since a flow shop scheduling problem has been proved to be NP-hard in a strong sense, an effective immune algorithm (IA) is proposed for searching locally the Pareto-optimal frontier for the given problem. To validate the performance of the proposed algorithm in terms of solution quality and diversity level, various test problems are carried out and the efficiency of the proposed algorithm, based on some comparison metrics, is compared with a prominent multi-objective genetic algorithm, i.e., strength Pareto evolutionary algorithm II (SPEA-II). The computational results show that the proposed IA outperforms the above genetic algorithm, especially for large problems.     

有效的混合粒子群算法求解阻塞流水车间调度问题

针对以最小化完工时间为目标的阻塞流水车间调度问题,提出了一种混合粒子群算法进行求解。该算法将粒子群算法与迭代贪婪算法进行了结合。利用改进的迭代贪婪算法产生问题初始优化解,利用粒子群算法进行全局优化。针对粒子群算法易早熟收敛的特点,提出一种判断粒子停滞和粒子群早熟的方法,并在发现种群早熟后利用迭代贪婪算法的构造操作和毁坏操作对相关粒子进行变异,同时按照一定比例对最差的部分粒子进行重新初始化,以增加种群多样性。通过标准实例测试,验证了所提算法的有效性。     

A hybrid discrete particle swarm optimization algorithm for the no-wait flow shop scheduling problem with makespan criterion

This paper proposes a novel hybrid discrete particle swarm optimization (HDPSO) algorithm to solve the no-wait flow shop scheduling problems with the criterion to minimize the maximum completion time (makespan). Firstly, a simple approach is presented in the paper to calculate the makespan of a job permutation. Secondly, a speed-up method is proposed to evaluate the similar insert neighborhood solution. Thirdly, a discrete particle swarm optimization (DPSO) algorithm based on permutation representation and a local search algorithm based on the insert neighborhood are fused to enhance the searching ability and to balance the exploration and exploitation. Then, computational simulation results based on the well-known benchmarks and statistical performance comparisons are provided. It is concluded that the proposed HDPSO algorithm is superior to both the single DPSO algorithm and the existing hybrid particle swarm optimization (HPSO) algorithm from literature in terms of searching quality, robustness and efficiency.     

An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion

An improved iterated greedy algorithm (IIGA) is proposed in this paper to solve the no-wait flow shop scheduling problem with the objective to minimize the makespan. In the proposed IIGA, firstly, a speed-up method for the insert neighborhood is developed to evaluate the whole insert neighborhood of a single solution with (n???1)² neighbors in time O(n ²), where n is the number of jobs; secondly, an improved Nawaz-Enscore-Ham (NEH) heuristic is presented for constructing solutions in the initial stage and searching process; thirdly, a simple local search algorithm based on the speed-up method is incorporated into the iterated greedy algorithm to perform exploitation. The computational results based on some well-known benchmarks show that the proposed IIGA can obtain results better than those from some existing approaches in the literature.