A hybrid Pareto-based local search algorithm for multi-objective flexible job shop scheduling problems

This paper presents a hybrid Pareto-based local search (PLS) algorithm for solving the multi-objective flexible job shop scheduling problem. Three minimisation objectives are considered simultaneously, i.e. the maximum completion time (makespan), the total workload of all machines, and the workload of the critical machine. In this study, several well-designed neighbouring approaches are proposed, which consider the problem characteristics and thus can hold fast convergence ability while keep the population with a certain level of quality and diversity. Moreover, a variable neighbourhood search (VNS) based self-adaptive strategy is embedded in the hybrid algorithm to utilise the neighbouring approaches efficiently. Then, an external Pareto archive is developed to record the non-dominated solutions found so far. In addition, a speed-up method is devised to update the Pareto archive set. Experimental results on several well-known benchmarks show the efficiency of the proposed hybrid algorithm. It is concluded that the PLS algorithm is superior to the very recent algorithms, in term of both search quality and computational efficiency.     

求解一类无关并行机调度的遗传迭代贪心算法

以最小化最大完工时间为优化目标,建立带工单加工约束和序相关设置时间无关并行机调度问题的混合整数规划模型;考虑现实生产对求解算法在质量、收敛速度和鲁棒性等方面的较高要求,构建一种混合遗传-迭代贪心算法。在遗传变异操作中嵌入一种迭代贪心策略的破坏和构建机制,用于提高算法的种群多样性;引入基于破坏与构建操作设计而成的快速局部搜索算法来增强算法的局部开发能力;基于实际生产数据的相关特征随机生成了一系列计算案例,并通过实验说明所提新型混合算法相较于传统混合算法的优越性。     

Adaptive scheduling and tool flow control in flexible job shops

The recent manufacturing environment is characterized as having diverse products due to mass customization, short production lead-time, and ever-changing customer demand. Today, the need for flexibility, quick responsiveness, and robustness to system uncertainties in production scheduling decisions has dramatically increased. In traditional job shops, tooling is usually assumed as a fixed resource. However, when a tooling resource is shared among different machines, a greater product variety, routing flexibility with a smaller tool inventory can be realized. Such a strategy is usually enabled by an automatic tool changing mechanism and tool delivery system to reduce the time for tooling set-up, hence it allows parts to be processed in small batches. In this paper, a dynamic scheduling problem under flexible tooling resource constraints is studied and presented. An integrated approach is proposed to allow two levels of hierarchical, dynamic decision making for job scheduling and tool flow control in flexible job shops. It decomposes the overall problem into a series of static sub-problems for each scheduling horizon, handles random disruptions by updating job ready time, completion time, and machine status on a rolling horizon basis, and considers the machine availability explicitly in generating schedules. The effectiveness of the proposed dynamic scheduling approach is tested in simulation studies under a flexible job shop environment, where parts have alternative routings. The study results show that the proposed scheduling approach significantly outperforms other dispatching heuristics, including cost over time (COVERT), apparent tardiness cost (ATC), and bottleneck dynamics (BD), on due-date related performance measures. It is also found that the performance difference between the proposed scheduling approach and other heuristics tend to become more significant when the number of machines is increased. The more operation steps a system has, the better the proposed method performs, relative to the other heuristics.     

基于改进NSGA2算法的多目标柔性作业车间调度

柔性作业车间调度问题（FJSP）是经典作业车间调度问题的重要扩展,其中每个操作可以在多台机器上处理,反之亦然。结合实际生产过程中加工时间、机器负载、运行成本等情况,建立了多目标调度模型。针对NSGA2算法收敛性不足的缺陷,引入免疫平衡原理改进NSGA2算法的选择策略和精英保留策略,成功避免了局部收敛问题,提高了算法的优化性能。通过与启发式规则以及多种智能算法进行比对仿真实验,改进的NASA2算法能获得更好的解。用改进的NAGA2算法求解实例,不仅有效地克服多目标间数量级和量纲的障碍,而且得到了满意的pareto解集,进一步验证了该算法和模型的可行性。     

A GRASP algorithm for flexible job-shop scheduling problem with limited resource constraints

