A dynamic scheduling algorithm for singe-arm two-cluster tools with flexible processing times

This article presents a dynamic algorithm for job scheduling in two-cluster tools producing multi-type wafers with flexible processing times. Flexible processing times mean that the actual times for processing wafers should be within given time intervals. The objective of the work is to minimize the completion time of the newly inserted wafer. To deal with this issue, a two-cluster tool is decomposed into three reduced single-cluster tools (RCTs) in a series based on a decomposition approach proposed in this article. For each single-cluster tool, a dynamic scheduling algorithm based on temporal constraints is developed to schedule the newly inserted wafer. Three experiments have been carried out to test the dynamic scheduling algorithm proposed, comparing with the results the ‘earliest starting time’ heuristic (EST) adopted in previous literature. The results show that the dynamic algorithm proposed in this article is effective and practical.     

Multi-degree cyclic hoist scheduling with time window constraints

This paper deals with the multi-degree cyclic single-hoist scheduling problem with time window constraints, in which multiple identical parts enter and leave the system during each cycle. We propose an analytical mathematical model and a branch-and-bound algorithm so as to find a cyclic sequence of hoist moves that maximises the throughput. The branch-and-bound algorithm implicitly enumerates the sequence of hoist moves and requires the solution of a specific set of linear programming problems (LPPs). Computational results on benchmark instances and randomly generated test instances are presented.     

Transient inter-production scheduling based on Petri nets and constraint programming

In this article, we focus on the transient inter-production scheduling problem between two cyclic productions in the framework of flexible manufacturing systems. This problem is first formulated as a reachability problem in timed Petri nets (TPN), then solved using a methodology based on constraint programming. Our work is based on the controlled executions proposed by Chretienne to model the sequence of transition firing dates. Our methodology is based on a preliminary resolution of the state equation between initial and final states in the underlying non-TPN. Then, we choose a duration T _max corresponding to the maximal duration time of the scheduling. For each solution S of the state equation, we build a controlled execution from the sequence of firings in S. After the propagation of firing date constraints and reachability constraints in the TPN, we use constraint programming to enumerate the set of feasible controlled executions.     

Cross-docking truck scheduling with product unloading/loading constraints based on an improved particle swarm optimisation algorithm

Cross-docking is a very useful logistics technique that can substantially reduce distribution costs and improve customer satisfaction. A key problem in its success is truck scheduling, namely, decision on assignment and docking sequence of inbound/outbound trucks to receiving/shipping dock doors. This paper focuses on the problem with the requirement of unloading/loading products in a given order, which is very common in many industries, but is less concerned by existing researches. An integer programming model is established to minimise the makespan. An improved particle swarm optimisation (ωc-PSO) algorithm is proposed for solving it. In the algorithm, a cosine decreasing strategy of inertia weight is designed to dynamically balance global and local search. A repair strategy is put forward for continuous search in the feasible solution space and a crossover strategy is presented to prevent the algorithm from falling into local optimum. After algorithm parameters are tuned using Taguchi method, computational experiments are conducted on different problem scales to evaluate ωc-PSO against genetic algorithm, basic PSO and GLNPSO. The results show that ωc-PSO outperforms other three algorithms, especially when the number of dock doors, trucks and product types is great. Statistical tests show that the performance difference is statistically significant.     

Active robustness of a milk manufacturing workshop with time constraints

This paper deals with the active robustness of a milk manufacturing workshop including time interval constraints. Such systems have robustness properties towards time disturbances. The robustness property can be a static property, but using a dynamic control strategy may increase the robustness value. Controlled P-time Petri nets are used as a modelling tool. Some definitions and a series of lemmas are cited in order to build a theory dealing with robustness problems. In order to avoid the death of marks at the synchronisation transitions of the P-time Petri net model, a robust control strategy facing time disturbances is presented. The proposed approach tries to reject the disturbance as soon as it is observed. Furthermore, this approach is used by an algorithm computing an active robustness margin at a given node. It is illustrated step by step on an example of a milk manufacturing workshop. A comparison with the bound provided for the passive robustness is made.     

A hybrid scheduling approach for automated flowshops with material handling and time constraints

