Mathematical modelling and a meta-heuristic for flexible job shop scheduling

This study develops new solution methodologies for the flexible job shop scheduling problem (F-JSSP). As a first step towards dealing with this complex problem, mathematical modellings have been used; two novel effective position- and sequence-based mixed integer linear programming (MILP) models have been developed to fully characterise operations of the shop floor. The developed MILP models are capable of solving both partially and totally F-JSSPs. Size complexities, solution effectiveness and computational efficiencies of the developed MILPs are numerically explored and comprehensively compared vis-à-vis the makespan optimisation criterion. The acquired results demonstrate that the proposed MILPs, by virtue of its structural efficiencies, outperform the state-of-the-art MILPs in literature. The F-JSSP is strongly NP-hard; hence, it renders even the developed enhanced MILPs inefficient in generating schedules with the desired quality for industrial scale problems. Thus, a meta-heuristic that is a hybrid of Artificial Immune and Simulated Annealing (AISA) Algorithms has been proposed and developed for larger instances of the F-JSSP. Optimality gap is measured through comparison of AISA’s suboptimal solutions with its MILP exact optimal counterparts obtained for small- to medium-size benchmarks of F-JSSP. The AISA’s results were examined further by comparing them with seven of the best-performing meta-heuristics applied to the same benchmark. The performed comparative analysis demonstrated the superiority of the developed AISA algorithm. An industrial problem in a mould- and die-making shop was used for verification.     

Minimising makespan on parallel batch processing machines with non-identical ready time and arbitrary job sizes

This paper considers the parallel batch processing machine scheduling problem which involves the constraints of unequal ready times, non-identical job sizes, and batch dependent processing times in order to sequence batches on identical parallel batch processing machines with capacity restrictions. This scheduling problem is a practical generalisation of the classical parallel batch processing machine scheduling problem, which has many real-world applications, particularly, in the aging test operation of the module assembly stage in the manufacture of thin film transistor liquid crystal displays (TFT-LCD). The objective of this paper is to seek a schedule with a minimum total completion time for the parallel batch processing machine scheduling problem. A mixed integer linear programming (MILP) model is proposed to optimise the scheduling problem. In addition, to solve the MILP model more efficiently, an effective compound algorithm is proposed to determine the number of batches and to apply this number as one parameter in the MILP model in order to reduce the complexity of the problem. Finally, three efficient heuristic algorithms for solving the large-scale parallel batch processing machine scheduling problem are also provided.     

Mathematical modelling and optimisation of energy-conscious hybrid flow shop scheduling problem with unrelated parallel machines

This paper investigates an energy-conscious hybrid flow shop scheduling problem with unrelated parallel machines (HFSP-UPM) with the energy-saving strategy of turning off and on. We first analyse the energy consumption of HFSP-UPM and formulate five mixed integer linear programming (MILP) models based on two different modelling ideas namely idle time and idle energy. All the models are compared both in size and computational complexities. The results show that MILP models based on different modelling ideas vary dramatically in both size and computational complexities. HFSP-UPM is NP-Hard, thus, an improved genetic algorithm (IGA) is proposed. Specifically, a new energy-conscious decoding method is designed in IGA. To evaluate the proposed IGA, comparative experiments of different-sized instances are conducted. The results demonstrate that the IGA is more effective than the genetic algorithm (GA), simulating annealing algorithm (SA) and migrating birds optimisation algorithm (MBO). Compared with the best MILP model, the IGA can get the solution that is close to an optimal solution with the gap of no more than 2.17% for small-scale instances. For large-scale instances, the IGA can get a better solution than the best MILP model within no more than 10% of the running time of the best MILP model.     

Leading the lean enterprise transformation,by G. Koenigsaecker

This paper first formulates a binary integer programming (BIP) model that minimises C _max for a multi-stage flexible job shop floor with machine compatibility. Due to a computational limitation, the exact optimal model is then relaxed as a linear programming model. The output from the relaxation model then turns into the objective of the BIP-based real-time scheduling (RTS) heuristic model. The RTS heuristic requires an iteration to calculate the final C _max. At each iteration, the RTS heuristic assigns just one job to the earliest available machines. Since the set of jobs and machines included in the RTS model is relatively small, RTS can be solved in a very short computational time. We evaluate an overall effectiveness (in terms of solution quality and run time) of the RTS heuristic by way of computer experiments.     

