Two-stage flowshop scheduling with a common second-stage machine

This article considers minimizing the makespan in a two-stage flowshop scheduling problem with a common second-stage machine. After introducing the problem, we show that it is -hard and give two special cases which are polynomially solvable. Next, we propose a heuristic algorithm and analyze its worst-case error bound. We then develop some lower bounds. Finally, we perform some computational experiments to test the average performance of the proposed heuristic.     

Two-stage hybrid batching flowshop scheduling with blocking and machine availability constraints using genetic algorithm

This research investigates a two-stage hybrid flowshop scheduling problem in a metal-working company. The first stage consists of multiple parallel machines and the second stage has only one machine. Four characteristics of the company have substantiated the complexity of the problem. First, all machines in stage one are able to process multiple jobs simultaneously but the jobs must be sequentially set up one after another. Second, the setup time of each job is separated from its processing time and depends upon its preceding job. Third, a blocking environment exists between two stages with no intermediate buffer storage. Finally, machines are not continuously available due to the preventive maintenance and machine breakdown. Two types of machine unavailability, namely, deterministic case and stochastic case, are identified in this problem. The former occurs on stage-two machine with the start time and the end time known in advance. The latter occurs on one of the parallel machine in stage one and a real-time rescheduling will be triggered. Minimizing the makespan is considered as the objective to develop the optimal scheduling algorithm. A genetic algorithm is used to obtain a near-optimal solution. The computational results with actual data are favorable and superior over the results from existing manual schedules.     

两台流水机器协调分解调度问题

研究钢管加工流程中一类新型两台机器流水车间调度问题,工件在第一台机器上加工后被分解成多个子工件.对于最小化最大完成时间的情况,给出一个多项式时间的最优算法;对于最小化最大完成时间与惩罚费用之和的情况,给出一个拟多项式时间的动态规划算法;对于考虑生产前运输的最小化最大完成时间的情况,分析了问题的复杂性.证明了第一种情况的最优算法可作为后两种情况的2-近似算法.数值实验表明了算法的有效性.     

A two-stage hybrid flowshop scheduling problem with a function constraint and unrelated alternative machines

This article addresses a two-stage hybrid flowshop scheduling problem with unrelated alternative machines. The problem to be studied has m unrelated alternative machines at the first machine center followed by a second machine center with a common processing machine in the system. The objective is to minimize the makespan of the system. For the processing of any job, it is assumed that the operation can be partially substituted by other machines in the first center, depending on its machining constraints. Such scheduling problems occur in certain practical applications such as semiconductors, electronics manufacturing, airplane engine production, and petrochemical production. We demonstrate that the addressed problem is NP-hard and then provide some heuristic algorithms to solve the problem efficiently. The experimental results show that the combination of the modified Johnson's rule and the First-Fit rule provides the best solutions within all proposed heuristics.Scope and purpose     

含忽略工序和不相关机的混合流水车间调度

研究从炼钢等生产过程提炼出的含忽略工序和不相关并行机的混合流水车间调度问题,以最小化最大完工时间为目标,建立整数规划模型,并提出结合全局搜索、自适应遗传算法和候鸟优化的遗传候鸟优化算法以求解该模型。在算法中采用与处理时间相关的全局搜索和随机程序以获得初始种群,提出自适应交叉和变异操作改进遗传算法解,在迭代进程中,引入基于工件、机器和工序位3种邻域搜索结构的候鸟优化算法更新最佳解。仿真实验中将遗传候鸟优化算法的实验结果与几种启发式算法进行对比,证明了模型和算法的有效性。     

Scheduling hybrid flowshop with parallel batching machines and compatibilities

This paper considers a two-stage hybrid flowshop problem in which the first stage contains several identical discrete machines, and the second stage contains several identical batching machines. Each discrete machine can process no more than one task at time, and each batching machine can process several tasks simultaneously in a batch with the additional feature that the tasks of the same batch have to be compatible. A compatibility relation is defined between each pair of tasks, so that an undirected compatibility graph is obtained which turns out to be an interval graph. The batch processing time is equal to the maximal processing time of the tasks in this batch, and all tasks of the same batch start and finish together. The goal is to make batching and sequencing decisions in order to minimize the makespan. Since the problem is NP-hard, we develop several heuristics along with their worst cases analysis. We also consider the case in which tasks have the same processing time on the first stage, for which a polynomial time approximation scheme (PTAS) algorithm is presented.     

置换流水车间调度问题的两阶段分布估计算法

针对置换流水车间调度问题,以最小化总流水时间为目标,提出了一种新颖的两阶段分布估计算法。第一阶段先利用NEH（Nawaz-Enscore-Ham,NEH）启发式构造一个较优的初始个体,然后随机生成初始种群,为保留种群的多样性,提出一种择优机制来选择个体并建立概率模型,同时在当代种群中利用精英机制保留当代种群中的最优解,最后利用概率模型采样并生成下一代种群。第二阶段采用插入、互换操作算子对第一阶段得到的最优解进行邻域搜索,来提高分布估计算法的全局搜索能力,阻止其陷入局部最优解。通过对算例进行实验、对比和分析,证明该算法的可行性和有效性。     