Flowshop scheduling problems have been extensively studied by several authors using different approaches. A typical flowshop process consists of successive manufacturing stages arranged in a single production line where different jobs have to be processed following a predefined production recipe. In this work, the scheduling of a complex flowshop process involving automated wet-etch station from semiconductor manufacturing systems requires a proper synchronisation of processing and transport operations, due to stringent storage policies and fixed transfer times between stages. Robust hybrid solution strategies based on mixed integer linear programming formulations and heuristic-based approaches, such as aggregation and decomposition methods, are proposed and illustrated on industrial-scale problems. The results show significant improvements in solution quality coupled with a reduced computational effort compared to other existing methodologies.     

Schedule robustness analysis with the help of attainable sets in continuous flow problem under capacity disruptions

Continuous flow scheduling problems have their place in many industries such as gas, oil, chemicals, glass and fluids production as well as production of granular goods and steel details. The disruptions in processing capacities may result in schedule performance decrease. In this paper, we develop a new method for robustness analysis of those schedules that are formulated in continuous time in the state-space domain. The developed method is based on attainable sets (ASs) that allow computing a form to represent the states and performance of schedules in regard to different capacity degradation levels. Having such a form, it becomes possible to estimate the schedule robustness. The technical development and approximation of ASs are presented. A robustness index is developed on the basis of the minimax regret approach, and it can be used for decision-makers regarding the trade-off ‘performance vs. robustness’. As such, it becomes possible to compare maximal possible profits in situations without disruptions and realistic profits subject to some robustness investments and costs of protection against disruptions. With the presented results, it becomes possible to obtain ASs for interval data with no a priori information about perturbation impacts, i.e. for non-stationary perturbations. ASs permit to consider perturbations and schedule performances as time functions. Perturbation functions may be set up for different uncertainty scenarios, including interval perturbations.     

Open shop scheduling problem with a multi-skills resource constraint: a genetic algorithm and an ant colony optimisation approach

The continuous evolution of manufacturing environments leads to a more efficient production process that controls an increasing number of parameters. Production resources usually represent an important constraint in a manufacturing activity, specially talking about the management of human resources and their skills. In order to study the impact of this subject, this paper considers an open shop scheduling problem based on a mechanical production workshop to minimise the total flow time including a multi-skill resource constraint. Then, we count with a number of workers that have a versatility to carry out different tasks, and according to their assignment a schedule is generated. In that way, we have formulated the problem as a linear as and a non-linear mathematical model which applies the classic scheduling constraints, adding some different resources constraints related to personnel staff competences and their availability to execute one task. In addition, we introduce a genetic algorithm and an ant colony optimisation (ACO) method to solve large size problems. Finally, the best method (ACO) has been used to solve a real industrial case that is presented at the end.     

Integrated scheduling of production and delivery with time windows

This paper deals with an integrated scheduling problem in which orders have been processed by a distribution centre and then delivered to retailers within time windows. We propose a nonlinear mathematical model to minimise the time required to complete producing the product, delivering it to retailers and returning to the distribution centre. The optimal schedule and vehicle routes can be determined simultaneously in the model. In addition, two kinds of genetic-algorithm-based heuristics are designed to solve the large-scale problems. The conventional genetic algorithm provides the search with a high transition probability in the beginning of the search and with a low probability toward the end of the search. The adaptive genetic algorithm provides an adaptive operation rate control scheme that changes rate based on the fitness of the parents. The experimental results have shown that the solution quality of these two algorithms is not significant but that the adaptive genetic algorithm can save more time in finding the best parameter values of the genetic algorithm.     

Design of high-performing hybrid meta-heuristics for unrelated parallel machine scheduling with machine eligibility and precedence constraints

This study involves an unrelated parallel machine scheduling problem in which sequence-dependent set-up times, different release dates, machine eligibility and precedence constraints are considered to minimize total late works. A new mixed-integer programming model is presented and two efficient hybrid meta-heuristics, genetic algorithm and ant colony optimization, combined with the acceptance strategy of the simulated annealing algorithm (Metropolis acceptance rule), are proposed to solve this problem. Manifestly, the precedence constraints greatly increase the complexity of the scheduling problem to generate feasible solutions, especially in a parallel machine environment. In this research, a new corrective algorithm is proposed to obtain the feasibility in all stages of the algorithms. The performance of the proposed algorithms is evaluated in numerical examples. The results indicate that the suggested hybrid ant colony optimization statistically outperformed the proposed hybrid genetic algorithm in solving large-size test problems.     