A greedy randomised adaptive search procedure (GRASP) is an iterative multi-start metaheuristic for difficult combinatorial optimisation. The GRASP iteration consists of two phases: a construction phase, in which a feasible solution is found and a local search phase, in which a local optimum in the neighbourhood of the constructed solution is sought. In this paper, a GRASP algorithm is presented to solve the flexible job-shop scheduling problem (FJSSP) with limited resource constraints. The main constraint of this scheduling problem is that each operation of a job must follow an appointed process order and each operation must be processed on an appointed machine. These constraints are used to balance between the resource limitation and machine flexibility. The model objectives are the minimisation of makespan, maximum workload and total workload. Representative benchmark problems are solved in order to test the effectiveness and efficiency of the GRASP algorithm. The computational result shows that the proposed algorithm produced better results than other authors’ algorithms.     

Combined scheduling algorithm for re-entrant batch-processing machines in semiconductor wafer manufacturing

In this paper, a new combined scheduling algorithm is proposed to address the problem of minimising total weighted tardiness on re-entrant batch-processing machines (RBPMs) with incompatible job families in the semiconductor wafer fabrication system (SWFS). The general combined scheduling algorithm forms batches according to parameters from the real-time scheduling simulation platform (ReS²), and then sequences batches through slack-based mixed integer linear programming model (S-MILP), which is defined as batch-oriented combined scheduling algorithm. The new combined scheduling algorithm obtains families’ parameters from ReS² and then sequences these families through modified S-MILP, which is defined as family-oriented combined scheduling algorithm. With rolling horizon control strategy, two combined scheduling algorithms can update RBPMs scheduling continually. The experiments are implemented on ReS² of SWFS and ILOG CPLEX, respectively. The results demonstrate the effectiveness of our proposed methods.     

Control of manufacturing networks which contain a batch processing machine

We consider the control of a batch processing machine which is part of a larger manufacturing network of machines. Systems consisting of a batch processing machine and one or more unit-capacity machines in tandem are considered. The objective is to minimize the average time that jobs spend in the entire system. We present algorithms to determine the optimal policies for certain finite horizon, deterministic problems. We then discuss the structure of the optimal policies for infinite horizon, stochastic problems, and investigate the benefit of utilizing information about upstream and downstream unit-capacity machines in the control of the batch machine. We develop a simple heuristic scheduling policy to control the batch machine which takes into account the state of other machines in the network. Computational results demonstrate the effectiveness of our heuristic over a wide range of problem instances.     

A re-entrant hybrid flow shop scheduling problem with machine eligibility constraints

A production scheduling problem originating from a real rotor workshop is addressed in the paper. Given its specific characteristics, the problem is formulated as a re-entrant hybrid flow shop scheduling problem with machine eligibility constraints. A mixed integer linear programming model of the problem is provided and solved by the Cplex solver. In order to solve larger sized problems, a discrete differential evolution (DDE) algorithm with a modified crossover operator is proposed. More importantly, a new decoder addressing the machine eligibility constraints is developed and embedded to the algorithm. To validate the performance of the proposed DDE algorithm, various test problems are examined. The efficiency of the proposed algorithm is compared with two other algorithms modified from the existing ones in the literatures. A one-way ANOVA analysis and a sensitivity analysis are applied to intensify the superiority of the new decoder. Tightness of due dates and different levels of scarcity of machines subject to machine eligibility restrictions are discussed in the sensitivity analysis. The results indicate the pre-eminence of the new decoder and the proposed DDE algorithm.     

Parallel-machine scheduling with controllable processing times and rate-modifying activities to minimise total cost involving total completion time and job compressions

In this paper, we consider unrelated parallel-machine scheduling involving controllable processing times and rate-modifying activities simultaneously. We assume that the actual processing time of a job can be compressed by allocating a greater amount of a common resource to process the job. We further assume that each machine may require a rate-modifying activity during the scheduling horizon. The objective is to determine the optimal job compressions, the optimal positions of the rate-modifying activities and the optimal schedule to minimise a total cost function that depends on the total completion time and total job compressions. If the number of machines is a given constant, we propose an efficient polynomial time algorithm to solve the problem.     

Minimising the makespan in the two-machine job shop problem under availability constraints

Classical scheduling problem assumes that machines are available during the scheduling horizon. This assumption may be justified in some situations but it does not apply if maintenance requirements, machine breakdowns or other availability constraints have to be considered. In this paper, we treat a two-machine job shop scheduling problem with one availability constraint on each machine to minimise the maximum completion time (makespan). The unavailability periods are known in advance and the processing of an operation cannot be interrupted by an unavailability period (non-preemptive case). We present in our approach properties dealing with permutation dominance and the optimality of Jackson's rule under availability constraints. In order to evaluate the effectiveness of the proposed approach, we develop two mixed integer linear programming models and two schemes for a branch and bound method to solve the tackled problem. Computational results validate the proposed approach and prove the efficiency of the developed methods.     

