Scheduling distributed flowshops with flexible assembly and set-up time to minimise makespan

The scheduling problems under distributed production or flexible assembly settings have achieved increasing attention in recent years. This paper considers scheduling the integration of these two environments and proposes an original distributed flowshop scheduling problem with flexible assembly and set-up time. Distributed production stage is deployed several homogeneous flowshop factories that process the jobs to be assembled into final products in the flexible assembly stage. The objective is to find a schedule, including a production subschedule for jobs and an assembly subschedule for products, to minimise the makespan. Such a scheduling problem involves four successive decisions: assigning jobs to production factories, sequencing jobs at every factory, designating an assembly machine for each product and sequencing products on each assembly machine. The computational model is first established, and then a constructive heuristic (TPHS) and two hybrid metaheuristics (HVNS and HPSO) are proposed. Numerical experiments have been carried out and results validate the algorithmic feasibility and effectiveness. TPHS can obtain reasonable solutions in a shorter time, while metaheuristics can report better solutions using more yet acceptable time. HPSO is statistically comparable yet less robust compared with HVNS for small-scale instances. For the large-scale case, HPSO outperforms HVNS on both effectiveness and robustness.     

Meta-heuristics for the distributed two-stage assembly scheduling problem with bi-criteria of makespan and mean completion time

This paper focuses on the distributed two-stage assembly flowshop scheduling problem for minimising a weighted sum of makespan and mean completion time. This problem involves two inter-dependent decision sub-problems: (1) how to allocate jobs among factories and (2) how to schedule the assigned jobs at each factory. A mathematical model is formulated for solving the small-sized instances of the problem. Since the NP-hardness of the problem, we also proposed a variable neighbourhood search (VNS) algorithm and a hybrid genetic algorithm combined with reduced variable neighbourhood search (GA-RVNS) to solve the distributed two-stage assembly flowshop scheduling problems and approximately optimise makespan and mean completion time simultaneously. Computational experiments have been conducted to compare the performances of the model and proposed algorithms. For a set of small-sized instances, both the model and the proposed algorithms are effective. The proposed algorithms are further evaluated on a set of large-sized instances. The results statistically show that both GA-RVNS and VNS obtain much better performances than the GA without RVNS-based local search step (GA-NOV). For the instances with small numbers of jobs, VNS achieves better performances than GA-RVNS. However, for the instances with large numbers of jobs, GA-RVNS yields better performances than the VNS. It is also shown that the overall performances of VNS are very close to GA-RVNS with different numbers of factories, weights given to makespan and numbers of machines at the first stage.     

A hybrid Tabu sample-sort simulated annealing approach for solving distributed scheduling problem

The distributed scheduling problem has been considered as the allocation of a task to various machines in such a way that these machines are situated in different factories and these factories are geographically distributed. Therefore distributed scheduling has fulfilled various objectives, such as allocation of task to the factories and machines in such a manner that it can utilise the maximum resources. The objective of this paper is to minimise the makespan in each factory by considering the transportation time between the factories. In this paper, to address such a problem of scheduling in distributed manufacturing environment, a novel algorithm has been developed. The proposed algorithm gleans the ideas both from Tabu search and sample sort simulated annealing. A new algorithm known as hybrid Tabu sample-sort simulated annealing (HTSSA) has been developed and it has been tested on the numerical example. To reveal the supremacy of the proposed algorithm over simple SSA and Tabu search, more computational experiments have also been performed on 10 randomly generated datasets.     

An improved artificial bee colony algorithm for addressing distributed flow shop with distance coefficient in a prefabricated system

This paper proposes an improved artificial bee colony (IABC) algorithm for addressing the distributed flow shop considering the distance coefficient found in precast concrete production system, with the minimisation of the makespan. In the proposed algorithm, each solution is first represented by a two-dimensional vector, where the first dimensional vector is the factory and the second dimensional vector lists the operation scheduling sequence of each factory. Second, considering the distributed problem feature, a distributed iterated greedy heuristic (DIG) is developed where destruction and construction processes are designed in detail while considering the distributed structures. Third, an efficient population initialisation method that considers the factory workload balance is presented. Then, a local search approach that randomly replaces two factories with two randomly selected jobs and that finds an optimal position for the two inserted operations via the DIG method is proposed. For the canonical ABC algorithm, using the DIG approach, the main three parts are improved, namely, the employee, onlooker, and scout bees. Finally, the proposed algorithm is tested on sets of extended instances based on the well-known benchmarks. Through an analysis of the experimental results, the highly effective proposed IABC algorithm is compared to several efficient algorithms drawn from the literature.     