带运输考虑的多阶段动态可重入混合流水车间调度

可重入混合流水车间调度允许一个工件多次进入某些加工阶段,它广泛出现在许多工业制造过程中,如半导体制造、印刷电路板制造等.本文研究了带运输时间的多阶段动态可重入混合流水车间问题,目标是最小化总加权完成时间.针对该问题,建立了整数规划模型,进而基于工件解耦方式提出了两种改进的拉格朗日松弛(LR)算法.在这些算法中,设计了动态规划的改进策略以加速工件级子问题的求解,提出了异步次梯度法以得到有效的乘子更新方向.测试结果说明了所提出的两种改进算法在解的质量和运行时间方面均优于常规LR算法,两种算法都能在可接受的计算时间内得到较好的近优解.     

A hybrid flowshop scheduling model considering dedicated machines and lot-splitting for the solar cell industry

This paper studies a solar cell industry scheduling problem, which is similar to traditional hybrid flowshop scheduling (HFS). In a typical HFS problem, the allocation of machine resources for each order should be scheduled in advance. However, the challenge in solar cell manufacturing is the number of machines that can be adjusted dynamically to complete the job. An optimal production scheduling model is developed to explore these issues, considering the practical characteristics, such as hybrid flowshop, parallel machine system, dedicated machines, sequence independent job setup times and sequence dependent job setup times. The objective of this model is to minimise the makespan and to decide the processing sequence of the orders/lots in each stage, lot-splitting decisions for the orders and the number of machines used to satisfy the demands in each stage. From the experimental results, lot-splitting has significant effect on shortening the makespan, and the improvement effect is influenced by the processing time and the setup time of orders. Therefore, the threshold point to improve the makespan can be identified. In addition, the model also indicates that more lot-splitting approaches, that is, the flexibility of allocating orders/lots to machines is larger, will result in a better scheduling performance.     

Modeling realistic hybrid flexible flowshop scheduling problems

This paper aims to contribute to the recent research efforts to bridge the gap between the theory and the practice of scheduling by modelizing a realistic manufacturing environment and analyzing the effect of the inclusion of several characteristics in the problem formulation. There are several constraints and characteristics that affect the scheduling operations at companies. While these constraints are many times tackled in the literature, they are seldom considered together inside the same problem formulation. We propose a formulation along with a mixed integer modelization and some heuristics for the problem of scheduling n jobs on m stages where at each stage we have a known number of unrelated machines. The jobs might skip stages and, therefore, we have what we call a hybrid flexible flowshop problem. We also consider per machine sequence-dependent setup times which can be anticipatory and non-anticipatory along with machine lags, release dates for machines, machine eligibility and precedence relationships among jobs. Manufacturing environments like this appear in sectors like food processing, ceramic tile manufacturing and several others. The optimization criterion considered is the minimization of the makespan. The MIP model and the heuristics proposed are tested against a comprehensive benchmark and the results evaluated by advanced statistical tools that make use of decision trees and experimental designs. The results allow us to identify the constraints that increase the difficulty.     

Tabu search heuristic for two-machine flowshop with batch processing machines

Batch processing machines are frequently encountered in many industrial environments. A batch processing machine is one which can process several jobs simultaneously as a batch. The processing time of a batch is equal to the largest processing time of any job in the batch. This study deals with the problem of scheduling jobs in a flowshop with two batch processing machines such that the makespan is minimized. A heuristic based on Tabu search (TS) technique is proposed. The proposed heuristic is compared with a heuristic based on mixed integer linear programming (MILP). Because the complexity of the MILP-based heuristic is depended on the number of job batches, the comparison is under up-to-eight batches problem. In order to measure the proposed TS-based heuristic in larger batch problem, the relative error percentage with the lower bound (REP_LB) is used. The results show that the proposed heuristic is efficient and effective for the problems with relative large job sizes.     

A note on two-stage hybrid flowshop scheduling with missing operations

The scheduling problem in a multi-stage hybrid flowshop has been the subject of considerable research. All the studies on this subject assume that each job has to be processed on all the stages, i.e., there are no missing operations for a job at any stage. However, missing operations usually exist in many real-life production systems, such as a system in a stainless steel factory investigated in this note. The studied production system in the factory is composed of two stages in series. The first stage contains only one machine while the second stage consists of two identical machines (namely a 1 × 2 hybrid flowshop). In the system, some jobs have to be processed on both stages, but others need only to be processed on the second stage. Accordingly, the addressed scheduling problem is a 1 × 2 hybrid flowshop with missing operations at the first stage. In this note, we develop a heuristic for the problem to generate a non-permutation schedule (NPS) from a given permutation schedule, with the objective of minimizing the makespan. Computational results demonstrate that the heuristic can efficiently generate better NPS solutions.     