Modelling and optimization of a bi-objective flow shop scheduling with diverse maintenance requirements

In real-world problems, machines cannot continuously operate and have to stop for maintenance before they fail. Lack of maintenance can also affect the performance of machines in processing jobs. In this paper, a permutation flow shop scheduling problem with multiple age-based maintenance requirements is modelled as a novel mixed-integer linear program in which the objectives are conflicting. In modelling the problem, we assume that infrequent maintenance can prolong job processing times. One of the objectives is to minimise the total maintenance cost by planning as few maintenance activities as possible to only meet the minimum requirements, and the other objective tries to minimise the total tardiness by sequencing the jobs and planning the maintenance activities in such a way that the processing times are not prolonged and unnecessary maintenance times are avoided. Because of this conflict, an interactive fuzzy, bi-objective model is introduced. Application of the model is illustrated through a case study for operations and maintenance scheduling of heavy construction machinery. An effective and efficient solution methodology is developed based on the structure of the problem and tested against commercial solvers and a standard GA. Computational results have verified the efficiency of the proposed solution methodology and show that unlike the proposed method, a generic metaheuristic that does not consider the unique structure of the problem can become ineffective for real-world problem sizes.     

The impact of human consideration,schedule types and product mix on scheduling objectives for unpaced mixed-model assembly lines

There is an increasing awareness in scheduling research that human behaviour needs to be considered explicitly in scheduling models. Although most scheduling literature ignores human behaviour, especially sequence-dependent processing times form a good basis for explicit consideration. Hence, a processing time function is derived that considers the effects of learning, forgetting, fatigue and recovery. The necessity for explicit human consideration can be regarded as most urgent for unpaced highly-manual mixed-model assembly lines. Based on real data a simulation study is conducted to determine the effect of explicit human consideration while also taking into account the effects of different idealised schedule types and the product mix. The results strongly indicate that the product mix has a consistently high impact on scheduling objectives, the schedule type affects lower-level objectives like starving and blocking times to a greater extent than higher-level objectives like makespan and flow time, and that for certain objectives the height of the objective values and the relative favourability of schedule types depends on human consideration.     

An improved multi-objective evolutionary algorithm based on decomposition for energy-efficient permutation flow shop scheduling problem with sequence-dependent setup time

With the increasing attention on environment issues, green scheduling in manufacturing industry has been a hot research topic. As a typical scheduling problem, permutation flow shop scheduling has gained deep research, but the practical case that considers both setup and transportation times still has rare research. This paper addresses the energy-efficient permutation flow shop scheduling problem with sequence-dependent setup time to minimise both makespan as economic objective and energy consumption as green objective. The mathematical model of the problem is formulated. To solve such a bi-objective problem effectively, an improved multi-objective evolutionary algorithm based on decomposition is proposed. With decomposition strategy, the problem is decomposed into several sub-problems. In each generation, a dynamic strategy is designed to mate the solutions corresponding to the sub-problems. After analysing the properties of the problem, two heuristics to generate new solutions with smaller total setup times are proposed for designing local intensification to improve exploitation ability. Computational tests are carried out by using the instances both from a real-world manufacturing enterprise and generated randomly with larger sizes. The comparisons show that dynamic mating strategy and local intensification are effective in improving performances and the proposed algorithm is more effective than the existing algorithms.     

Optimisation of block erection scheduling based on a Petri net and discrete PSO

The shipyard block erection system (SBES) is a typical discrete-event dynamic system. To model multiprocessing paths and a concurrent assembly procedure, a timed Petri net (TPN) is proposed. The definition of a Petri net is extended to accord with the real-world SBES organisation. The basic TPN modules are presented to model the corresponding variable structures in the SBES, and then the scheduling model of the whole SBES is easily constructed. A modified discrete particle swarm optimisation (PSO) based on the reachability analysis of Petri nets is developed for scheduling of the SBES. In the proposed algorithm, particles are coded by welding transitions and selecting places of the TPN model, and then the collaboration and competition of particle individuals is simulated by crossover and mutation operators in a genetic algorithm. Numerical simulation suggests that the proposed TPN–PSO scheduler can provide an improvement over the conventional scheduling method. Finally, a case study of the optimisation of a back block erection process is provided to illustrate the effectiveness of the method.     

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.     