A bounded-search iterated greedy algorithm for the distributed permutation flowshop scheduling problem

As the interest of practitioners and researchers in scheduling in a multi-factory environment is growing, there is an increasing need to provide efficient algorithms for this type of decision problems, characterised by simultaneously addressing the assignment of jobs to different factories/workshops and their subsequent scheduling. Here we address the so-called distributed permutation flowshop scheduling problem, in which a set of jobs has to be scheduled over a number of identical factories, each one with its machines arranged as a flowshop. Several heuristics have been designed for this problem, although there is no direct comparison among them. In this paper, we propose a new heuristic which exploits the specific structure of the problem. The computational experience carried out on a well-known testbed shows that the proposed heuristic outperforms existing state-of-the-art heuristics, being able to obtain better upper bounds for more than one quarter of the problems in the testbed.     

基于改进遗传算法的导向辊生产调度方法研究

目的 研究导向辊生产车间中的调度优化问题,有利于缩短工件的完工时间,提高产线生产效率。方法 以某导向辊生产车间为研究对象,以最小化最大完工时间为目标建立数学模型。针对该导向辊生产车间的实际工况,提出一种改进的遗传算法进行求解。通过对10种不同尺寸的导向辊进行生产调度,分别采用改进的遗传算法和传统遗传算法进行试验分析。结果 改进的遗传算法相比传统遗传算法寻优能力更高,工件的完工时间从139 min缩短为113 min,缩短了18.7%左右,生成了完工时间为113 min的生产调度甘特图。结论 与传统遗传算法相比,改进的遗传算法在导向辊生产调度优化中具有更高的全局优化能力和寻优精度。     

Scheduling continuous aluminium casting lines

This study considers the problem of scheduling casting lines of an aluminium casting and processing plant. In aluminium processing plants, continuous casting lines are the bottleneck resources, i.e. factory throughput is limited by the amount of aluminium that can be cast. The throughput of a casting line might be increased by minimizing total setup time between jobs. The objective is to minimize setup time on production lines for a given time period while balancing workload between production lines to accommodate potential new orders. A mathematical formulation for scheduling jobs to minimize the total setup time while achieving workload balance between the production lines is presented. Since the casting scheduling problem is an NP-hard problem, even with only one casting line, a four-step algorithm to find good solutions in a reasonable amount of time is proposed. In this process, a set of asymmetric travelling salesman problems is followed by a pairwise exchange heuristic. The proposed procedure is applied to a case study using real casting data.     

Scheduling with shutdowns and sequence dependent set-up times

This paper considers a single machine scheduling problem with ready and due times constraints on jobs, shutdown constraints on the machine and sequence dependent set-up times among jobs. The shutdown is a disruptive event such as holiday, breaks or machine maintenance, and has a prespecified period when the machine will be interrupted. If no pre-emption is allowed for jobs, shutdown constraints divide the planning horizon into disconnected time windows. An optimization algorithm based on the branch-and-bound method is developed to minimize the maximum tardiness for solving the problem. This paper further develops the post-processing algorithm that manipulates the starting time of the shutdown period so as to reduce the obtained maximum tardiness. The post-processing algorithm can determine plural schedules to reduce the maximum tardiness, and the production manager will select the objective schedule among them for the interest of overall efficiency. Computational results for the proposed algorithms will indicate that the post-processing algorithm can improve upon the original solution and the problems with multiple shutdowns and with set-up times varying widely can be satisfactorily solved.     

A divide-and-conquer strategy with particle swarm optimization for the job shop scheduling problem

An optimization algorithm based on the ‘divide-and-conquer’ methodology is proposed for solving large job shop scheduling problems with the objective of minimizing total weighted tardiness. The algorithm adopts a non-iterative framework. It first searches for a promising decomposition policy for the operation set by using a simulated annealing procedure in which the solutions are evaluated with reference to the upper bound and the lower bound of the final objective value. Subproblems are then constructed according to the output decomposition policy and each subproblem is related to a subset of operations from the original operation set. Subsequently, all these subproblems are sequentially solved by a particle swarm optimization algorithm, which leads directly to a feasible solution to the original large-scale scheduling problem. Numerical computational experiments are carried out for both randomly generated test problems and the real-world production data from a large speed-reducer factory in China. Results show that the proposed algorithm can achieve satisfactory solution quality within reasonable computational time for large-scale job shop scheduling problems.     

Scheduling a tempered glass manufacturing system: a three-stage hybrid flow shop model

