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.     

An effective neighborhood search algorithm for scheduling a flow shop of batch processing machines

This paper considers scheduling problem of flow shop with many batch processing machines and objective of maximum lateness. An effective neighborhood search algorithm (NSA) is proposed for the problem, in which a job permutation and a batch permutation are used to indicate the solution of two sub-problems, respectively. Each job permutation consists of several family-permutations for the representation of jobs from the same family. Two swaps are applied to two permutations to produce new solutions. NSA is applied to a number of instances and compared with some methods, and computational results validate the good performance of NSA.     

A holonic approach to flexible flow shop scheduling under stochastic processing times

Flexible flow shop scheduling problems are NP-hard and tend to become more complex when stochastic uncertainties are taken into consideration. This paper presents a novel decomposition-based holonic approach (DBHA) for minimising the makespan of a flexible flow shop (FFS) with stochastic processing times. The proposed DBHA employs autonomous and cooperative holons to construct solutions. When jobs are released to an FFS, the machines of the FFS are firstly grouped by a neighbouring K-means clustering algorithm into an appropriate number of cluster holons, based on their stochastic nature. A scheduling policy, determined by the back propagation networks (BPNs), is then assigned to each cluster holon for schedule generation. For cluster holons of a low stochastic nature, the Genetic Algorithm Control (GAC) is adopted to generate local schedules in a centralised manner; on the other hand, for cluster holons of a high stochastic nature, the Shortest Processing Time Based Contract Net Protocol (SPT-CNP) is applied to conduct negotiations for scheduling in a decentralised manner. The combination of these two scheduling policies enables the DBHA to achieve globally good solutions, with considerable adaptability in dynamic environments. Computation results indicate that the DBHA outperforms either GAC or SPT-CNP alone for FFS scheduling with stochastic processing times.     

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.     

An ACO-based intercell scheduling approach for job shop cells with multiple single processing machines and one batch processing machine

Intercell transfers are inevitable for the manufacturing of complicated products, which disrupts the philosophy of cellular manufacturing and leads new challenges to the field of production scheduling. The issue of intercell scheduling is analyzed in the context of a cellular manufacturing system consisting of multiple single-processing machines and one batch-processing machine, which is derived from the actual manufacturing of complicated assemblies in the equipment manufacturing industry. Since the two types of machines are different from, even contrary to, each other in some constraint conditions, a combinational ant colony optimization (CACO) approach is developed in this paper, which designs two structures for the single-processing machines and the batch-processing machine, respectively. By updating pheromone trails integratedly and scheduling the single-processing operations and the batch-processing operations simultaneously, cooperative optimization for the two types of machines is achieved in the CACO. Minimizing the maximum completion time is taken as the scheduling objectives. Computational results show that the CACO has significant advantages comparing with other approaches and the CPLEX, and is especially suitable for the large dimension problems.     

A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes

This paper investigates the scheduling problem of parallel identical batch processing machines in which each machine can process a group of jobs simultaneously as a batch. Each job is characterized by its size and processing time. The processing time of a batch is given by the longest processing time among all jobs in the batch. Based on developing heuristic approaches, we proposed a hybrid genetic heuristic (HGH) to minimize makespan objective. To verify the performance of our algorithm, comparisons are made through using a simulated annealing (SA) approach addressed in the literature as a comparator algorithm. Computational experiments reveal that affording the knowledge of problem through using heuristic procedures, gives HGH the ability of finding optimal or near optimal solutions in a reasonable time.     

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.     

Design of efficient hybrid neural networks for flexible flow shop scheduling

Abstract: Although neural networks have been successfully used in performing pattern recognition, their application for solving optimization problems has been limited. In this paper we design a neural network to solve a well‐known combinatorial problem, namely the flexible flow shop problem. A key feature of our neural network design is the integration of problem structure and heuristic information in the network structure and solution. We compare the performance of our neural network with well‐known current heuristics with respect to solution quality. The results indicate that our approach outperforms the heuristics.     

求解分布式两阶段混合流水车间调度的反馈人工蜂群算法

针对考虑工厂适用性和附加资源的分布式两阶段混合流水车间调度问题(DTHFSP), 本文提出了一种反馈人工蜂群算法(FABC), 以最小化最大完成时间和总延迟时间, 该算法利用一种新型反馈机制动态调整搜索策略集.为此, 本文共设计了5 种特点各异的搜索策略, 将其用于初始策略集和备选策略集, 同时, 建立并调整雇佣蜂群和跟随蜂群的共享策略集, 雇佣蜂阶段和跟随蜂阶段在种群划分的基础上采用随机选择和自适应选择方式确定搜索策略, 在侦查蜂阶段完成后, 对搜索策略集进行动态调整. 文章进行了大量的计算实验, 计算结果表明, FABC策略合理有效, 且它对所求解的DTHFSP具有较强的搜索优势.     

A two-stage hybrid memetic algorithm for multiobjective job shop scheduling

