A heuristic method for two-stage hybrid flow shop with dedicated machines

This paper considers a two-stage hybrid flow shop scheduling problem with dedicated machines, in which the first stage contains a single common critical machine, and the second stage contains several dedicated machines. Each job must be first processed on the critical machine in stage one and depending on the job type, the job will be further processed on the dedicated machine of its type in stage two. The objective is to minimize the makespan. To solve the problem, a heuristic method based on branch and bound (B&B) algorithm is proposed. Several lower bounds are derived and four constructive heuristics are used to obtain initial upper bounds. Then, three dominance properties are employed to enhance the performance of the proposed heuristic method. Extensive computational experiments on two different problem categories each with various problem configurations are conducted. The results show that the proposed heuristic method can produce very close-to-optimal schedules for problems up to 100 jobs and five dedicated machines within 60 s. The comparisons with solutions of two other meta-heuristic methods also prove the better performance of the proposed heuristic method.     

A two-stage hybrid flow shop with dedicated machines at the first stage

This paper considers the problem of minimizing the makespan in a two-stage hybrid flow shop with dedicated machines at stage 1. There exist multiple machines at stage 1 and one machine at stage 2. Each job must be processed on a specified machine at stage 1 depending on job type, and then the job is processed on the single machine at stage 2.     

A simulated annealing algorithm approach to hybrid flow shop scheduling with sequence-dependent setup times

One of the scheduling problems with various applications in industries is hybrid flow shop. In hybrid flow shop, a series of n jobs are processed at a series of g workshops with several parallel machines in each workshop. To simplify the model construction in most research on hybrid flow shop scheduling problems, the setup times of operations have been ignored, combined with their corresponding processing times, or considered non sequence-dependent. However, in most real industries such as chemical, textile, metallurgical, printed circuit board, and automobile manufacturing, hybrid flow shop problems have sequence-dependent setup times (SDST). In this research, the problem of SDST hybrid flow shop scheduling with parallel identical machines to minimize the makespan is studied. A novel simulated annealing (NSA) algorithm is developed to produce a reasonable manufacturing schedule within an acceptable computational time. In this study, the proposed NSA uses a well combination of two moving operators for generating new solutions. The obtained results are compared with those computed by Random Key Genetic Algorithm (RKGA) and Immune Algorithm (IA) which are proposed previously. The results show that NSA outperforms both RKGA and IA.     

Minimizing total completion time in two-stage hybrid flow shop with dedicated machines

We consider the problem of minimizing total completion time in a two-stage hybrid flow shop scheduling problem with dedicated machines at stage 2. There exist one machine at stage 1 and two machines at stage 2. Each job must be processed on the single machine at stage 1 and depending upon the job type, the job is processed on either of the two machines at stage 2.     

Solving two-stage hybrid flow shop using climbing depth-bounded discrepancy search

This paper investigates how to adapt a discrepancy-based search method to solve two-stage hybrid flowshop scheduling problems in which each stage consists of several identical machines operating in parallel. The objective is to determine a schedule that minimizes the makespan. We present an adaptation of the Climbing Depth-bounded Discrepancy Search (CDDS) method based on Johnson’s rule and on dedicated lower bounds for the two-stage hybrid flow shop problem. We report the results of extensive computational experiments, which show that the proposed adaptation of the CDDS method solves instances in restrained CPU time and with high quality of makespan.     

Minimizing total completion time in a two-stage hybrid flow shop with dedicated machines at the first stage

This paper considers a two-stage hybrid flow shop scheduling with dedicated machines at stage 1 with the objective of minimizing the total completion time. There exist two machines at stage 1 and one machine at stage 2. Each job must be processed on one of the two dedicated machines at stage 1 depending on the job type; subsequently, the job is processed on the single machine at stage 2.First, we introduce the problem and establish the complexity of the problem. For a special case in which the processing times on the machine at stage 2 are identical, an optimal solution is presented; for three special cases, we show that the decision version is unary NP-complete. For the general case, two simple and intuitive heuristics are introduced, and a worst case bound on the relative error is found for each of the heuristics. Finally, we empirically evaluate the heuristics, including an optimal algorithm for a special case.     