Chinese tempered glass has entered a fast and stable growing era. To improve the productivity of tempered glass manufacturers, this paper investigates a scheduling problem in tempered glass production system, originated from a tempered glass manufacturer in China. This problem can be formulated as a three-stage hybrid flow shop (HFS). Single and batch processing machines coexist in this HFS. Besides, a limited buffer, between the first two stages, and machine eligibility requirement are also significant characteristics. To address this complicated scheduling problem, we first establish an integer programming model with the objective of minimising the makespan, i.e. the maximum completion time of jobs in the system. Due to the strong NP-hard nature of the problem, we then propose a constructive heuristic method, a genetic algorithm, as well as a simulated annealing algorithm, to solve practical large-scale problems. Computational results demonstrate the efficiency of the proposed approaches.     

A coordinated algorithm for integrated production scheduling and vehicle routing problem

In this paper, the integrated production scheduling and vehicle routing problem is considered for a Make-to-Order manufacturer, who has a single machine for production and limited vehicles with capacity constraints for transportation. The objective is to determine production scheduling and vehicle routing, which are two interacted decisions, to minimise the maximum order delivery time. A property on optimal production sequence is proposed first, based on which backward and forward batching methods are developed and are embedded into a proposed genetic algorithm. The proposed genetic algorithm is capable of providing high-quality solutions by determining the two decisions simultaneously. For comparison purpose, a two-stage algorithm is developed, which decomposes the overall problem into two successively solved sub-problems. The experiments show that the proposed genetic algorithm can provide higher quality solutions than the proposed two-stage algorithm and two published algorithms studying related problems.     

A scatter search approach to sequence-dependent setup times job shop scheduling

Scheduling jobs on multiple machines is a difficult problem when real-world constraints such as the sequence setup time, setup times for jobs and multiple criteria are used for solution goodness. It is usually sufficient to obtain a near-optimal solution quickly when an optimal solution would require days or weeks of computation. Common scheduling heuristics such as Shortest Processing Time can be used to obtain a feasible schedule quickly, but are not designed for multiple simultaneous objectives. We use a new meta-heuristic known as a scatter search (SS) to solve these types of job shop scheduling problems. The results are compared with solutions obtained by common heuristics, a tabu search, simulated annealing, and a genetic algorithm. We show that by combining the mechanism of diversification and intensification, SS produces excellent results in a very reasonable computation time. The study presents an efficient alternative for companies with a complicated scheduling and production situation.     

Development of a hybrid metaheuristic to minimise earliness and tardiness in a hybrid flowshop with sequence-dependent setup times

This paper presents an efficient hybrid metaheuristics for scheduling jobs in a hybrid flowshop with sequence-dependent setup times. The problem is to determine a schedule that minimises the sum of earliness and tardiness of jobs. Since this problem class is NP-hard in the strong sense, there seems to be no escape from appealing to metaheuristic procedures to achieve near-optimal solutions for real life problems. This paper proposes the hybrid metaheuristic algorithm which comprises three components: an initial population generation method based on an ant colony optimisation, a simulated annealing algorithm as an evolutionary algorithm that employs certain probability to avoid becoming trapped in a local optimum, and a variable neighbourhood search which involves three local search procedures to improve the population. A design of experiments approach is employed to calibrate the parameters of the algorithm. Results of computational tests in solving 252 problems up to 100 jobs have shown that the proposed algorithm is computationally more effective in yielding solutions of better quality than the adapted random key genetic algorithm and immune algorithm presented previously.     

Minimising makespan in distributed permutation flowshops using a modified iterated greedy algorithm

The distributed permutation flowshop scheduling problem (DPFSP) is a newly proposed topic in the shop scheduling field, which has important application in globalised and multi-plant environments. This study presents a modified iterated greedy (MIG) algorithm for this problem to minimise the maximum completion time among all the factories. Compared with previous approaches, the proposed algorithm is simpler yet more effective, more efficient, and more robust in solving the DPFSP. To validate the performance of the proposed MIG algorithm, computational experiments and comparisons are conducted on an extended benchmark problem set of Taillard. Despite its simplicity, the computational results show that the proposed MIG algorithm outperforms all existing algorithms, and the best-known solutions for almost half of instances are updated. This study can be offered as a contribution to the growing body of work on both theoretically and practically useful approaches to the DPFSP.     

考虑急件到达的单机鲁棒调度方法

