Learning dispatching rules using random forest in flexible job shop scheduling problems

In this paper, we address the flexible job-shop scheduling problem (FJSP) with release times for minimising the total weighted tardiness by learning dispatching rules from schedules. We propose a random-forest-based approach called Random Forest for Obtaining Rules for Scheduling (RANFORS) in order to extract dispatching rules from the best schedules. RANFORS consists of three phases: schedule generation, rule learning with data transformation, and rule improvement with discretisation. In the schedule generation phase, we present three solution approaches that are widely used to solve FJSPs. Based on the best schedules among them, the rule learning with data transformation phase converts them into training data with constructed attributes and generates a dispatching rule with inductive learning. Finally, the rule improvement with discretisation improves dispatching rules with a genetic algorithm by discretising continuous attributes and changing parameters for random forest with the aim of minimising the average total weighted tardiness. We conducted experiments to verify the performance of the proposed approach and the results showed that it outperforms the existing dispatching rules. Moreover, compared with the other decision-tree-based algorithms, the proposed algorithm is effective in terms of extracting scheduling insights from a set of rules.     

Learning effective dispatching rules for batch processor scheduling

Batch processor scheduling, where machines can process multiple jobs simultaneously, is frequently harder than its unit-capacity counterpart because an effective scheduling procedure must not only decide how to group the individual jobs into batches, but also determine the sequence in which the batches are to be processed. We extend a previously developed genetic learning approach to automatically discover effective dispatching policies for several batch scheduling environments, and show that these rules yield good system performance. Computational results show the competitiveness of the learned rules with existing rules for different performance measures. The autonomous learning approach addresses a growing practical need for rapidly developing effective dispatching rules for these environments by automating the discovery of effective job dispatching procedures.     

A lever concept integrated with simple rules for flow shop scheduling

The development of more efficient and better performing priority dispatching rules (PDRs) for production scheduling is relevant to modern flow shop scheduling practice because they are simple, easy to apply and have low computational complexity, especially for large-scale problems. While the current research trend in scheduling is towards finding superior solutions through meta-heuristics, they are computationally expensive and many meta-heuristics also use PDRs to generate starting points. In this paper, we analyse the properties of flow shop scheduling problems to minimise maximum completion time, and generate a new dominance rule that is complementary to Szwarc’s rule. These dominance rules indicate that a weighting factor should be included in sequencing to account for the possibility that a single job’s processing time can generate idle time repeatedly within a flow line. Two new PDRs with a leveraged weighting factor are proposed to minimise makespan and average completion time. Computational results on Taillard’s benchmark problems and on historical operating room data show that the proposed PDRs perform much better than established PDRs without an increase in computational complexity.     

Optimal scheduling for flexible job shop operation

This paper presents a new integer linear programming (ILP) model to schedule flexible job shop, discrete parts manufacturing industries that operate on a make-to-order basis. The model considers groups of parallel homogeneous machines, limited intermediate buffers and negligible set-up effects. Orders consist of a number of discrete units to be produced and follow one of a given number of processing routes. The model allows re-circulation to take place, an important issue in practice that has received scant treatment in the scheduling literature. Good solution times were obtained using commercial mixed-integer linear programming (MILP) software to solve realistic examples of flexible job shops to optimality. This supports the claim that recent advances in computational power and MILP solution algorithms are making this approach competitive with others traditionally applied in job shop scheduling.     

Study on constraint scheduling algorithm for job shop problems with multiple constraint machines

This paper focuses on a job-shop scheduling problem with multiple constraint machines (JSPMC). A constraint scheduling method for the JSPMC is proposed. It divides the machines in the shop into constraint and non-constraint machines based on a new identification method, and formulates a reduced problem only for constraint machines while replacing the operations of non-constraint machines with time lags. The constraint machines are scheduled explicitly by solving the reduced problem with an efficient heuristic, while the non-constraint machines are scheduled by the earliest operation due date (EODD) dispatching rule. Extensive computational results indicate that the proposed constraint scheduling algorithm can obtain a better trade-off between solution quality and computation time compared with various versions of the shifting bottleneck (SB) methods for the JSPMC.     

Extracting priority rules for dynamic multi-objective flexible job shop scheduling problems using gene expression programming

In this paper, two new approaches are proposed for extracting composite priority rules for scheduling problems. The suggested approaches use simulation and gene expression programming and are able to evolve specific priority rules for all dynamic scheduling problems in accordance with their features. The methods are based on the idea that both the proper design of the function and terminal sets and the structure of the gene expression programming approach significantly affect the results. In the first proposed approach, modified and operational features of the scheduling environment are added to the terminal set, and a multigenic system is used, whereas in the second approach, priority rules are used as automatically defined functions, which are combined with the cellular system for gene expression programming. A comparison shows that the second approach generates better results than the first; however, all of the extracted rules yield better results than the rules from the literature, especially for the defined multi-objective function consisting of makespan, mean lateness and mean flow time. The presented methods and the generated priority rules are robust and can be applied to all real and large-scale dynamic scheduling problems.     

