Heuristic search algorithms for lot streaming in a two-machine flowshop

The objective of this paper is to propose and evaluate heuristic search algorithms for a two-machine flowshop problem with multiple jobs requiring lot streaming that minimizes makespan. A job here implies many identical items. Lot streaming creates sublots to move the completed portion of a production lot to second machine. The three heuristic search algorithms evaluated in this paper are Baker’s approach (Baker), genetic algorithm (GA) and simulated annealing (SA) algorithm. To create neighborhoods for SA, three perturbation schemes, viz., pair-wise exchange, insertion and random insertion are used, and the performance of these on the final schedule is also compared. A wide variety of data sets is randomly generated for comparative evaluation. The parameters for GA and SA are obtained after conducting sensitivity analysis. The genetic algorithm is found to perform well for lot streaming in the two-machine flowshop scheduling.     

An ant colony algorithm for scheduling in flowshops with sequence-dependent setup times of jobs

The problem of scheduling in flowshops with sequence-dependent setup times of jobs is considered and solved by making use of ant colony optimization (ACO) algorithms. ACO is an algorithmic approach, inspired by the foraging behavior of real ants, that can be applied to the solution of combinatorial optimization problems. A new ant colony algorithm has been developed in this paper to solve the flowshop scheduling problem with the consideration of sequence-dependent setup times of jobs. The objective is to minimize the makespan. Artificial ants are used to construct solutions for flowshop scheduling problems, and the solutions are subsequently improved by a local search procedure. An existing ant colony algorithm and the proposed ant colony algorithm were compared with two existing heuristics. It was found after extensive computational investigation that the proposed ant colony algorithm gives promising and better results, as compared to those solutions given by the existing ant colony algorithm and the existing heuristics, for the flowshop scheduling problem under study.     

Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria

In textile industries, production facilities are established as multi-stage production flow shop facilities, where a production stage may be made up of parallel machines. This known as a flexible or hybrid flow shop environment. This paper considers the problem of scheduling n independent jobs in such an environment. In addition, we also consider the general case in which parallel machines at each stage may be unrelated. Each job is processed in ordered operations on a machine at each stage. Its release date and due date are given. The preemption of jobs is not permitted. We consider both sequence- and machine-dependent setup times. The problem is to determine a schedule that minimizes a convex combination of makespan and the number of tardy jobs. A 0–1 mixed integer program of the problem is formulated. Since this problem is NP-hard in the strong sense, we develop heuristic algorithms to solve it approximately. Firstly, several basic dispatching rules and well-known constructive heuristics for flow shop makespan scheduling problems are generalized to the problem under consideration. We sketch how, from a job sequence, a complete schedule for the flexible flow shop problem with unrelated parallel machines can be constructed. To improve the solutions, polynomial heuristic improvement methods based on shift moves of jobs are applied. Then, genetic algorithms are suggested. We discuss the components of these algorithms and test their parameters. 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.     

Due windows group scheduling using an effective hybrid optimization approach

This paper considers the problem of scheduling part families (groups) and jobs within each part family in a hybrid flow shop manufacturing cell with sequence-dependent family setups times where jobs should be completed at times as close as possible to their respective due dates, and hence both earliness and tardiness should be penalized while processing parts (jobs) in each family together. It is assumed that earliness and tardiness penalties will not occur if a job is completed within the due window. The objective is to determine a schedule that minimizes sum of the earliness and tardiness of jobs. To this problem, the hybrid metaheuristic algorithm combined elements from particle swarm optimization; simulated annealing and variable neighborhood search are developed. The aim of using a hybrid metaheuristic is to raise the level of generality so as to be able to apply the same solution method to several problems. Problem sizes ranging in size from small, medium, to large are considered along with three levels of flexibility. The higher the number of stages and the number of parallel machines in each stage, the higher is the flexibility introduced into the problem. A design of experiments approach is employed to calibrate the parameters and operators of the algorithm. We present computational experiments on 126 problems and compare the results with the simulated annealing and genetic algorithms that presented recently. The computational results show that our proposed algorithm is more efficient than the other methods.     

A simulated annealing/local search to minimize the makespan and total tardiness on a hybrid flowshop

Scheduling is a major issue faced every day in manufacturing systems as well as in the service industry, so it is essential to develop effective and efficient advanced manufacturing and scheduling technologies and approaches. Also, it can be said that bi-criteria scheduling problems are classified in two general categories respecting the approach used to solve the problem. In one category, the aim is to determine a schedule that minimizes a convex combination of two objectives and in the other category is to find a good approximation of the set of efficient solutions. The aim of this paper is to determine a schedule for hybrid flowshop problem that minimizes a convex combination of the makespan and total tardiness. For the optimization problem, a meta-heuristic procedure is proposed based on the simulated annealing/local search (SA/LS) along with some basic improvement procedures. The performance of the proposed algorithm, SA/LS, is compared with a genetic algorithm which had been presented in the literature for hybrid flowshop with the objective of minimizing a convex combination of the makespan and the number of tardy jobs. Several computational tests are used to evaluate the effectiveness and efficiency of the proposed algorithm against the other algorithm provided in the literature. From the results obtained, it can be seen that the proposed algorithm in comparison with the other algorithm is more effective and efficient.     