Genetic algorithms for job shop scheduling problems with alternative routings

The purpose of this research is to solve a general job shop problem with alternative machine routings. We consider four performance measures: mean flow time, makespan, maximum lateness, and total absolute deviation from the due dates. We first develop mixed-integer linear programming (MILP) formulations for the problems. The MILP formulations can be used either to compute optimal solutions for small-sized problems or to test the performance of existing heuristic algorithms. In addition, we have developed a genetic algorithm that can be used to generate relatively good solutions quickly. Further, computational experiments have been performed to compare the solution of the MILP formulations with that of existing algorithms.     

Two-machine flow shop problem with unit-time operations and conflict graph

This paper addresses the problem of scheduling, on a two-machine flow shop, a set of unit-time operations subject to the constraints that some conflicting jobs cannot be scheduled simultaneously on different machines. In the context of our study, these conflicts are modelled by general graphs. The problem of minimising the maximum completion time (makespan) is known to be NP-hard in the strong sense. We propose a mixed-integer linear programming (MILP) model. Then, we develop a branch and bound algorithm based on new lower and upper bound procedures. We further provide a computer simulation to measure the performance of the proposed approaches. The computational results show that the branch and bound algorithm outperforms the MILP model and can solve instances of size up to 20,000 jobs.     

求解带AGV柔性作业车间调度问题的改进灰狼算法

针对带AGV的柔性作业车间调度问题,以最小化完工时间为目标,考虑AGV在装载站、机器、卸载站之间的有效负载时间和空载时间,构建了数学规划模型。其次,提出一种有效的灰狼算法进行求解,基于该问题特征,设计机器选择、工序排序和AGV搬运的3段编码,有效地保证每个个体均可产生可行解;灰狼算法中改进了关键参数a和E设定方式,有效平衡了算法的勘探能力和局部搜索能力;为进一步提升算法跳出局部最优解的能力,该算法融合了领域搜索等方法。最后,案例测试结果表明,改进灰狼算法在求解带AGV柔性作业车间调度问题中具有优越的性能。     

A tabu search algorithm for simultaneous machine/AGV scheduling problem

Machines and automated guided vehicles (AGVs) scheduling problems are two essential issues that need to be addressed for the efficiency of the overall production system. The purpose of this paper is to study the simultaneous scheduling problem of machines and AGVs in a flexible manufacturing system (FMS) since the global optimum cannot be reached by considering each of them individually. In this paper, a mixed integer linear programming (MILP) model is developed with the objective of makespan minimisation. The MILP model consists of the following two constraint sets: machines and AGVs scheduling sub-problems. As both sub-problems are known to be NP-hard, a heuristic algorithm based on tabu search (TS) is proposed to get optimal or near to optimal solution for large-size problems within reasonable computation time. The proposed algorithm includes a novel two-dimensional solution representation and the generation of two neighbour solutions, which are alternately and iteratively applied to improve solutions. Moreover, an improved lower bound calculation method is introduced for the large-size problems. Computational results show the superior performance of the TS algorithm for the simultaneous scheduling problem.     

A mixed integer goal programming model for discrete values of design requirements in QFD

A main feature of quality function deployment (QFD) planning process is to determine target values for the design requirements (DRs) of a product, with a view to achieving a higher level of overall customer satisfaction. However, in real world applications, values of DRs are often discrete instead of continuous. Therefore, a mixed integer linear programming (MILP) model considering discrete data is suggested. As opposed to the existing literature, the fulfilment levels of DRs are assumed to have a piece-wise linear relationship with cost; because, constraints of technology and resource rarely provides a linear relationship in manufacturing systems. In the proposed MILP model, we considered customer satisfaction as the only goal. But, QFD process may be necessary to optimise cost and technical difficulty goals as well as customer satisfaction. Therefore, by developing the MILP model with multi-objective decision making (MODM) approach, a novel mixed integer goal programming (MIGP) model is proposed to optimise these goals simultaneously. Finally, MILP model solution turns out to be a more realistic approach to real applications because piece-wise linear relationship is taken into account. The solution of MIGP model provided different alternative results to decision makers according to usage of the lexicographic goal programming (LGP) approach. The applicability of the proposed models in practice is demonstrated with a washing machine development problem.     

LP-based heuristics for scheduling chemical batch processes