Dynamic job shop scheduling for missed due date performance

In this research, missed due date in terms of mean absolute lateness (MAL) and mean square lateness (MSL) has been considered as a performance criterion and a scheduling study has been performed to improve the missed due date performance in dynamic, stochastic, multi machine job shop environments. In the study, a new due date assignment model was proposed and a new dynamic dispatching rule was developed. The results indicate that the proposed due date assignment model is very successful for improving the missed due date performance and the developed dispatching rule is also very successful for meeting the assigned due dates.     

Integrated approach to part scheduling and inspection policies for a job shop manufacturing system

The quality of a product greatly depends on the quality of its components. This requires that manufacturing specifications have to be met in the manufacturing environment and as a consequence inspection stations are present in many manufacturing systems and inspection policies must be adopted. One problem, which has been widely investigated, concerns the detection of the inspection points in the hypothesis that the action to be taken is known when a defective part is detected. If different jobs are to be produced, then operation scheduling becomes yet another complex problem needing to be solved. And while the problem of scheduling has received a great amount of attention from researchers, to our knowledge the interaction between the two problems has not been treated in job-shop environment. In the present paper three different control policies are preliminarily examined: they differ both in terms of the number of operations that are inspected, and with regard to the type of intervention carried out on detection of a defect. Each control policy affects the optimal inspection locations, which, in their turn, influence operation scheduling. As will be shown in the present paper, a sequential decision process based on separate optimization steps can lead to very poor final results. For this reason, an integrated approach is proposed, in an attempt to identify an optimal solution using a genetic algorithm.     

A simulation study of new multi-objective composite dispatching rules,CONWIP, and push lot release in semiconductor fabrication

This paper evaluates dispatching rules and order release policies in two wafer fabrication facilities (thereafter referred to as ‘fab’) representing ASIC (application specific integrated circuit) and low-mix high-volume production. Order release policies were fixed-interval (push) release, and constant work-in-process (CONWIP) (pull) policy. Following rigorous fab modelling and statistical analysis, new composite dispatching rules were found to be robust for average and variance of flow time, as well as due-date adherence measures, in both production modes.     

An optimization-based algorithm for job shop scheduling

Scheduling is a key factor for manufacturing productivity. Effective scheduling can improve on-time delivery, reduce inventory, cut lead times, and improve the utilization of bottleneck resources. Because of the combinatorial nature of scheduling problems, it is often difficult to find optimal schedules, especially within a limited amount of computation time. Production schedules therefore are usually generated by using heuristics in practice. However, it is very difficult to evaluate the quality of these schedules, and the consistency of performance may also be an issue. In this paper, near-optimal solution methodologies for job shop scheduling are examined. The problem is formulated as integer optimization with a “separable” structure. The requirement of on-time delivery and low work-in-process inventory is modelled as a goal to minimize a weighted part tardiness and earliness penalty function. Lagrangian relaxation is used to decompose the problem into individual part subproblems with intuitive appeal. By iteratively solving these subproblems and updating the Lagrangian multipliers at the high level, near-optimal schedules are obtained with a lower bound provided as a byproduct. This paper reviews a few selected methods for solving subproblems and for updating multipliers. Based on the insights obtained, a new algorithm is presented that combines backward dynamic programming for solving low level subproblems and interleaved conjugate gradient method for solving the high level problem. The new method significantly improves algorithm convergence and solution quality. Numerical testing shows that the method is practical for job shop scheduling in industries. This work was supported in part by the National Science Foundation under DMI-9500037, and the Advanced Technology Center for Precision Manufacturing, University of Connecticut.     

Total tardiness minimization in permutation flow shops: a simple approach based on a variable greedy algorithm

This paper addresses the problem of scheduling jobs in a permutation flowshop with the objective of minimizing the total tardiness of jobs. To tackle this problem, it is suggested that a procedure based on a greedy algorithm is employed that successively iterates over an increasing number of candidate solutions. The computational experiments carried out show this algorithm outperforms the best existing one for the problem under consideration. In addition, out some tests are carried out to analyse the efficiency of the adopted design.     

Performance of an ant colony optimisation algorithm in dynamic job shop scheduling problems

The goal of the current study is to identify appropriate application domains of Ant Colony Optimisation (ACO) in the area of dynamic job shop scheduling problem. The algorithm is tested in a shop floor scenario with three levels of machine utilisations, three different processing time distributions, and three different performance measures for intermediate scheduling problems. The steady-state performances of ACO in terms of mean flow time, mean tardiness, total throughput on different experimental environments are compared with those from dispatching rules including first-in-first-out, shortest processing time, and minimum slack time. Two series of experiments are carried out to identify the best ACO strategy and the best performing dispatching rule. Those two approaches are thereafter compared with different variations of processing times. The experimental results show that ACO outperforms other approaches when the machine utilisation or the variation of processing times is not high.     

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.     

Look ahead job demanding for improving job shop performance

