Scheduling of a job-shop problem with limited output buffers

ABSTRACT

This article addresses a job-shop problem with limited output buffers (JS-LOB) with the objective of minimizing the process makespan. An integer nonlinear mathematical programming model is proposed to describe this problem. Based on the model, a two-stage algorithm consisting of obtaining feasible solutions and a local search is proposed to solve the JS-LOB problem. The local search has two operators: the first is a neighbourhood structure based on a disjunctive graph model, and the second is similar to crossover in the genetic algorithm to avoid falling into local optima. Computational results are presented for a set of benchmark tests. The results show the effectiveness of the proposed algorithm and indicate whether the processing time of the job conforms to a uniform distribution. When the proportion between the capacity of the buffer and the number of jobs is larger than 20%, the influence of the buffer becomes very small.     

Flow-shop problems with intermediate buffers

In this paper the following extension of the classical flow-shop problem is considered: Between each two consecutive machines a buffer of limited capacity is given. After finishing processing on a machine, a job either directly has to be processed on the following machine or it has to be stored in the buffer between these machines. If the buffer is completely occupied the job may wait on its current machine but blocks this machine for other jobs. The objective is to determine a feasible schedule minimizing the makespan. To model such a problem setting, a variation of the classical disjunctive graph model for shop problems is extended. A tabu search procedure is described where neighborhoods based on an extension of the classical block approach theorem are used. Computational results for extended flow-shop benchmark instances are presented. Corespondence to: Silvia HeitmannThe authors are grateful to Tim Nieberg for implementing the tabu search procedure proposed in this paper.S. Heitmann     

Makespan minimisation for a parallel machine scheduling problem with preemption and job incompatibility

In this paper, an extension of the graph colouring problem is introduced to model a parallel machine scheduling problem with job incompatibility. To get closer to real-world applications, where the number of machines is limited and jobs have different processing times, each vertex of the graph requires multiple colours and the number of vertices with the same colour is bounded. In addition, several objectives related to scheduling are considered: makespan, number of pre-emptions and summation over the jobs’ throughput times. Different solution methods are proposed, namely, two greedy heuristics, two tabu search methods and an adaptive memory algorithm. The latter uses multiple recombination operators, each one being designed for optimising a subset of objectives. The most appropriate operator is selected dynamically at each iteration, depending on its past performance. Experiments show that the proposed algorithm is effective and robust, while providing high-quality solutions on benchmark instances for the graph multi-colouring problem, a simplification of the considered problem.     

Modeling for flexible manufacturing systems with an FMS blocking mechanism and a BDSM job routing

We consider a Flexible Manufacturing System (FMS) which is composed of a set of workstations, a common buffer and a Material Handling System (MHS). Each workstation includes a limited input buffer, several machines and a limited output buffer. The MHS consists of several carts moving jobs among the workstations according to the process paths required by the jobs. The carts treat blocked jobs in accordance with a new blocking mechanism, called the 'FMS blocking mechanism'. The function of the common buffer is to temporarily store blocked jobs. Such an FMS is formulated as an open queueing network, in which the MHS is modeled as a central station routing jobs to the workstations. In the model, the machines process jobs with an exponentially distributed processing time, and the carts route jobs to the workstations following a 'Blocking Depended Static Markov (BDSM) job routing' with an exponentially distributed routing time and treat blocked jobs in accordance with the FMS blocking mechanism. It is shown that the equilibrium state distribution of the model has a product-form solution. The blocking probabilities are obtained by computing a fixed point problem whose solution is revealed by an iterative algorithm. Moreover, it is shown that the throughputs of the workstations are independent of the spaces on the local buffers at the workstations. Several numerical examples are presented.     

Iterated greedy algorithms to minimize the total family flow time for job-shop scheduling with job families and sequence-dependent set-ups

This study addresses a variant of job-shop scheduling in which jobs are grouped into job families, but they are processed individually. The problem can be found in various industrial systems, especially in reprocessing shops of remanufacturing systems. If the reprocessing shop is a job-shop type and has the component-matching requirements, it can be regarded as a job shop with job families since the components of a product constitute a job family. In particular, sequence-dependent set-ups in which set-up time depends on the job just completed and the next job to be processed are also considered. The objective is to minimize the total family flow time, i.e. the maximum among the completion times of the jobs within a job family. A mixed-integer programming model is developed and two iterated greedy algorithms with different local search methods are proposed. Computational experiments were conducted on modified benchmark instances and the results are reported.     

An approach to identify the optimal configurations and reconfiguration processes for design of reconfigurable machine tools

A reconfigurable machine tool (RMT) is a special machine that can deliver different machining functions through reconfiguration processes among its configurations during the machine utilisation stage. In this research, a new approach is developed to identify the optimal configurations and the reconfiguration processes for design of the RMTs. In this work, a generic design AND-OR tree is used to model different design solution candidates, their machine configurations and parameters of these configurations. A specific design solution is created from the generic design AND-OR tree through tree-based search and modelled by different machine configurations. For a reconfiguration process between two machine configurations, a generic process AND-OR graph is used to model reconfiguration operation candidates, sequential constraints among operations and operation parameters. A graph-based search is used to generate all feasible reconfiguration process candidates from the generic process AND-OR graph. The optimal design is identified by multi-level and multi-objective hybrid optimisation. A case study is developed to show how this new approach is used for the optimal design of a RMT.     