In this paper we address multiobjective job shop scheduling problems. After several decades of research in scheduling problems, a variety of heuristics have been developed. The proposed algorithm is a hybrid of three frequently applied ones: the dispatching rule, the shifting bottleneck procedure, and the evolutionary algorithm. It is a two-stage algorithm, which integrates a rule-based memetic algorithm in the first stage and a re-optimization procedure of shifting bottleneck in the second. We conduct experiments using benchmark instances found in the literature to assess the performance of the proposed method. The experimental results show that the proposed method is effective and efficient for multiobjective scheduling problems.     

Flexible flow shop scheduling with stochastic processing times: A decomposition-based approach

Flexible flow shop scheduling problems are NP-hard and tend to become more complex when stochastic uncertainties are taken into consideration. Although some methods have been developed to address such problems, they remain inherently difficult to solve by any single approach. This paper presents a novel decomposition-based approach (DBA), which combines both the shortest processing time (SPT) and the genetic algorithm (GA), to minimizing the makespan of a flexible flow shop (FFS) with stochastic processing times. In the proposed DBA, a neighbouring K-means clustering algorithm is developed to firstly group the machines of an FFS into an appropriate number of machine clusters, based on their stochastic nature. Two optimal back propagation networks (BPN), corresponding to the scenarios of simultaneous and non-simultaneous job arrivals, are then selectively adopted to assign either SPT or GA to each machine cluster for sub-schedule generation. Finally, an overall schedule is generated by integrating the sub-schedules of machine clusters. Computation results show that the DBA outperforms SPT and GA alone for FFS scheduling with stochastic processing times.     

A bi-layer optimization approach for a hybrid flow shop scheduling problem involving controllable processing times in the steelmaking industry

A steelmaking-continuous casting (SCC) scheduling problem is an example of complex hybrid flow shop scheduling problem (HFSSP) with a strong industrial background. This paper investigates the SCC scheduling problem that involves controllable processing times (CPT) with multiple objectives concerning the total waiting time, earliness/tardiness and adjusting cost. The SCC scheduling problem with CPT is seldom discussed in the existing literature. This study is motivated by the practical situation of a large integrated steel company in which the just-in-time (JIT) and cost-cutting production strategy have become a significant concern. To address this complex HFSSP, the scheduling problem is decomposed into two subproblems: a parallel machine scheduling problem (PMSP) in the last stage and an HFSSP in the upstream stages. First, a hybrid differential evolution (HDE) algorithm combined with a variable neighborhood decomposition search (VNDS) is proposed for the former subproblem. Second, an iterative backward list scheduling (IBLS) algorithm is presented to solve the latter subproblem. The effectiveness of this bi-layer optimization approach is verified by computational experiments on well-designed and real-world scheduling instances. This study provides a new perspective on modeling and solving practical SCC scheduling problems.     

A meta-heuristic approach to solve a JIT scheduling problem in hybrid flow shop

In this paper we address a hybrid flow shop scheduling problem considering the minimization of the sum of the total earliness and tardiness penalties. This problem is proven to be NP-hard, and consequently the development of heuristic and meta-heuristic approaches to solve it is well justified. So, we propose an ant colony optimization method to deal with this problem. Our proposed method has several features, including some heuristics that specifically take into account both earliness and tardiness penalties to compute the heuristic information values. The performance of our algorithm is tested by numerical experiments on a large number of randomly generated problems. A comparison with solutions performance obtained by some constructive heuristics is presented. The results show that the proposed approach performs well for this problem.     

Scheduling two-stage hybrid flow shop with availability constraints

Most of the literature on scheduling assumes that machines are always available. However, in real life industry, machines may be subject to some unavailability periods due to maintenance activities such as breakdowns (stochastic case) and preventive maintenance (deterministic case). In this paper we investigate the two-stage hybrid flow shop scheduling problem with only one machine on the first stage and m machines on the second stage to minimize the makespan. We consider that each machine is subject to at most one unavailability period. The start time and the end time of each period are known in advance (deterministic case) and only the non-resumable case is studied. First we discuss the complexity of the problem. Afterwards, we give the Branch and Bound model for this problem. Last, we calculate the worst-case performances of three heuristics: LIST algorithm, LPT algorithm and H-heuristic.     

基于改进蛙跳算法的分布式两阶段混合流水车间调度

针对考虑顺序相关准备时间的分布式两阶段混合流水车间调度问题,提出一种改进的蛙跳算法以同时最小化拖后工件数和最大完成时间.该算法通过启发式方法和随机方法对种群进行初始化,采取基于种群和记忆的种群划分方法,同时给出模因组质量评价方法,并根据模因组质量将所有模因组划分为最优模因组、最差模因组和其他模因组,每种类型的模因组分别采取不同的搜索策略,并分配不同的搜索次数,其中最优模因组不参与种群划分.选用一种多目标经典算法和两种近5年提出的算法作为对比算法,并与改进蛙跳算法的变体进行比较以验证模因组搜索新策略的有效性.通过对大量实例的计算实验结果表明,模因组搜索新策略有效,改进蛙跳算法能有效求解分布式两阶段混合流水车间调度问题.     

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

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

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.