Scheduling of multi-component products in a two-stage flexible flow shop

In this research, the problem of scheduling and sequencing of two-stage assembly-type flexible flow shop with dedicated assembly lines, which produce different products according to requested demand during the planning horizon with the aim of minimizing maximum completion time of products is investigated. The first stage consists of several parallel machines in site I with different speeds in processing components and one machine in site II, and the second stage consists of two dedicated assembly lines. Each product requires several kinds of components with different sizes. Each component has its own structure which leading to difference processing times to assemble. Products composed of only single-process components are assigned to the first assembly line and products composed of at least a two-process component are assigned to the second assembly line. Components are placed on the related dedicated assembly line in the second phase after being completed on the assigned machines in the first phase and final products will be produced by assembling the components. The main contribution of our work is development of a new mathematical model in flexible flow shop scheduling problem and presentation of a new methodology for solving the proposed model. Flexible flow shop problems being an NP-hard problem, therefore we proposed a hybrid meta-heuristic method as a combination of simulated annealing (SA) and imperialist competitive algorithms (ICA). We implement our obtained algorithm and the ones obtained by the LINGO9 software package. Various parameters and operators of the proposed Meta-heuristic algorithm are discussed and calibrated by means of Taguchi statistical technique.     

A neural network model and algorithm for the hybrid flow shop scheduling problem in a dynamic environment

A hybrid flow shop (HFS) is a generalized flow shop with multiple machines in some stages. HFS is fairly common in flexible manufacturing and in process industry. Because manufacturing systems often operate in a stochastic and dynamic environment, dynamic hybrid flow shop scheduling is frequently encountered in practice. This paper proposes a neural network model and algorithm to solve the dynamic hybrid flow shop scheduling problem. In order to obtain training examples for the neural network, we first study, through simulation, the performance of some dispatching rules that have demonstrated effectiveness in the previous related research. The results are then transformed into training examples. The training process is optimized by the delta-bar-delta (DBD) method that can speed up training convergence. The most commonly used dispatching rules are used as benchmarks. Simulation results show that the performance of the neural network approach is much better than that of the traditional dispatching rules.This revised version was published in June 2005 with corrected page numbers.     

Real-time scheduling for reentrant hybrid flow shops: A decision tree based mechanism and its application to a TFT-LCD line

A reentrant hybrid flow shop, typically found in the electronics industry, is an extended system of the ordinary flow shop in such a way that there exist one or more parallel machines at each serial stage and each job has the reentrant product flow, i.e., a job may visit a stage several times. Among the operational issues in reentrant hybrid flow shops, we focus on the scheduling problem that determines the allocation of jobs to the machines at each stage as well as the sequence of the jobs assigned to each machine. Unlike the theoretical approach on reentrant hybrid flow shop scheduling, we suggest a real-time scheduling mechanism with a decision tree when selecting appropriate dispatching rules. The decision tree, one of the commonly used data mining techniques, is adopted to eliminate the computational burden required to carry out simulation runs to select dispatching rules. To illustrate the mechanism suggested in this study, a case study was performed on a thin film transistor-liquid crystal display (TFT-LCD) manufacturing line and the results are reported for various system performance measures.     

Evolutionary algorithms for scheduling m-machine flow shop with lot streaming

This paper addresses the problem of making sequencing and scheduling decisions for n jobs–m-machines flow shops under lot sizing environment. Lot streaming (Lot sizing) is the process of creating sub lots to move the completed portion of a production sub lots to down stream machines. There is a scope for efficient algorithms for scheduling problems in m-machine flow shop with lot streaming. In recent years, much attention is given to heuristics and search techniques. Evolutionary algorithms that belong to search heuristics find more applications in recent research. Genetic algorithm (GA) and hybrid genetic algorithm (HEA) also known as hybrid evolutionary algorithm fall under evolutionary heuristics. On this concern this paper proposes two evolutionary algorithms namely, GA and HEA to evolve best sequence for makespan/total flow time criterion for m-machine flow shop involved with lot streaming and set-up time. The following two algorithms are used to evaluate the performance of the proposed GA and HEA: (i) Baker's algorithm (BA), an optimal solution procedure for two-machine flow shop problem with lot streaming and makespan objective criterion and (ii) simulated annealing algorithm (SA) for m-machine flow shop problem with lot streaming and makespan and total flow time criteria.     