实际生产过程中经常会有急件到达。由于急件的优先级最高,其到达容易扰乱初始调度,使实际调度性能恶化,影响调度目标的实现。针对以总拖期为目标且带有释放时间的单机调度问题,研究了在有急件到达情况下的鲁棒调度方法,以降低急件对实际调度性能的影响。鉴于该调度问题是NP hard问题,根据工件释放时间和交货期的关系构造“金字塔”结构,获得该调度问题的占优性质。根据这些占优性质和急件到达特点,研究急件到达情景下的占优规则,据此求解急件到达情景下的占优调度集合,作为鲁棒调度的备选调度方案集合。提出了应对急件到达的鲁棒调度算法。给出仿真算例验证了算法的有效性,算例表明本文给出的鲁棒调度方法能有效避免急件到达造成实际调度性能的恶化。      

多品种小批量订单型企业生产调度优化

目的研究多品种小批量订单型企业的生产调度优化问题,方法针对S公司的生产现状,应用遗传算法思想设计调度优化方案,采用不等长矩阵的编码方式实现订单的批量生产及车间排产的方案。结果通过仿真分析和S公司生产调度的实际应用,验证了该算法的可行性及有效性。结论基于遗传算法的调度优化算法实现了多品种小批量流程型生产企业生产调度优化,达到了缩短生产周期、有效利用生产资源的目的。     

Scheduling job shop associated with multiple routings with genetic and ant colony heuristics

The general job shop problem is one of the well known machine scheduling problems, in which the operation sequence of jobs are fixed that correspond to their optimal process plans and/or resource availability. Scheduling and sequencing problems, in general, are very difficult to solve to optimality and are well known as combinatorial optimisation problems. The existence of multiple job routings makes such problems more cumbersome and complicated. This paper addresses a job shop scheduling problem associated with multiple job routings, which belongs to the class of NP hard problems. To solve such NP-hard problems, metaheuristics have emerged as a promising alternative to the traditional mathematical approaches. Two metaheuristic approaches, a genetic algorithm and an ant colony algorithm are proposed for the optimal allocation of operations to the machines for minimum makespan time criterion. ILOG Solver, a scheduler package, is used to evaluate the performance of the proposed algorithms. The comparison reveals that both the algorithms are capable of providing solutions better than the solution obtained with ILOG Solver.     

Scheduling with multi-attribute set-up times on unrelated parallel machines

This paper studies a problem in the knitting process of the textile industry. In such a production system, each job has a number of attributes and each attribute has one or more levels. Because there is at least one different attribute level between two adjacent jobs, it is necessary to make a set-up adjustment whenever there is a switch to a different job. The problem can be formulated as a scheduling problem with multi-attribute set-up times on unrelated parallel machines. The objective of the problem is to assign jobs to different machines to minimise the makespan. A constructive heuristic is developed to obtain a qualified solution. To improve the solution further, a meta-heuristic that uses a genetic algorithm with a new crossover operator and three local searches are proposed. The computational experiments show that the proposed constructive heuristic outperforms two existed heuristics and the current scheduling method used by the case textile plant.     

Decision-making on multi-mould maintenance in production scheduling

The reliability of a critical tool like a mould on a machine affects the productivity seriously in many manufacturing firms. In fact, its breakdown frequency is even higher than machines. The decision-making on when mould maintenance should be started become a challenging issue. In the previous study, the mould maintenance plans were integrated with the traditional production schedules in a plastics production system. It was proven that considering machine and mould maintenance in production scheduling could improve the overall reliability and productivity of the production system. However, the previous model assumed that each job contained single operation. It is not workable in other manufacturing systems such as die stamping which may contain multiple operations with multiple moulds in each job. Thus, this study models a new problem for multi-mould production-maintenance scheduling. A genetic algorithm approach is applied to minimise the makespan of all jobs in 10 hypothetical problem sets. A joint scheduling (JS) approach is proposed to decide the start times of maintenance activities during scheduling. The numerical result shows that the JS approach has a good performance in the new problem and it is sensitive to the characteristic of the setup time defined.     

Hybrid flowshop scheduling with family setup time and inconsistent family formation

This research considers a hybrid flowshop scheduling problem where jobs are organised in families according to their machine settings and tools. The family setup time arises when a machine shifts from processing one job family to another. The problem is compounded by the challenges that the formation of job families is different in different stages and only a limited number of jobs can be processed within one setup. This type of problem is common in the production process of standard metal components. This paper aims to propose two approaches to solve this problem. One is a metaheuristic in the form of a genetic algorithm and the other is a heuristic. The proposed approaches are compared and contrasted against the two relevant metaheuristic and heuristic adapted from solving a generalised sequence-dependent setup flowshop problem. Comparative results indicate that the proposed genetic algorithm has better performance on minimising makespan and the heuristic is more effective on reducing family setup time.