A mixed-integer linear programming (MILP) model for scheduling chemical batch processes is presented. Since computational times are prohibitive for most problems of realistic size, a two-stage solution procedure is suggested. In the first stage, an initial solution is derived by use of a LP-based heuristic. The proposed heuristic defines a time grid that includes only a limited number of feasible periods in which a processing task is allowed to start. Thus, the size of the original multi-period MILP model is reduced in a controlled manner and optimal solutions to the relaxed model are obtained within reasonable computational time. The second stage consists of an improvement step that aims to compress the initial schedule by left-shifting operations over the time-axis. In order to evaluate the applicability of the heuristics a number of numerical experiments were performed. It is shown that near-optimal solutions are obtained for largesize problems with only modest computational effort.     

Scheduling manufacturing systems with blocking: a Petri net approach

This paper introduces a Petri net-based approach for scheduling manufacturing systems with blocking. The modelling of the job routings and the resource and blocking constraints is carried out with the Petri net formalism due to their capability of representing dynamic, concurrent discrete-event dynamic systems. In addition Petri nets can detect deadlocks typically found in systems with blocking constraints. The scheduling task is performed with an algorithm that combines the classical A* search with an aggressive node-pruning strategy. Tests were conducted on a variety of manufacturing systems that included classical job shop, flexible job shop and flexible manufacturing scheduling problems. The optimisation criterion was makespan. The experiments show that the algorithm performed well in all types of problems both in terms of solution quality and computing times.     

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 hybrid differential evolution algorithm for a two-stage flow shop on batch processing machines with arbitrary release times and blocking

Batch processing machines (BPMs) have important applications in a variety of industrial systems. This paper considers the problem of scheduling two BPMs in a flow shop with arbitrary release times and blocking such that the makespan is minimised. The problem is formulated as a mixed integer programming model. Subsequently, a hybrid discrete differential evolution (HDDE) algorithm is proposed. In the algorithm, individuals in the population are first represented as discrete job sequences, and mutation and crossover operators are applied based on the representation. Second, after using the first-fit rule to form batches, a novel least idle/blocking time heuristic is developed to schedule the batches in the flow shop. Furthermore, an effective local search technique is embedded in the algorithm to enhance the exploitation ability. The performance of the proposed algorithm is evaluated by comparing its results to a commercial solver (CPLEX), a genetic algorithm and a simulated annealing algorithm. Computational experiments demonstrate the superiority of the HDDE algorithm in terms of solution quality, robustness and run time.     

Workshop scheduling using practical (inaccurate) data Part 3: A framework to integrate job releasing,routing and scheduling functions to create a robust predictive schedule

A comprehensive simulation study conducted by the authors investigated the robustness of a predictive scheduling system in a dynamic and stochastic environment. The results revealed that to improve the robustness of a scheduling system, besides using a robust scheduling method with a frequent rescheduling policy, the shop load should be well controlled and kept balanced. Integrating the planning and the scheduling functions has been shown to achieve this objective. This paper discusses the effects of the planning i.e. job releasing and routing and the scheduling functions in creating a robust schedule and a framework to integrate the above functions is proposed. This system consists of a planning module that is concerned with job releasing and routing decisions and a scheduling module that provides the detailed scheduling. A mathematical model using the integer programming technique is use to demonstrate a solution for the planning module. In addition, a heuristic algorithm is used to solve the scheduling problem. It is shown that, in terms of shop load balance level and job delivery time, the proposed system performs better than a benchmark loading strategy on the basis of minimum processing cost.     

Hedge against total flow time uncertainty of the uniform parallel machine scheduling problem with interval data

We consider a total flow time minimisation problem of uniform parallel machine scheduling when job processing times are only known to be bounded within certain given intervals. A minmax regret model is proposed to identify a robust schedule that minimises the maximum deviation from the optimal total flow time over all possible realisations of the job processing times. To solve this problem, we first prove that the maximal regret for any schedule can be obtained in polynomial time. Then, we derive a mixed-integer linear programming (MILP) formulation of our problem by exploiting its structural properties. To reduce the computational time, we further transform our problem into a robust single-machine scheduling problem and derive another MILP formulation with fewer variables and constraints. Moreover, we prove that the optimal schedule under the midpoint scenario is a 2-approximation for our minmax regret problem. Finally, computational experiments are conducted to evaluate the performance of the proposed methods.     

More MILP models for hybrid flow shop scheduling problem and its extended problems