基于演化算法的带频率约束的桁架结构形状和尺寸优化

具有频率约束的桁架结构形状和尺寸优化设计是一个难度大的非线性动力优化问题。形状和尺寸变量的耦合通常导致收敛困难,而频率约束则使得动力灵敏度分析困难,传统的优化准则法和数学规划法难于求解。将单纯形算法、子空间变维技术、均匀变异有机融入郭涛算法,提出一种混合演化算法,避开繁琐的动力灵敏度分析,简单、有效地求解这类桁架形状和尺寸优化问题。典型的桁架算例验证了算法的有效性和可靠性。     

The effect of work content imbalance and its interaction with scheduling method on sequential flow line performance

Uneven workflow in serial flow lines is common when job work content varies. Unfortunately, work content imbalance between stations or between jobs degrades system performance. The effect of this imbalance can be mitigated by proper job sequencing. In this paper, we uncouple the influence of station-to-station and job-to-job imbalance within a set of jobs, introducing metrics to quantify the degree of imbalance, and determine their impact on line performance. We then examine the sensitivity of several scheduling methods at different problem scales and processing time variance levels, and compare the sensitivity to process time stability radii. Within the case studies explored, we determine that greater station imbalance can degrade solution quality regardless of problem scale and variance level. Greater job imbalance can either improve or diminish solution quality (i.e. relative performance from a given scheduling method), but less than station imbalance. Scheduling methods that sequence jobs based on the sums of processing times, e.g. SPT, can benefit from greater station imbalance. Scheduling methods that sequence jobs based on idle time between stations, e.g. the state-space heuristic, are more sensitive to station imbalance, but can also benefit from job imbalance. Finally, we conclude that job sequence has a greater impact on solution quality than stability radii.     

Developing a new model for simultaneous scheduling of two grand projects based on game theory and solving the model with Benders decomposition

Grand infrastructure projects, such as dam, power plant, petroleum, and gas industry projects, have several contractors working on them in several independent sub-projects. The concern of reducing the duration of these projects is one of the important issues among various aspects; thus, our aim is to fulfill the requirements by using the game theory approach. In this study, a mixed-integer programming model consisting of game theory and project scheduling is developed to reduce the duration of projects with a minimum increase in costs. In this model, two contractors in successive periods are entered into a step-by-step competition by the employer during dynamic games, considering an exchange in their limited resources. The optimum solution of the game in each stage are selected as the strategy, and the resources during the game are considered to be renewable and limited. The strategy of each contractor can be described as follows: 1) share their resources with the other contractor and 2) not share the resources with the other contractor. This model can act dynamically in all circumstances during project implementation. If a player chooses a non-optimum strategy, then this strategy can immediately update itself at the succeeding time period. The proposed model is solved using the exact Benders decomposition method, which is coded in GAMS software. The results suggest the implementation of four step-by-step games between the contractors. Then, the results of our model are compared with those of the conventional models. The projects’ duration in our model is reduced by 22.2%. The nominal revenue of both contractors has also reached a significant value of 46078 units compared with the relative value of zero units in the original model. Moreover, we observed in both projects the decreases of 19.5%, 20.9%, and 19.7% in the total stagnation of resources of types 1, 2, and 3, respectively.     

基于仿真的长距离引水隧洞施工全过程进度实时控制与可视化分析研究

长距离引水隧洞常具有埋深大、洞线长、洞径大和工程地质条件极其复杂等特点,各工序工程量大,相互间影响巨大,因此,在实际施工过程中内外环境和约束条件可能发生变化,使原定的施工进度计划与实际施工进程不可避免地产生偏差。如果这种偏差不及时纠正,将会越来越大,以致原计划进度起不到指导实际施工的作用。文章利用计算机仿真技术、控制论思想和虚拟现实技术,提出了基于仿真的长距离引水隧洞施工全过程进度实时控制与可视化分析方法,对施工进度的实时控制提供了可行性研究和科学依据。