A Memetic Algorithm for the <Emphasis Type="SmallCaps">n</Emphasis>/2/Flowshop/α<Emphasis Type="SmallCaps">F </Emphasis>+ β<Emphasis Type="SmallCaps">C</Emphasis><Subscript>max</Subscript> Scheduling Problem

Machine scheduling has been a popular area of research during the past four decades. Its object is to determine the sequence for processing jobs on a given set of machines. The need for scheduling arises from the limited resources available to the decision-maker. In this study, a special situation involving a computationally difficult n/2/Flowshop/ αF + βCmax flowshop scheduling problem is discussed. We develop a memetic algorithm (MA, a hybrid genetic algorithm) by combining a genetic algorithm and the greedy heuristic using the pairwise exchange method and the insert method, to solve the n/2/Flowshop/ αF + βCmax flowshop scheduling problem. Preliminary computational experiments demonstrate the efficiency and performance of the proposed memetic algorithm. Our results compare favourably with the best-known branch-and-bound algorithm, the traditional genetic algorithm and the best-known heuristic algorithm.     

A hybrid genetic algorithm to minimize makespan for the single batch machine dynamic scheduling problem

This paper considers a single batch machine dynamic scheduling problem, which is readily found in the burn-in operation of semiconductor manufacturing. The batch machine can process several jobs as a batch simultaneously, within the capacity limit of the machine, and the processing time is represented by the longest processing time among all jobs in a batch. For a single batch machine problem with arbitrary job release time, we proposed an improved algorithm (merge-split procedure) to refine the solution obtained by the LPT-BFF heuristic, and two versions of a hybrid genetic algorithm (GA) are introduced in this paper. Each version of the hybrid GA diversifies job sequences using the GA operators in stage 1, forms batches in stage 2, and finally sequence the batches in stage 3. The difference is that merge-split procedures are involved in the second version of the hybrid GA. Computational experiments showed that the hybrid GA would obtain satisfactory average solution quality and the merge-split procedures would be good at reinforcing the solution consistency of the hybrid GA.     

Solving manpower scheduling problem in manufacturing using mixed-integer programming with a two-stage heuristic algorithm

Manpower scheduling problem is one of the key scheduling problems with extensive applications in manufacturing. This paper presents a mixed-integer programming model with a two-stage heuristic algorithm for solving the manpower scheduling problem in the precision engineering industry. Firstly, a mixed-integer programming formulation is developed to model the manpower scheduling problem in this high-mix low-volume manufacturing environment. Secondly, a two-stage heuristic algorithm is proposed where the first stage is deployed to calculate the skill requirements for each shift by considering the jobs, machines, and their production schedule and the second stage is designed to assign operators to the machines by considering the skill set requirements and the operator's expressed preferences. Lastly, the computational results based on problem instances emulating real-world scenarios demonstrated the feasibility and effectiveness of the proposed heuristic.     

Multiple cycle economic lot and delivery-scheduling problem in a two-echelon supply chain

This paper addresses the problem of lot sizing, scheduling, and delivery of several items in a two-echelon supply chain over a finite planning horizon. Single supplier produces the items through a flexible flow line and delivers them directly to an assembly facility where the transfer of sub-lots between adjacent stages of supplier’s production system (i.e., lot streaming) is allowed in order to decrease the manufacturing lead time. At first, a mixed zero-one nonlinear programming model is developed based on the so-called basic period (BP) approach aiming to minimize the average setup, inventory holding, and delivery costs per unit time in the supply chain without any stock-out. The problem is very complex and cannot be solved to optimality especially for real-sized problems. Therefore, two efficient hybrid genetic algorithms (HGA) are proposed based on the power-of-two (PTHGA) and non-power-of-two (NPTHGA) variants of BP approach. The solution qualities of the proposed algorithms are compared with a proposed lower bound. Numerical experiments demonstrate that the NPTHGA outperforms the PTHGA algorithm with respect to the solution quality, but the PTHGA outperforms the NPTHGA with respect to the computation time.     

Lot streaming in a two-machine mixed shop

