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.     

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.     

On Ashour's decomposition algorithm for shop scheduling problems

This note exposes an oversight in the development of a decomposition approach to the shop scheduling problem reported previously. Included is a brief account of the original algorithm, exposure of its weakness via a small example and a suggested modification.     

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.     

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.     

An analogue genetic algorithm for solving job shop scheduling problems

This paper develops a genetic algorithm for solving job shop scheduling problems. It discusses the difficulties arising from the traditional encoding of the problem and suggests a new encoding scheme. The paper also develops an analogue electrical system to represent the problem and uses the measure of that system to develop a new measure for the fitness function of the genetic algorithm. The algorithm considers the conventional genetic operations but with some modification. The computational results, developed for the makespan criterion, show that, for this criterion, the algorithm is reliable and performs relatively well.     

Job shop scheduling with alternative machines

In this paper we investigate the problem of minimizing the mean flow time in a general job shop type machining system with alternative machine tool routeings. An analytical formulation of the problem as a mixed integer programming is developed. An efficient algorithm based on this formulation is developed to solve the problem by decomposing it into subproblems that are easier to solve. The algorithm solves large problems in relatively short time. A second algorithm based on the SPT rule is developed and its performance is compared with the first algorithm. A greedy procedure is also developed for the case when a penalty cost is associated with adding alternative machines. Numerical examples are given to demonstrate the use of the above algorithms.     

Load smoothing with feedback in a bottleneck job shop

Most of the past research on job shop scheduling has assumed the shop environment where the load-smoothing function in the production planning and control system is ignored and consequently no visibility is provided to the shop. In practice, some kind of load-smoothing is used to smooth the work load level of the shop across the periods, by pulling jobs forward or pushing jobs back. In this study, three load-smoothing approaches with two levels of control for each approach are proposed and tested with two order review/release decisions in a bottleneck job shop. No smoothing becomes a benchmark. Also, the effectiveness of a feedback loop between load-smoothing and the shop floor is investigated. Experiments were conducted in a six-machine job shop simulation model. Results showed that the employment of load-smoothing is important, and pulling jobs forward in a valley period is better than pushing back jobs in a peak period. Controlling the release of jobs to the shop floor in the order review/release phase, given the amount of jobs to be processed during the planning period, is not effective. Also, the feedback system between the planning phase and shop floor to maintain the minimum shop load becomes much more important than simply controlling job release time.     

Two-stage flow shop scheduling with dedicated machines

This study is concerned with the manufacturing model that has a common machine at stage one and two parallel dedicated machines at stage two. All jobs need to be processed on the stage-one common machine. After the stage-one processing, the jobs of type 1 (type 2) will route to the first (second) dedicated machine at stage two. We first elaborate several published works on makespan minimisation which are not known to other streams of recent works. While the minimisation of maximum lateness is strongly NP-hard, we develop a linear-time algorithm to solve the case where two sequences of the two job types are given a priori.     

A genetic algorithm based procedure for more realistic job shop scheduling problems

This work presents a robust procedure to solve job shop scheduling problems with large number of more realistic constraints such as jobs with several subassembly levels, alternative processing plans for parts and alternative resources for operations, requirement of multiple resources to process an operation (e.g. machine, tools, fixtures, staff), resource calendars, batch overlap and sequence dependent setups. Also, the approach considers multi-objective evaluation functions. The system uses modified schedule generation algorithms to obtain a set of initial solutions. Each initial solution is enhanced by a local improvement procedure. Then a hybrid genetic algorithm, which incorporates a local hill climbing procedure, is applied to the set of local optimum schedules.     

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.     

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.     

Hybrid algorithm based on improved extended shifting bottleneck procedure and GA for assembly job shop scheduling problem

With the makespan as the optimisation goal, we propose a hybrid solving method that combines improved extended shifting bottleneck procedure (i-ESB) and genetic algorithm (GA) for the assembly job shop scheduling problem (AJSSP). Hybrid genetic algorithm (HGA) uses a GA based on operation constraint chain coding to achieve global search and a local search based on an i-ESB. In the design of i-ESB, an extended disjunctive graph model (EDG) corresponding to AJSSP is presented. The calculation method of the operation head and tail length based on EDG is studied, as well as the searching method of key operations. The Schrage algorithm with disturbance is used to solve the single-machine scheduling subproblem. The selection criterion for bottleneck machines is increased. A greedy bottleneck machine re-optimisation process is designed. The effectiveness and superiority of the proposed algorithm are verified by testing and analysing the relevant examples in the literature.     

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.     

Seqential approach in job shop scheduling

Abstract

This study investigats a new approach‐the sequential approach‐ in job shop scheduling. The objective is to minimize the total of lateness cost and set‐up cost in job shops. Whenever a scheduling decision has to be made as to which job should receive the next processing, this approach considers each cost sequentially. One of the two costs is considered first, and every time all waiting jobs must be examined in terms of this cost, and only those jobs qualified would the second cost apply to and from which a job would be selected for processing. This investigation was carried out by using GASP IV simulation under a variety of job shop situations. The effectiveness of this approach and job selection mechanism constitute the main theme of this study.     

Time- and cost-based priorities for job shop scheduling

Competitively, cost- and time-based scheduling should provide a firm with a powerful market advantage. The cost- and time-based priority scheduling concept is driven by profit maximization and quick response in a competitive market. The literature on shop scheduling contains numerous studies reporting on the use of dispatching rules that are based only on the time criterion. Alternatively there have been only a few published articles that specifically consider a composite of cost and time. Aggarwal and McCarl and Scudder and Hoffmann have investigated the use of cost and time information for determining the job priority in random job shops. One result of this study is a reconciliation of the differences between the Aggarwal and McCarl and the Scudder and Hoffmann study. Moreover, a simplistic priority rule based on profit margin and due dates is introduced and tested. The results reported in this research are an attempt to reconcile the issue of time-based versus cost-based priority rule performance.     

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.     

Twofold look-ahead search for multi-criterion job shop scheduling

The twofold look-ahead search ((TLAS) was proposed as a general purpose search technique and applied to single-criterion job shop scheduling. In the present study, this method is applied to multi-criterion scheduling problems with some modification and illustrated by bi-criterion scheduling with mean tardiness and mean flowtime. Application circumstances are divided into two situations according to the scheduling objective and TLAS is tested for each situation. From the computational results, the proposed method is found to generate higher performance schedules in comparison with other methods. Its algorithmic features and applicability to other problems are also discussed based on several experimental results.     

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.     

A multiple-pass heuristic rule for job shop scheduling with due dates

This paper presents an efficient multiple-pass heuristic algorithm for job shop scheduling problems with due dates wherein the objective is to minimize total job tardiness. Algorithm operation is carried out in two phases. In phase 1 a dispatching rule is employed to generate an active or non-delay initial schedule. In phase 2, tasks selected from a predetermined set of promising target operations in the initial schedule are tested to ascertain whether by left-shifting their start times and rearranging some subset of the remaining operations one can reduce total tardiness. Performance evaluation is carried out over a range of shop sizes focusing, first of all, on the quality of the initial schedule produced through five commonly used dispatching rules and, secondly, the schedule improvement achieved with the multiple-pass heuristic. Results indicate that the proposed technique is capable of yielding notable reductions in total tardiness (over initial schedules) for practical size problems and would suggest that the approach presents an efficient scheduling option for this class of complex optimization problems.