Flexible job-shop scheduling problem under resource constraints

A flexible job-shop-scheduling problem is an extension of classical job-shop problems that permit an operation of each job to be processed by more than one machine. The research methodology is to assign operations to machines (assignment) and determine the processing order of jobs on machines (sequencing) such that the system objectives can be optimized. This problem can explore very well the common nature of many real manufacturing environments under resource constraints. A genetic algorithm-based approach is developed to solve the problem. Using the proposed approach, a resource-constrained operations–machines assignment problem and flexible job-shop scheduling problem can be solved iteratively. In this connection, the flexibility embedded in the flexible shop floor, which is important to today's manufacturers, can be quantified under different levels of resource availability.     

A Branch-and-Bound Algorithm for the Continuous-Process Job-Shop Scheduling Problem

The continuous-process job-shop scheduling problem (CPJS) arises typically in the following way: (1) a set of M machines or production facilities are available; (2) a set of N jobs are to be processed through these machines in accordance with a technological matrix; (3) the machines associated with a given job must all be used simultaneously for the completion of this job; (4) a predetermined production time is required for each job; (5) the objective is to determine a production schedule which minimizes the total completion time (makespan) of all jobs. A branch-and-bound type algorithm for the solution of the (CPJS) problem is presented.     

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.     

Lot streaming multiple jobs with values exponentially deteriorating over time in a job-shop environment

The main issue in lot streaming (LS) is determining the means by which to split jobs into sub-jobs to improve the makespan (or some other criterion). However, LS has been overlooked in most studies dealing with scheduling problems associated with specific kinds of job shops, where the job value exponentially deteriorates over time. The current study attempts to determine whether the expected benefits of LS would be evident in the job-shop scheduling problem (JSP) with the objective of maximising the total value of jobs. This study comprised two stages. In the first stage, we studied the influence of a fixed number of sub-jobs on the performance of the LS by systematically varying this parameter using the fixed number job splitting (FNJS) approach. We considered a total of 12 dispatching rules for the analysis of relative performance. Simulation results suggest that dividing each job into several sub-jobs increases the total value of jobs. In addition, dispatching rules incorporating information related to job value perform better than those without this information. In the second stage of the study, we proposed a genetic algorithm-based job splitting (GAJS) approach. The simulation results led us to conclude that the GAJS approach is superior to the FNJS approach in terms of the total value of the jobs and the average number of sub-jobs generated.     

A method combining rules with genetic algorithm for minimizing makespan on a batch processing machine with preventive maintenance

This paper considers the problem of minimising makespan on a single batch processing machine with flexible periodic preventive maintenance. This problem combines two sub-problems, scheduling on a batch processing machine with jobs’ release dates considered and arranging the preventive maintenance activities on a batch processing machine. The preventive maintenance activities are flexible but the maximum continuous working time of the machine, which is allowed, is determined. A mathematical model for integrating flexible periodic preventive maintenance into batch processing machine problem is proposed, in which the grouping of jobs with incompatible job families, the starting time of batches and the preventive maintenance activities are optimised simultaneously. A method combining rules with the genetic algorithm is proposed to solve this model, in which a batching rule is proposed to group jobs with incompatible job families into batches and a modified genetic algorithm is proposed to schedule batches and arrange preventive maintenance activities. The computational results indicate the method is effective under practical problem sizes. In addition, the influences of jobs’ parameters on the performance of the method are analyzed, such as the number of jobs, the number of job families, jobs’ processing time and jobs’ release time.     

Scheduling the fabrication and assembly of components in a two-machine flowshop

In this paper we study the problem of scheduling the fabrication and assembly of components in a two-machine flowshop so as to minimize the makespan. Each job consists of a component unique to that job and a component common to all jobs. Both the unique and the common components are processed on the first machine. While the unique components are processed individually, the common components are processed in batches and a setup is needed to form each batch. The assembly operations of a job is performed on the second machine, and can only begin when both components for the job are available. We first show that the problem is NP-complete with either batch availability or item availability for the common components. We identify several properties of an optimal solution to the problem, and some polynomially solvable special cases.     

An investigation of cooperative dispatching for minimising mean flowtime in a finite-buffer-capacity dynamic flowshop

Scheduling in a dynamic flowshop that receives jobs at random and unforeseen points in time has traditionally been done by using dispatching rules. This study compares the performances of leading dispatching rules with a cooperative dispatching approach, for the objective of minimising mean flowtime in a flowshop, in which the buffers that hold in-process jobs between machines have finite capacities. Cooperative dispatching employs a consultative and consensus-seeking methodology for deciding which job to dispatch next on a machine. Computational experiments using randomly generated test problems for three different utilisation (congestion) levels are carried out for 5- and 10-machine flowshops, under a wide range of buffer capacities. The results highlight the sensitivity of some of the popular dispatching rules to buffer size. In contrast, cooperative dispatching emerges as a robust method that performs consistently well across the range of buffer sizes and machine utilisations tested. The reductions in mean flowtime obtained by cooperative dispatching, in comparison to the other dispatching rules, are particularly large in flowshops that operate with very tight buffer capacities and elevated levels of congestion     

A computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops

We present and compare a number of branch and bound algorithms for minimizing the total weighted tardiness in job shops. There are basically two types of branching schemes. The first one inserts operations in a partial schedule, while the second one fixes arcs in the disjunctive graph formulation of the problem. The bounding schemes are based on the analysis of precedence constraints, and on the solution of nonpreemptive single machine subproblems that are subject to so-called delayed precedence constraints. We obtain optimal solutions for all the instances with ten jobs and ten machines that we consider, including three tardiness versions of a well-known 10 × 10 instance introduced by Muth and Thompson [1] in 1963.     

A new method for the placement of buffers in serial production lines

The placement of buffers in a production line is an old and well-studied problem in industrial engineering/operations research that is still relevant today. Decisions regarding the amount and placement of buffers in a production line occur repeatedly in system design. In this paper we document a new buffer placement method for serial production lines that operate under a variety of assumptions. The method uses information generated in a production line simulation, whose conceptual representation of job flow and workstation interaction can be described with a network, to place buffers in order to maximise throughput. This buffer placement method is very efficient and can be implemented in a spreadsheet. We demonstrate the effectiveness of the method by comparing our results against those produced by a genetic algorithm for buffer placement. Experiments are conducted on a variety of test cases. This new buffer placement optimisation method will permit designers to quickly and effectively evaluate many design alternatives and thus improve final production system performance.     

A computational study of heuristics for two-stage flexible flowshops

We consider the scheduling of two-stage flexible flowshops. This manufacturing environment involves two machine centres representing two consecutive stages of production. Each machine centre is composed of multiple parallel machines. Each job has to be processed serially through the two machine centres. In each machine centre, a job may be processed on any of the machines. There are n independent jobs to be scheduled without preemption. The jobs can wait in between the two machine centres and the intermediate storage is unlimited. Our objective will be to minimize the maximum completion time of the jobs. We formulate the problem as a mixed integer program. Given this problem class is NP-hard in the strong sense, we present three lower bounds to estimate the optimal solution. We then propose a sequence-first, allocate-second heuristic approach for its solution. We heuristically decompose the problem by first creating a priority list to order the jobs and then assign the jobs to the available machines in each machine centre based on this order. We describe seven rules for the sequencing phase. The assignment phase consists of a heuristic which attempts to minimize each partial schedule length while looking ahead at the future assignment of the currently unscheduled jobs. The computational performance of the heuristic approach was evaluated by comparing the value of each heuristic variant to the best among the three lower bounds. Its effectiveness was tested on scenarios pertinent to flexible flowshop environments, such as cellular manufacturing, by conducting a computational study of over 3400 problems. Our computational results indicate that the most effective approach used Johnson's rule to provide the priority list for job assignment. This provided integrality gaps which on the average were less than 0·73%.     

Batch scheduling problem for a machinery factory with fixed-position layout

We consider a batch scheduling problem for a two-stage flow shop with fixed-position layout. In the first stage, a fixed number of jobs are assembled on a batch machine with a family batch setup time and a common processing time. In the second stage, the assembled jobs are individually performed for system integration on a discrete machine. The finished job is immediately packed and shipped if the payment has been made; otherwise, it is moved to a temporary storage area, incurring additional removal time. This study develops a mixed integer programming (MIP) to solve the problem of minimising the total completion time and proposes two heuristics for large-size problems. Computational results show that the proposed methods can be applied to resolve real-world problems similar to those in this study.     

A branch & bound method for the general-shop problem with sequence dependent setup-times

A branch & bound algorithm is presented for a very general scheduling problem withn jobs andm machines. Each job consists of a set of operations. Each operation has to be processed on a dedicated machine. There may be arbitrary precedence relations between the operations. The set of all operations is partitioned into groups. If on a machine an operation belonging to groupG _g is processed immediately after an operation belonging to groupG _f there is a setup ofs _fg time units. We assume thats _fg=0 iff=g and that thes _fg satisfy the triangle inequality. Computational results for this general problem as well as for special cases like the job-shop problem and the open-shop problem are reported.Supported by the Deutsche Forschungsgemeinschaft (Project JoPTAG) and by INTAS (Project 93–257)     

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.     

Fabrication and assembly scheduling in a two-machine flowshop

This paper considers a fabrication scheduling problem to minimize the makespan in a two-machine flowshop. Each job has a unique component and a common component to be processed on the first machine. On machine 1, the common components of the jobs are grouped into batches for processing with a setup cost incurred whenever a batch is formed. A job is ready for its assembly operation on the second machine if both its unique and common components are finished on machine 1. The problems with batch availability and item availability are known as NP-hard. In this paper, we give proofs for the strong NP-hardness of the two problems. The results suggest that it is very unlikely to develop polynomial- or pseudo-polynomial-time algorithm for finding exact solutions for the two problems.