Most classical scheduling models overlook the fact that products are often produced in job lots and assume that job lots are indivisible single entities, although an entire job lot consists of many identical items. However, splitting an entire lot (process batch) into sublots (transfer batches) to be moved to downstream machines allows the overlapping of different operations on the same product while work needs to be completed on the upstream machine. This approach is known as lot streaming in scheduling theory. In this study, the lot streaming problem of multiple jobs in a two-machine mixed shop where there are two different job types as flow shop and open shop is addressed so as to minimize the makespan. The optimal solution method is developed for the mixed shop scheduling problem in which lot streaming can improve the makespan.     

Scheduling algorithms for two-stage reentrant hybrid flow shops: minimizing makespan under the maximum allowable due dates

We consider the scheduling problem in hybrid flow shops that consist of two stages in series, each of which has multiple identical parallel machines. Each job has reentrant flow, i.e., the job visits each production stage several times. The problem is to determine the allocation of jobs to machines as well as the sequence of the jobs assigned to each machine for the objective of minimizing makespan subject to the maximum allowable due dates in the form of a constraint set with a certain allowance. To solve the problem, two types of algorithms are suggested: (a) a branch and bound algorithm that gives optimal semi-permutation schedules; and (b) heuristic algorithms that give non-permutation schedules. To show their performances, computational experiments were done on a number of test problems and the results are reported. In particular, one of the heuristics is competitive to the branch and bound algorithm with respect to the solution quality while requiring much shorter computation times.     

基于工件聚类的并行机调度算法及其应用

针对纺织生产广泛存在的带工件释放时间、以最小化总拖期工件数和总拖期时间为目标的大规模并行机调度问题，提出一种基于工件聚类的遗传算法。该算法将求解过程分为工件聚类和工件排序两个阶段。在工件聚类阶段，基于影响并行机调度性能的重要调度特征量，采用改进的模糊C-均值聚类方法将所有待上机工件分为多个聚类；在工件排序阶段，采用基于规则编码的遗传算法，优化各聚类内工件的加工顺序。数值计算结果及实际应用效果表明，所提出的算法适用于求解带工件释放时间的大规模并行机调度问题。     

A two-criteria objective function flexible flowshop scheduling problem with machine eligibility constraint

This research deals with a flexible flowshop scheduling problem with the arrival and delivery of jobs in groups and processing them individually. Each group of jobs has a specific release time. Due to the special characteristics of each job, only a specific group of machines in each stage are eligible to process that job. All jobs in a group should be delivered at the same time after processing. The objectives of the problem are the minimization of the sum of the completion time of groups on one hand and the minimization of sum of the differences between the completion time of jobs and the delivery time of the group containing that job (waiting period) on the other hand. The problem can be stated as FF_c /r _j , M _j /irreg based on existing scheduling notations. This problem has many applications in the production and service industries such as ceramic tile manufacturing companies and restaurants. A mathematical model has been proposed to solve the problem. Since the research problem is shown to be NP-complete, a particle swarm optimization (PSO) algorithm is applied to solve the problem approximately. Based on the frequency of using local search procedure, four scenarios of PSO have been developed. The algorithms are compared by applying experimental design techniques on random test problems with different sizes. The results show that the PSO algorithm enhanced with local search for all particles has a weaker performance than the other scenarios in solving large-sized problems.     

JIT柔性混合流水车间生产调度问题研究

针对混合柔性流水车间多种工艺路线的生产调度问题,分析了生产工艺计划与车问调度系统的集成原理,建立目标模型,通过将简单遗传算法加以改进,在建立集成模型的基础上,对算法进行研究,把进化后的遗传算法（SGA）和改进的模拟退火算法（SA）有机结合,使算法优化机制融合和优化结构互补,形成较为高效的混合优化算法,并对问题进行求解。最后给出了一个具体算例,验证算法的有效性和先进性。     

Production planning in virtual cell of reconfiguration manufacturing system using genetic algorithm

This paper focuses on the scheduling problem of the reconfiguration manufacturing system (RMS) for execution level, where the final objective is to output a production plan. The practical situation in Chinese factory is analyzed, and the characteristics are summarized into the contradiction between flow and job shop production. In order to handle this problem, a new production planning algorithm in virtual cells is proposed for RMS using an improved genetic algorithm. The advantages of this algorithm have three parts: (1) the virtual cell reconfiguration is formed to assist making production plans through providing relationship among task families and machines from cell formation; (2) The operation buffer algorithm is developed for flow style production in cells, which can realize the nonstop processing for flow style jobs; and (3) The multicell sharing method is proposed to schedule job shop jobs in order to fully utilize manufacturing capability among machines in multicells. Based on the above advantages, an improved genetic algorithm is developed to output scheduling plan. At last, the algorithm is tested in different instances with LINGO and the other genetic algorithm, and then the scheduling solution comparison shows the proposed algorithm can get a better optimum result with the same time using the comparison algorithm.     

面向绿色制造模式调度的Petri网模型及优化算法