In this paper a new coordination approach for decentralized job shop scheduling rules is presented and analyzed in a simulation study. The coordination is based on look ahead information and contains a mechanism for demanding and supplying jobs. The simulation experiments show that the performance of conventional scheduling rules is significantly improved using the coordination mechanism.     

A new paradigm for rule-based scheduling in the wafer probe centre

This paper addresses the scheduling problem in the wafer probe centre. The proposed approach is based on the dispatching rule, which is popularly used in the semiconductor manufacturing industry. Instead of designing new rules, this paper proposes a new paradigm to utilize these rules. The proposed paradigm formulates the dispatching process as a 2-D assignment problem with the consideration of information from multiple lots and multiple pieces of equipment in an integrated manner. Then, the dispatching decisions are made by maximizing the gains of multiple possible decisions simultaneously. Besides, we develop a genetic algorithm (GA) for generating good dispatching rules through combining multiple rules with linear weighted summation. The benefits of the proposed paradigm and GA are verified with a comprehensive simulation study on three due-date-based performance measures. The experimental results show that under the proposed paradigm, the dispatching rules and GA can perform much better than under the traditional paradigm.     

New dispatching rules for shop scheduling: A step forward

This paper provides a set of new dispatching rules for the minimization of various performance measures such as mean, maximum and variance of flow time and tardiness in dynamic shops. A static rule which minimizes the number of tardy jobs is also proposed. To evaluate these proposed rules, their relative performance is analysed in open job shops and reported in comparison with the standard benchmark rules such as the SPT (shortest process time) and EDD (earliest due-date), popular rules like ATC (apparent tardiness cost) and MOD (modified operational due-date), and the best performing rules in current literature such as RR, PT + WINQ, PT + WINQ + SL and AT-RPT. Thereafter, a comparative analysis of the relative performance of these rules is carried out in job shops (with no machine revisitation of jobs) and flow shops (with missing operations on jobs) in dynamic environments. Based on the simulation study and analysis of results in different manufacturing environments viz. job shops and flow shops, observations and conclusions are made, highlighting some interesting aspects about the effect of routeing on the individual performance of rules.     

A shuffled frog-leaping algorithm for job shop scheduling with outsourcing options

In this paper, job shop scheduling problem with outsourcing options is considered and a novel shuffled frog-leaping algorithm (SFLA) is presented to minimise total tardiness under condition that total outsourcing cost does not exceed a given upper bound. In SFLA, a tournament selection-based method is used to decompose the whole population into some memeplexes, the search process in each memeplex is done on the best solution of the memeplex and composed of the global search step and the multiple neighbourhood search step. SFLA is tested on a number of instances and compared with some methods from the literature. Computational results validate the promising performance of SFLA on the considered problem.     

Multi-objective genetic algorithm for energy-efficient job shop scheduling

The paper investigates the effects of production scheduling policies aimed towards improving productive and environmental performances in a job shop system. A green genetic algorithm allows the assessment of multi-objective problems related to sustainability. Two main considerations have emerged from the application of the algorithm. First, the algorithm is able to achieve a semi-optimal makespan similar to that obtained by the best of other methods but with a significantly lower total energy consumption. Second, the study demonstrated that the worthless energy consumption can be reduced significantly by employing complex energy-efficient machine behaviour policies.     

Outsourcing and scheduling for a two-machine flow shop with release times

This article addresses a two-machine flow shop scheduling problem where jobs are released intermittently and outsourcing is allowed. The first operations of outsourced jobs are processed by the first subcontractor, they are transported in batches to the second subcontractor for processing their second operations, and finally they are transported back to the manufacturer. The objective is to select a subset of jobs to be outsourced, to schedule both the in-house and the outsourced jobs, and to determine a transportation plan for the outsourced jobs so as to minimize the sum of the makespan and the outsourcing and transportation costs. Two mathematical models of the problem and several necessary optimality conditions are presented. A solution approach is then proposed by incorporating the dominance properties with an ant colony algorithm. Finally, computational experiments are conducted to evaluate the performance of the models and solution approach.     

Two enhanced differential evolution algorithms for job shop scheduling problems

This paper proposes two new differential evolution algorithms (DE) for solving the job shop scheduling problem (JSP) that minimises two single objective functions: makespan and total weighted tardiness. The proposed algorithms aim to enhance the efficiency of the search by dynamically balancing exploration and exploitation ability in DE and avoiding the problem of premature convergence. The first algorithm allows DE population to simultaneously perform different mutation strategies in order to extract the strengths of various strategies and compensate for the weaknesses of each individual strategy to enhance the overall performance. The second algorithm allows the whole DE population to change the search behaviour whenever the solutions do not improve. This study also introduces a modified local mutation operation embedded in the two proposed DE algorithms to promote exploitation in different areas of the search space. In addition, a local search technique, called Critical Block (CB) neighbourhood, is applied to enhance the quality of solutions. The performances of the proposed algorithms are evaluated on a set of benchmark problems and compared with results obtained from an efficient existing Particle Swarm Optimisation (PSO) algorithm. The numerical results demonstrate that the proposed DE algorithms yield promising results while using shorter computing times and fewer numbers of function evaluations.