With the rapid development of computer technology and related softwares for mathematical models, mathematical modelling of scheduling problems is receiving growing attention from researchers. In this work, the hybrid flow shop scheduling problem with unrelated parallel machines (HFSP-UPM) with the objective aimed to minimise the makespan is studied. According to the characteristics of the HFSP-UPM, eight mixed integer linear programming (MILP) models are formulated in order to obtain optimal solutions based on different modelling ideas. Then, these models are extended to solve HFSP-UPM with sequence-dependent setup times (HFSP-UPM-SDST), no-wait HFSP-UPM (HFSP-UPM-NW) and HFSP-UPM with blocking (HFSP-UPM-B). All the proposed models and the existing model are detailedly compared and evaluated under three aspects namely modelling process, size complexity and computational complexity. Numerical experiments show that MILP models dependent on diverse modelling ideas perform very differently. The model developed based on stage precedence is the best one and should be given preference in future applications. In addition, the proposed models of HFSP-UPM-NW and HFSP-UPM-B improve several best known solutions for the test instances in the existing literature.     

A discrete time reactive scheduling model for new order insertion in job shop,make-to-order industries

This research presents a new reactive scheduling methodology for job shop, make-to-order industries. An integer linear programming formulation previously developed by the authors to schedule these types of industries is extended to address the problem of inserting new orders in a predetermined schedule, which is important in order-driven industries. A reactive scheduling algorithm is introduced to iteratively update the schedules. Numerical results on realistic examples of job shops of different sizes illustrate the effectiveness of the approach. In each case, different alternatives for inserting a set of new orders in an initial schedule are optimally generated, enabling the user to choose the most convenient one. Solutions are characterised by measures of scheduling efficiency as well as stability measures that assess the impact of rescheduling operations in a previously defined scheduling solution.     

Scheduling algorithms to minimise the total family flow time for job shops with job families

This paper considers the job scheduling problem in which jobs are grouped into job families, but they are processed individually. The decision variable is the sequence of the jobs assigned to each machine. This type of job shop scheduling can be found in various production systems, especially in remanufacturing systems with disassembly, reprocessing and reassembly shops. In other words, the reprocessing shop can be regarded as the job shop with job families since it performs the operations required to bring parts or sub-assemblies disassembled back to like-new condition before reassembling them. To minimise the deviations of the job completion times within each job family, we consider the objective of minimising the total family flow time. Here, the family flow time implies the maximum among the completion times of the jobs within a job family. To describe the problem clearly, a mixed integer programming model is suggested and then, due to the complexity of the problem, two types of heuristics are suggested. They are: (a) priority rule based heuristics; and (b) meta-heuristics. Computational experiments were performed on a number of test instances and the results show that some priority rule based heuristics are better than the existing ones. Also, the meta-heuristics improve the priority rule based heuristics significantly.     

Scheduling commercial advertisements for television

The problem of scheduling the commercial advertisements in the television industry is investigated. Each advertiser client demands that the multiple airings of the same brand advertisement should be as spaced as possible over a given time period. Moreover, audience rating requests have to be taken into account in the scheduling. This is the first time this hard decision problem is dealt with in the literature. We design two mixed integer linear programming (MILP) models. Two constructive heuristics, local search procedures and simulated annealing (SA) approaches are also proposed. Extensive computational experiments, using several instances of various sizes, are performed. The results show that the proposed MILP model which represents the problem as a network flow obtains a larger number of optimal solutions and the best non-exact procedure is one that uses SA.     

Scheduling flexible manufacturing cells using Tabu Search

Scheduling is an important aspect in the overall control of a flexible manufacturing system. The research presented focuses on production scheduling of jobs within a flexible manufacturing cell (FMC)–one type of flexible manufacturing system. Due to the complexity of the FMC scheduling problem, a 0–1 mixed-integer linear programming (MILP) model is formulated for M machines and N jobs with alternative routings. Although small instances of the problem can be solved optimally with MILP models, a two-stage Tabu Search (TS² ) algorithm that minimises the manufacturing makespan (MS) is proposed to solve medium-to-large-scale problems more efficiently. During Stage I (construction phase), two heuristics are utilised to generate an initial feasible sequence and an initial MS solution. In Stage II (improvement phase), the acquired initial solutions from Stage I are combined with a Tabu Search meta-heuristic procedure that provides improved MS solutions. The TS² algorithm provides tremendous savings in computational time for medium/large-sized multi-machine FMC problems.