针对绿色制造模式的作业车间调度中,不但要缩短生产周期和降低生产成本,而且要减少资源消耗和对环境的负面影响这一问题,建立包含加工时间、生产成本、资源消耗和环境影响等信息的Petri网模型。通过为机器分配工序来消解因机器库所共享引起的冲突,得到表示调度方案的标识图。提出生成可行调度标识图的三种方 法,并采用多目标遗传算法和多目标模拟退火算法相结合的混合算法对其优化。仿真结果表明算法的可行性和有效性。     

基于工序约束并行机模型的冲压线调度

根据双向冲压线的实际生产特点,提出了一种基于工序约束并行机的双向冲压线调度模型.在该模型中,工件同时在牛产线两端按设备顺序加工,且加工工件及其加工开始时间和完工时间受生产线两端工件工序数目约束和生产线设备加工能力的约束,给出了该约束的规则;设计了启发规则和遗传算法混合的求解算法.最后,以最大完工时间为优化指标进行验证,证明该模型具有较好的实用价值.     

A genetic algorithmic approach to multi-objective scheduling in a Kanban-controlled flowshop with intermediate buffer and transport constraints

In this paper, we consider the problem of extended permutation flowshop scheduling with the intermediate buffers. The Kanban flowshop problem considered involves dual-blocking by both part type and queue size acting on machines, as well as on material handling. The objectives considered in this study include the minimization of mean completion time of containers, mean completion time of part types, and the standard deviation of mean completion time of part types. An attempt is made to solve the multi-objective problem by using a proposed genetic algorithm, called the “non-dominated and normalized distance-ranked sorting multi-objective genetic algorithm” (NDSMGA). In order to evaluate the NDSMGA, we have made use of randomly generated flowshop scheduling problems with input and output buffer constraints in the flowshop. The non-dominated solutions for these problems are obtained from each of the existing methods, namely multi-objective genetic local search (MOGLS), elitist non-dominated sorting genetic algorithm (ENGA), gradual priority weighting genetic algorithm (GPWGA), modified MOGLS, and the NDSMGA. These non-dominated solutions are combined to obtain a net non-dominated solution set for a given problem. Contribution in terms of number of solutions to the net non-dominated solution set from each of these algorithms is tabulated, and the results reveal that a substantial number of non-dominated solutions are contributed by the NDSMGA.     

A genetic algorithmic approach to multi-objective scheduling in a kanban-controlled flowshop with intermediate buffer and transport constraints

In this paper, we consider the problem of extended permutation flowshop scheduling with the intermediate buffers. The Kanban flowshop problem considered involves dual-blocking by both part type and queue size acting on machines, as well as on material handling. The objectives considered in this study include the minimization of mean completion time of containers, mean completion time of part types, and the standard deviation of mean completion time of part types. An attempt is made to solve the multi-objective problem by using a proposed genetic algorithm, called the “non-dominated and normalized distanceranked sorting multi-objective genetic algorithm” (NDSMGA). In order to evaluate the NDSMGA, we have made use of randomly generated flowshop scheduling problems with input and output buffer constraints in the flowshop. The non-dominated solutions for these problems are obtained from each of the existing methods, namely multi-objective genetic local search (MOGLS), elitist non-dominated sorting genetic algorithm (ENGA), gradual priority weighting genetic algorithm (GPWGA), modified MOGLS, and the NDSMGA. These non-dominated solutions are combined to obtain a net non-dominated solution set for a given problem. Contribution in terms of number of solutions to the net non-dominated solution set from each of these algorithms is tabulated, and the results reveal that a substantial number of non-dominated solutions are contributed by the NDSMGA.     

Scheduling in aerospace composite manufacturing systems: a two-stage hybrid flow shop problem

This research investigates a real-world complex two-stage hybrid flow shop scheduling problem which is faced during the manufacturing of composite aerospace components. There are a number of new constraints to be taken into account in this special hybrid flow shop, in particular limited physical capacity of the intermediate buffer, limited waiting time between processing stages, and limited tools/molds used in both stages in each production cycle. We propose a discrete-time mixed integer linear programming model with an underlying branch and bound algorithm, to solve small- and medium-size problems (up to 100 jobs). To solve the large instances of the problem (up to 300 jobs), a genetic algorithm with a novel crossover operator is developed. A new heuristic method is introduced to generate the initial population of the genetic algorithm. The results show the high level of computational efficiency and accuracy of the proposed genetic algorithm when compared to the optimal solutions obtained from the mathematical model. The results also show that the proposed genetic algorithm outperforms the conventional dispatching rules (i.e., shortest processing time, earliest dues date and longest processing time) when applied to large-size problems. A real case study undertaken at one of the leading aerospace companies in Canada is used to formulate the model, collect data for the parameters of the model, and analyze the results.