Two-machine flowshop scheduling with flexible operations and controllable processing times

We consider a two-machine flowshop scheduling problem with identical jobs. Each of these jobs has three operations, where the first operation must be performed on the first machine, the second operation must be performed on the second machine, and the third operation (named as flexible operation) can be performed on either machine but cannot be preempted. Highly flexible CNC machines are capable of performing different operations. Furthermore, the processing times on these machines can be changed easily in albeit of higher manufacturing cost by adjusting the machining parameters like the speed and/or feed rate of the machine. The overall problem is to determine the assignment of the flexible operations to the machines and processing times for each operation to minimize the total manufacturing cost and makespan simultaneously. For such a bicriteria problem, there is no unique optimum but a set of nondominated solutions. Using ?-constraint$?\mathrm{-}\mathrm{constraint}$ approach, the problem could be transformed to be minimizing total manufacturing cost for a given upper limit on the makespan. The resulting single criterion problem can be reformulated as a mixed integer nonlinear problem with a set of linear constraints. We use this formulation to optimally solve small instances of the problem while a heuristic procedure is constructed to solve larger instances in a reasonable time.     

A hybrid scheduling approach for a two-stage flexible flow shop with batch processing machines

In this paper, we discuss a flexible flow shop scheduling problem with batch processing machines at each stage and with jobs that have unequal ready times. Scheduling problems of this type can be found in semiconductor wafer fabrication facilities (wafer fabs). We are interested in minimizing the total weighted tardiness of the jobs. We present a mixed integer programming formulation. The batch scheduling problem is NP-hard. Therefore, an iterative stage-based decomposition approach is proposed that is hybridized with neighborhood search techniques. The decomposition scheme provides internal due dates and ready times for the jobs on the first and second stage, respectively. Each of the resulting parallel machine batch scheduling problems is solved by variable neighborhood search in each iteration. Based on the schedules of the subproblems, the internal due dates and ready times are updated. We present the results of designed computational experiments that also consider the number of machines assigned to each stage as a design factor. It turns out that the proposed hybrid approach outperforms an iterative decomposition scheme where a fairly simple heuristic based on time window decomposition and the apparent tardiness cost dispatching rule is used to solve the subproblems. Recommendations for the design of the two stages with respect to the number of parallel machines on each stage are given.     

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.     

An efficient stochastic hybrid heuristic for flowshop scheduling

The paper addresses the problem of flowshop scheduling in order to minimize the makespan objective. Three probabilistic hybrid heuristics are presented for solving permutation flowshop scheduling problem. The proposed methodology combines elements from both constructive heuristic search and a stochastic improvement technique. The stochastic method used in this paper is simulated annealing (SA). Experiments have been run on a large number of randomly generated test problems of varying jobs and machine sizes. Our approach is shown to outperform best-known existing heuristics, including the classical NEH technique (OMEGA, 1983) and the SA based on (OMEGA, 1989) of Osman and Potts . Statistical tests of significance are performed to substantiate the claims of improvement.     

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.     

Real-time scheduling for hybrid flowshop in ubiquitous manufacturing environment

This paper discusses the implementation of RFID technologies, which enable the shop floor visibility and reduce uncertainties in the real-time scheduling for hybrid flowshop (HFS) production. In the real-time HFS environment, the arriving of new jobs is dynamic, while the processes in work stages are not continuous. The decision makers in shop floor level and stage level have different objectives. Therefore, classical off-line HFS scheduling approaches cannot be used under these situations. In this research, two major measures are taken to deal with these specific real-time features. Firstly, a ubiquitous manufacturing (UM) environment is created by deploying advanced wireless devices into value-adding points for the collection and synchronization of real-time shop floor data. Secondly, a multi-period hierarchical scheduling (MPHS) mechanism is developed to divide the planning time horizon into multiple shorter periods. The shop floor manager and stage managers can hierarchically make decisions for their own objectives. Finally, the proposed MPHS mechanism is illustrated by a numerical case study.     

Two-machine no-wait flowshop scheduling with learning effect and convex resource-dependent processing times

Two-machine no-wait flowshop scheduling problems in which the processing time of a job is a function of its position in the sequence and its resource allocation are considered in the study. The primary objective is to find the optimal sequence of jobs and the optimal resource allocation separately. Here we propose two separate models: minimizing a cost function of makespan, total completion time, total absolute differences in completion times and total resource cost; minimizing a cost function of makespan, total waiting time, total absolute differences in waiting times and total resource cost. Since each model is strongly NP-hard, we solve both models by breaking them down to two sub-problems, the optimal resource allocation problem for any job sequence and the optimal sequence problem with its optimal resource allocation. Specially, we transform the second sub-problem into the minimum of the bipartite graph optimal matching problem (NP-hard), and solve it by using the classic KM (Kuhn–Munkres) algorithm. The solutions of the two sub-problems demonstrate that the target problems remain polynomial solvable under the proposed model.