A novel imperialist competitive algorithm for bi-criteria scheduling of the assembly flowshop problem

This paper deals with the two-stage assembly flowshop scheduling problem with minimisation of weighted sum of makespan and mean completion time as the objective. The problem is NP-hard, hence we proposed a meta-heuristic named imperialist competitive algorithm (ICA) to solve it. Since appropriate design of the parameters has a significant impact on the algorithm efficiency, we calibrate the parameters of this algorithm using the Taguchi method. In comparison with the best algorithm proposed previously, the ICA indicates an improvement. The results have been confirmed statistically.     

An improved co-evolutionary algorithm for green manufacturing by integration of recovery option selection and disassembly planning for end-of-life products

There is a strong need for recovery decision-making for end-of-life (EOL) products to satisfy sustainable manufacturing requirements. This paper develops and tests a profit maximisation model by simultaneously integrating recovery option selection and disassembly planning. The proposed model considers the quality of EOL components. This paper utilises an integrated method of multi-target reverse recursion and partial topological sorting to generate a feasible EOL solution that also reduces the complexity of genetic constraints handling. In order to determine recovery options, disassembly level and disassembly sequence simultaneously, this paper develops an improved co-evolutionary algorithm (ICA) to search for an optimal EOL solution. The proposed algorithm adopts the evolutionary mechanism of localised interaction and endosymbiotic competition. Further, an advanced local search operator is introduced to improve convergence performance, and a global disturbance strategy is also suggested to prevent premature convergence. Finally, this paper conducts a series of computational experiments under various scenarios to validate the meta-heuristic integrated decision-making model proposed and the superiority of the developed ICA. The results show that the proposed approach offers a strong and flexible decision support tool for intelligent recovery management in a ubiquitous information environment. We discuss the theoretical and practical contributions of this paper and implications for future research.     

A memetic algorithm for multi-objective flexible job-shop problem with worker flexibility

In existing scheduling models, the flexible job-shop scheduling problem mainly considers machine flexibility. However, human factor is also an important element existing in real production that is often neglected theoretically. In this paper, we originally probe into a multi-objective flexible job-shop scheduling problem with worker flexibility (MO-FJSPW). A non-linear integer programming model is presented for the problem. Correspondingly, a memetic algorithm (MA) is designed to solve the proposed MO-FJSPW whose objective is to minimise the maximum completion time, the maximum workload of machines and the total workload of all machines. A well-designed chromosome encoding/decoding method is proposed and the adaptive genetic operators are selected by experimental studies. An elimination process is executed to eliminate the repeated individuals in population. Moreover, a local search is incorporated into the non-dominated sorting genetic algorithm II. In experimental phase, the crossover operator and elimination operator in MA are examined firstly. Afterwards, some extensive comparisons are carried out between MA and some other multi-objective algorithms. The simulation results show that the MA performs better for the proposed MO-FJSPW than other algorithms.     

Robust scheduling of a two-stage hybrid flow shop with uncertain interval processing times

This paper studies the makespan minimisation scheduling problem in a two-stage hybrid flow shop. The first stage has one machine and the second stage has m identical parallel machines. Neither the processing time nor probability distribution of the processing time of each job is uncertain. We propose a robust (min–max regret) scheduling model. To solve the robust scheduling problem, which is NP-hard, we first derive some properties of the worst-case scenario for a given schedule. We then propose both exact and heuristic algorithms to solve this problem. In addition, computational experiments are conducted to evaluate the performance of the proposed algorithms.     

A bi-objective parallel machine problem with eligibility,release dates and delivery times of the jobs

The scheduling of parallel machines is a well-known problem in many companies. Nevertheless, not always all the jobs can be manufactured in any machine and the eligibility appears. Based on a real-life problem, we present a model which has m parallel machines with different level of quality from the highest level for the first machine till the lowest level for the last machine. The set of jobs to be scheduled on these m parallel machines are also distributed among these m levels: one job from a level can be manufactured in a machine of the same or higher level but a penalty, depending on the level, appears when a job is manufactured in a machine different from the highest level i.e. different from the first machine. Besides, there are release dates and delivery times associated to each job. The tackled problem is bi-objective with the criteria: minimisation of the final date – i.e. the maximum for all the jobs of their completion time plus the delivery time – and the minimisation of the total penalty generated by the jobs. In a first step, we analyse the sub-problem of minimisation of the final date on a single machine for jobs with release dates and delivery times. Four heuristics and an improvement algorithm are proposed and compared on didactic examples and on a large set of instances. In a second step an algorithm is proposed to approximate the set of efficient solutions and the Pareto front of the bi-objective problem. This algorithm contains two phases: the first is a depth search phase and the second is a backtracking phase. The procedure is illustrated in detail on an instance with 20 jobs and 3 machines. Then extensive numerical experiments are realised on two different sets of instances, with 20, 30 and 50 jobs, 3 or 4 machines and various values of penalties. Except for the case of 50 jobs, the results are compared with the exact Pareto front.     