带工序跳跃的绿色混合流水车间机器与AGV联合调度

针对带工序跳跃的绿色混合流水车间机器和自动引导车(AGV)联合调度问题,提出改进memetic algorithm (MA)以同时最小化最大完工时间和总能耗.首先,设计基于工序、机器和转速的三层编码策略,最大程度保证算法在整个解空间中搜索;然后,设计混合种群初始化方法以提高初始种群解的质量,同时设计交叉和变异算子以及两种基于问题的邻域搜索策略来平衡算法的全局搜索和局部搜索能力;最后,通过大量仿真实验验证MA算法求解该问题的有效性和优越性.     

A note on the complexity of the concurrent open shop problem

The concurrent open shop problem is a relaxation of the well known open job shop problem, where the components of a job can be processed in parallel by dedicated, component specific machines. Recently, the problem has attracted the attention of a number of researchers. In particular, Leung et al. (2005) show, contrary to the assertion in Wagneur and Sriskandarajah (1993), that the problem of minimizing the average job completion time is not necessarily strongly NP-hard. Their finding has thus once again opened up the question of the problem's complexity. This paper re-establishes that, even for two machines, the problem is NP-hard in the strong sense.     

炼钢连铸生产中炉机优化匹配问题的算法

将炼钢连铸生产计划中炉机优化匹配问题归结为一个不允许等待的混合流水车间排序问题来进行研究,提出了一个启发式算法-最小偏差算法。通过实验设计,用大量随机数据进行了模拟和统计分析。结果表明,最小偏差算法是一种合理的、实用的、有效的算法。     

An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers

In this paper, an effective hybrid algorithm based on particle swarm optimization (HPSO) is proposed for permutation flow shop scheduling problem (PFSSP) with the limited buffers between consecutive machines to minimize the maximum completion time (i.e., makespan). First, a novel encoding scheme based on random key representation is developed, which converts the continuous position values of particles in PSO to job permutations. Second, an efficient population initialization based on the famous Nawaz–Enscore–Ham (NEH) heuristic is proposed to generate an initial population with certain quality and diversity. Third, a local search strategy based on the generalization of the block elimination properties, named block-based local search, is probabilistically applied to some good particles. Moreover, simulated annealing (SA) with multi-neighborhood guided by an adaptive meta-Lamarckian learning strategy is designed to prevent the premature convergence and concentrate computing effort on promising solutions. Simulation results and comparisons demonstrate the effectiveness of the proposed HPSO. Furthermore, the effects of some parameters are discussed.     

Two‐stage hybrid flow shop with recirculation

In this paper, we present two scheduling hybrid flow shop problems to minimize the makespan. In each problem, we have two stages. In the first problem, one machine at each stage is considered with recirculation of jobs in the second stage (machine). We prove that this first problem is polynomial and we present an algorithm for its resolution. The second problem consists of one machine in the first stage and two identical parallel machines in the second. Jobs can be recirculated a fixed number of times in the second stage. We show that the problem is NP‐hard and a polynomial subproblem is proposed. Linear program and heuristics are also presented with numerical experimentations.     

Study of stochastic sequence-dependent flexible flow shop via developing a dispatching rule and a hybrid GA

A flexible flow shop is a generalized flow shop with multiple machines in some stages. This system is fairly common in flexible manufacturing and in process industry. In most practical environments, scheduling is an ongoing reactive process where the presence of real time information continually forces reconsideration of pre-established schedules. This paper studies a flexible flow shop system considering non-deterministic and dynamic arrival of jobs and also sequence dependent setup times. The problem objective is to determine a schedule that minimizes average tardiness of jobs. Since the problem class is NP-hard, a novel dispatching rule and hybrid genetic algorithm have been developed to solve the problem approximately. Moreover, a discrete event simulation model of the problem is developed for the purpose of experimentation. The most commonly used dispatching rules from the literature and two new methods presented in this paper are incorporated in the simulation model. Simulation experiments have been conducted under various experimental conditions characterized by factors such as shop utilization, setup time level and number of stages. The results indicate that methods proposed in this study are much better than the traditional dispatching rules.     

Two-stage hybrid flow shop scheduling on parallel batching machines considering a job-dependent deteriorating effect and non-identical job sizes

In this paper, we investigate a specialized two-stage hybrid flow shop scheduling problem with parallel batching machines considering a job-dependent deteriorating effect and non-identical job sizes simultaneously. A novel concept of three-dimensional wasted volume based on the job normal processing time, job size, and job deteriorating rate is first proposed. Some structural properties, as well as a heuristic algorithm, are developed to solve the single parallel batching machine scheduling problem. Since the two-stage hybrid flow shop scheduling problem is NP-hard, a hybrid EDA-DE algorithm combining estimation of distribution algorithm (EDA) and differential evolution (DE) algorithm is proposed to tackle the studied problem. In addition, the Taguchi method of design of experiments (DOE) is implemented to tune the parameters of the EDA-DE. Finally, a series of computational experiments are carried out to compare the performance of the proposed hybrid EDA-DE algorithm and some recent existing algorithms from the literature, and the comparative results validate the effectiveness and efficiency of the proposed algorithm.     

Hybrid flow shop scheduling with not-all-machines options via local search with controlled deterioration

In this study we consider hybrid flow shop scheduling problem with a decision referring to the number of machines to be used. A simple way is used to decide the number of the used machines. A novel local search with controlled deterioration (CDLS) is proposed, which is composed of multiple neighborhood searches with the prefixed number of iterations and deterioration step. The deterioration step tries to obtain a new current solution with the controlled deteriorated degree on the solution quality. CDLS is tested on a number of instances and the computational results show that CDLS can provide the promising results for the considered problem.     

A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines,setup times,and dual criteria

This paper considers a flexible flow shop scheduling problem, where at least one production stage is made up of unrelated parallel machines. Moreover, sequence- and machine-dependent setup times are given. The objective is to find a schedule that minimizes a convex sum of makespan and the number of tardy jobs in a static flexible flow shop environment. For this problem, a 0–1 mixed integer program is formulated. The problem is, however, a combinatorial optimization problem which is too difficult to be solved optimally for large problem sizes, and hence heuristics are used to obtain good solutions in a reasonable time. The proposed constructive heuristics for sequencing the jobs start with the generation of the representatives of the operating time for each operation. Then some dispatching rules and flow shop makespan heuristics are developed. To improve the solutions obtained by the constructive algorithms, fast polynomial heuristic improvement algorithms based on shift moves and pairwise interchanges of jobs are applied. In addition, metaheuristics are suggested, namely simulated annealing (SA), tabu search (TS) and genetic algorithms. The basic parameters of each metaheuristic are briefly discussed in this paper. The performance of the heuristics is compared relative to each other on a set of test problems with up to 50 jobs and 20 stages and with an optimal solution for small-size problems. We have found that among the constructive algorithms the insertion-based approach is superior to the others, whereas the proposed SA algorithms are better than TS and genetic algorithms among the iterative metaheuristic algorithms.     

基于多班教学优化的多目标分布式混合流水车间调度

单工厂环境下的混合流水车间调度问题已受到广泛关注,而多工厂环境下的分布式混合流水车间调度问题(distributed hybrid flow shop scheduling problem,DHFSP)研究进展则较小.针对考虑顺序相关准备时间的DHFSP,提出一种多班教学优化(multi-class teaching-learning-based optimization,MTLBO)算法以同时最小化最大完成时间和最大延迟时间.该算法采用双串编码方式,将种群划分成s个班级,每个班级的进化都由两个教师阶段和一个学生阶段组成;引入一种班级质量评价方式,实现奖惩机制和淘汰过程.通过大量实验测试MTLBO的性能,计算结果表明,MTLBO对于所求解的DHFSP具有较强优势.