Adaptive scheduling in random flexible manufacturing systems subject to machine breakdowns

In a FMS dynamic scheduling environment, frequent rescheduling to react to disruptions such as machine breakdowns can make the behaviour of the system hard to predict, and hence reduce the effectiveness of dynamic scheduling. Another approach to handle the disruptions is to update the job ready time and completion time, and machine status on a rolling horizon basis, and consider the machine availability explicitly in generating schedules. When machine downtime has a small variation, the operation completion time is estimated by using limiting (steady-state) machine availability. However, steady-state analysis is sometimes unlikely to provide a complete picture of the system when there is a large variation in machine downtime and repair time, and frequent disruptions (e.g. tool failures) exist. Transient analysis of machine availability will be more meaningful in such a situation during a finite observation period. In this paper, an adaptive scheduling approach is proposed to make coupled decisions about part/machine scheduling and operation/tool assignments on a rolling horizon basis, while the operation completion time is estimated by a transient machine availability analysis based on a two-state continuous time Markov process. The expected tool waiting time is explicitly considered in the job machine scheduling decision. The effectiveness of the proposed method is compared with other approaches based on various dispatching heuristics such as Apparent Tardiness Cost, Cost OVER Time, and Bottleneck Dynamics, etc under different shop load and machine downtime levels.     

A genetic algorithm for the multi-stage and parallel-machine scheduling problem with job splitting – A case study for the solar cell industry

This paper studies a multi-stage and parallel-machine scheduling problem with job splitting which is similar to the traditional hybrid flow shop scheduling (HFS) in the solar cell industry. The HFS has one common hypothesis, one job on one machine, among the research. Under the hypothesis, one order cannot be executed by numerous machines simultaneously. Therefore, multiprocessor task scheduling has been advocated by scholars. The machine allocation of each order should be scheduled in advance and then the optimal multiprocessor task scheduling in each stage is determined. However, machine allocation and production sequence decisions are highly interactive. As a result, this study, motivated from the solar cell industry, is going to explore these issues. The multi-stage and parallel-machine scheduling problem with job splitting simultaneously determines the optimal production sequence, multiprocessor task scheduling and machine configurations through dynamically splitting a job into several sublots to be processed on multiple machines. We formulate this problem as a mixed integer linear programming model considering practical characteristics and constraints. A hybrid-coded genetic algorithm is developed to find a near-optimal solution. A preliminary computational study indicates that the developed algorithm not only provides good quality solutions but outperforms the classic branch and bound method and the current heuristic in practice.     

A STATIONARY CYCLICAL PRODUCTION SCHEDULING PROBLEM UNDER A NONADDITIVE OUTPUT FUNCTION

The purpose of this paper is to formulate and solve a nonlinear mixed zero-one integer programming problem aimed to maximize total output by scheduling the operational time of N non-identical machines. Properties of the optimal solution are identified under restrictions imposed on machine availability and various budget constraints. A branch and bound algorithm to solve the problem is suggested.     

A Meta-RaPS for the early/tardy single machine scheduling problem

This paper investigates a meta-heuristic solution approach to the early/tardy single machine scheduling problem with common due date and sequence-dependent setup times. The objective of this problem is to minimise the total amount of earliness and tardiness of jobs that are assigned to a single machine. The popularity of just-in-time (JIT) and lean manufacturing scheduling approaches makes the minimisation of earliness and tardiness important and relevant. In this research the early/tardy problem is solved by Meta-RaPS (meta-heuristic for randomised priority search). Meta-RaPS is an iterative meta-heuristic which is a generic, high level strategy used to modify greedy algorithms based on the insertion of a random element. In this case a greedy heuristic, the shortest adjusted processing time, is modified by Meta-RaPS and the good solutions are improved by a local search algorithm. A comparison with the existing ETP solution procedures using well-known test problems shows Meta-RaPS produces better solutions in terms of percent difference from optimal. The results provide high quality solutions in reasonable computation time, demonstrating the effectiveness of the simple and practical framework of Meta-RaPS.     

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.