The production capacity of job shops with limited storage space

Suppose the number of jobs which can be stored in front of the machines in a job shop is limited. As a result, arriving jobs for which there is no space in the shop will form a shop queue. The production capacity or maximum departure rate of jobs from the shop will depend on the way in which jobs are selected from the shop queue for release to the machine queues. For a job shop with two identical machines and random routing of jobs a number of release rules are compared. It is shown that the production capacity is increased when the number of jobs in the shop is kept less than the available storage space. Among release rules independent'of job processing times and number of operations the optimum release rule is shown, using dynamic programming, to be the idle machine rule, i.e. only release a job to the shop when a machine would otherwise be idle.     

Implementation of a demand-pull system in a job shop environment

This paper describes an implementation of JIT concepts in a medium-sized make-to-order manufacturing company. We develop a hybrid production control system for the company based on separating jobs with high production volumes following a standard routeing from relatively low-volume jobs with more complex routeings. The machines processing the high-volume standard-routeing jobs are treated as a virtual flow shop and controlled by a hybrid push/pull system, while the remainder of the floor is managed as a job shop. Initial tests have shown that this system can significantly improve throughput and simplify the production scheduling task. We believe that the system can be applied to a wide range of industries with similar characteristics. We also describe the testing of the system and the circumstances under which its implementation was discontinued, which indicate some of the difficulties faced by small manufacturers in implementing such systems.     

基于规则和仿真的多机并行作业车间生产调度研究

资源分派和能力分派是作业车间生产调度中的重要问题,路径选择规则和分派规则是解决上述问题的有效途径。采用基于规则的仿真研究多机并行作业车间资源分派和能力分派问题,分析工件加工时间、到达率以及机器加工速率对调度结果的影响,以平均完工时间、平均延迟交货率以及平均资源利用率为评价指标,通过对4种路径选择规则和6种分派规则的仿真试验,确定不同性能指标下最佳的调度规则。仿真研究表明:调度规则的选用取决于车间资源配置和调度目标,应避免仅凭借经验或偏好选择规则的调度方法。     

A priority scheduling approach for flexible job shops with multiple process plans

This paper considers the job shop scheduling problem with alternative operations and machines, called the flexible job shop scheduling problem. As an extension of previous studies, operation and routing flexibilities are considered at the same time in the form of multiple process plans, i.e. each job can be processed through alternative operations, each of which can be processed on alternative machines. The main decisions are: (a) selecting operation/machine pair; and (b) sequencing the jobs assigned to each machine. Since the problem is highly complicated, we suggest a practical priority scheduling approach in which the two decisions are done at the same time using a combination of operation/machine selection and job sequencing rules. The performance measures used are minimising makespan, total flow time, mean tardiness, the number of tardy jobs, and the maximum tardiness. To compare the performances of various rule combinations, simulation experiments were done on the data for hybrid systems with an advanced reconfigurable manufacturing system and a conventional legacy system, and the results are reported.     

Distributed production planning using a graph-based negotiation protocol

A distributed model for allocating a single job to be processed through multiple machines and alternative routings so that the job flow time is experimentally shown to reach its minimum is presented. Issues are addressed pertaining to dynamic and fully distributed decision-making for determining the job flow time in a cooperative manner between system agents (i.e. machines and a job), and for selecting a good routing (i.e. a short flow time) for a job when alternative routings are available. Two cases with confirmed jobs and without confirmed jobs are examined. The proposed protocols can deal with job shop scheduling with multiple product types in a sequential manner. The model is developed on the basis of a distributed shortest path algorithm using asynchronous job-initiated protocols. These protocols are examined using object-oriented simulation models and it is shown how the agents converge to the optimal path in a finite time.     

A job shop distributed scheduling based on Lagrangian relaxation to minimise total completion time

This paper considers a distributed job shop scheduling problem where autonomous sub-production systems share common machines with each other. Each sub-production system is responsible for the scheduling of a set of jobs to minimise the total completion time on shared machines. A sub-production system has ultimate responsibility on maintaining private information such as objective function, processing time and routings on shared machines. Also sub-production systems must cooperate each other in order to achieve a global goal while sharing minimum of private information. In this research, we propose a distributed cooperation method in which sub-production systems and shared machines interact with one another to find a compromised solution between a locally optimised solution and a system-wide solution. We tested the proposed method for small, medium and large size of job shop scheduling problems and compared to a global optimal solutions. The proposed method shows promising results in terms of solution qualities and computational times.     

A simple metaheuristic approach to the simultaneous scheduling of machines and automated guided vehicles

In this paper we address the problem of simultaneous scheduling of machines and vehicles in flexible manufacturing systems. The studied problem is a job shop where the jobs have to be transported between the machines by automatic guided vehicles. In addition to the processing of jobs, we consider the transportation aspect as an integral part of the optimization process. To deal with this problem, we propose a new solution representation based on vehicles rather than machines. Each solution can thus be evaluated using a discrete event approach. An efficient neighbouring system is then described and implemented into three different metaheuristics: iterated local search, simulated annealing and their hybridisation. Computational results are presented for a benchmark of 40 literature instances. New upper bounds are found for 11 of them, showing the effectiveness of the presented approach.     

Routing-based reactive scheduling policies for machine failures in dynamic job shops

A scheduling and control system can be viewed as a vital component of modern manufacturing systems that determines companies' overall performance in their respective supply chains. This paper studies reactive scheduling policies developed against unexpected machine failures. These reactive policies are based on rerouting the jobs to their alternative machines when their primary machine fails. Depending on the subset of the jobs considered for rerouting, the long-term performance of four policies are tested under various conditions. Expecting that these rerouting policies would bring an extra load for a material-handling system (MHS), a dynamic job shop environment was studied with and without a MHS. It is shown that the proper selection of a good reactive policy is based not only on the system characteristics such as utilization, machine down times and frequency of machine failures, but also on the MHS capacity (in terms of speed and number of MH devices). The extensive experiments show that when the MHS is not a bottleneck and/or the down times are long enough to compensate the cost of extra rerouting, rerouting all affected jobs to their alternative machines proves to be the best policy. However, when the MHS cannot handle the extra load due to rerouting or the down times are relatively short, then rerouting only the jobs that will arrive to the failed machine during repair performs the best.     

Dispatching in a multistage job shop where machine capacities are unbalanced

In the multistage job shop, several parts are assembled to form sub-assemblies which are then assembled into final products. Job delays may occur due to the lack of capacity and also due to the lack of component parts necessary to form a subassembly. Previous research of similar systems have assumed a balanced capacity. A more realistic assumption is one in which machine capacities are not balanced such that one machine can be identified as a bottleneck. In this paper, the performance of selected dispatching rules in an unbalanced multistage job shop is evaluated to-determine whether the performance is consistent for jobs which are routed through the bottleneck and for jobs which by-pass the bottleneck.     

Scheduling production tasks in a two-stage FMS

The paper is concerned with construction of a heuristic algorithm for an existing two-machine FMS. The system contains two dedicated machines with an automatic transport system served by one robot. There are three storage places: unlimited input and output buffers and a limited transitional one. The jobs are grouped into batches of identical parts. The parts are produced in a flow shop production environment. The parameters like release dates and set-up times for batches are taken into account. Furthermore, some of the parts need an additional operation processed by cooperatives between the first and second operation of the job. The heuristic algorithm has been constructed for the makespan criterion. Appropriate computational experiments validated the model and the algorithm proposed.     

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.     

A practical approach to scheduling a multistage,multiprocessor flow-shop problem

This paper describes a rubber manufacturing system and the numerous technological, operating and quality constraints governing its scheduling process. The complex system resembles a flow-shop problem where all jobs share the same general processing order on a progression of machines. The manufacturing system is defined in terms of production stages and parallel processing lines. One stage can process two or more jobs simultaneously. Jobs are often split on the last stage so that two or more parallel processing lines process the same job simultaneously. The scheduling for such a multistage, multiprocessor flow shop is dominated by the quality constraints. A pragmatic approach is provided in which a schedule is constructed through extensive iterations of analysis and simulation.     

A batch splitting method for a job shop scheduling problem in an MRP environment

The job shop scheduling problem has been a major target for many researchers. Unfortunately though, most of the previous research was based on assumptions that are different from the real manufacturing environment. Among those distorted assumptions, two assumptions about set-up time and job composition can greatly influence the performance of a schedule. First, most of the past studies ignored the impact of the before-arrival set-up time. If we know the sequence of operations in advance, we can obtain an improved schedule by preparing the setup before a job arrives. Secondly, most of the past studies assumed that a job consists of only a single part, that is a batch of size one. However, if we assume that a job consists of a batch size greater than one, as in many real manufacturing environments, then we can obtain an improved schedule because we can fill up the idle times of machines with jobs which have smaller processing times by splitting the original batches. However, the number of job orders may then increase due to the split, and the size of the scheduling problem would become too large to be solved in a practical time limit. Consequently, there may be an optimum batch size considering trade-off between better solution and tractability. The current study is the result of an attempt to find an acceptable solution when the production requirement from a MRP system for a planning period exceeds the capacity of a production system. We try to get an improved schedule by splitting the original batch into smaller batches, and consider setting up a machine before the actual arrival of jobs to that machine. Thereby we can meet the due date requirement without resorting to rescheduling of the master production schedule. For the given batch, we disaggregate it according to the algorithm we are proposing. A so-called 'modified shifting bottleneck procedure' is then applied to solve the job shop scheduling problem with a before-arrival family set-up time considering release date, transportation time and due date. The study also shows that we can adapt to unexpected dynamic events more elegantly by allowing the splitting of batches.     

Minimizing production flow time in a process and assembly job shop

Scheduling is one of the most important issues in the planning and operation of production systems, but in medium to large shops, the generation of consistently good schedules has proven to be extremely difficult. The problem is that optimal scheduling solutions involve costly and impractical enumeration procedures. In the literature, most scheduling problems only address jobs with serial or sequential operations. Rarely do they consider jobs in which machining and assembly operations are simultaneously involved. This lack of attention to scheduling problems that involve both machining and assembly goes against what one would normally find in most job shops. In this paper, the problem of scheduling a set of N final products on M machines in a job shop environment that involve both machining and assembly operations is addressed. The objective pursued is the minimization of production flow time (makespan). A mathematical model is developed in an effort to obtain optimal solutions. Because this type of model grows exponentially as the size of the problems increases, an heuristic solution approach is developed to solve the problems more efficiently. The models are tested and compared on several test problems.     

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 a no-wait flow shop containing unbounded batching machines

We study the problem of scheduling n jobs in a no-wait flow shop consisting of m batching machines. Each job has to be processed by all the machines. All jobs visit the machines in the same order. A job completed on an upstream machine should be immediately transferred to the downstream machine. Batching machines can process several jobs simultaneously in a batch so that all jobs of the same batch start and complete together. The processing time of a batch is equal to the maximum processing time of the jobs in this batch. We assume that the capacity of any batch is unbounded. The problem is to find an optimal batch schedule such that the maximum job completion time, that is the makespan, is minimized. For m = 2, we prove that there exists an optimal schedule with at most two batches and construct such a schedule in O(n log n) time. For m = 3, we prove that the number of batches can be limited to nine and give an example where all optimal schedules have seven batches. Furthermore, we prove that the best schedules with at most one, two and three batches are 3-, 2- and 3/2-approximate solutions, respectively. The first two bounds are tight for corresponding schedules. Finally, we suggest an assignment method that solves the problem with m machines and at most r batches in O(n^{m(r-2)+1+[m/r]}) time, if m and r are fixed. The method can be generalized to minimize an arbitrary maximum cost or total cost objective function.     

Impact of sequence-dependent setup time on job shop scheduling performance

In a production system using multi-purpose and flexible machines, reducing setup time is an important task for better shop performance. Numerous cases were reported about successful reduction of setup times by standardization of setup procedures. However, setup times have not been eliminated and remain an important element of real production problems for production systems such as commercial printing, plastics manufacturing, metal processing, etc. It is especially critical when the setup time is sequence dependent. In this situation, shop performance cannot be effectively improved without the aid of an appropriate scheduling procedure. Review of the past studies shows that there has not been a significant amount of research done on the scheduling procedure for a dynamic job shop with sequence dependent setup times. This paper investigates the job shop scheduling problems that are complicated by sequence-dependent setup times. The study classifies and tests scheduling rules by considering whether setup time and/or due date information is employed. These scheduling rules are evaluated in dynamic scheduling environments defined by due date tightness, setup times and cost structure. A simulation model of a nine machine job shop is used for the experiment. A hypothetical, asymmetric, setup time matrix is applied to the nine machines.     

A simulation based approach to analyse the effects of job release on the performance of a multi-stage job-shop with processing flexibility

Workload control concepts are advocated as one of the new production planning and control methods. In its elaborated form, workload control includes three major decision levels: job entry, job release and priority dispatching. In each decision level, several decision points which have significant impact on the effectiveness of the production planning and control are defined (i.e., acceptance/rejection, due date assignment, etc.). Workload control systems should consider all of these decision points simultaneously in order to improve the effectiveness of production planning and control. In addition to these decision levels, flexibility of the shop can also be included as the fourth decision level which allows the shop capacity to be adjusted as new orders enter the system and as they are released to the shop floor. In this study, simulation models which enable the effect of each decision level within a workload control concept to be explored are developed and tested. The results reveal that simultaneous consideration of decision levels is critical and can improve the effectiveness of production planning and control.     

Production sequencing problem with re-entrant work flows and sequence dependent setup times

This paper addresses a shop scheduling problem where a set of n jobs needs to be scheduled on two machines for the side frame press shop in a truck manufacturing company. A most unusual aspect of the problem is that the setup times required for a job in the first machine depend not on the immediately preceding job but on the job which is two steps prior to it. Redefining the job elements, the problem is formulated into a general two machine flow shop problem which can be solved by dynamic programming with the objective of the minimum makespan. An optimal schedule is found utilizing the sequence dominance conditions and the decisiondelay scheme. Since the computational requirements of dynamic programming are impracticably demanding for large-sized problems, a genetic algorithm is developed and its performance is examined through a comparative study.     

Managing flexible manufacturing technology: Must parts in an FMS always move in a job-shop manner?

The literature typically assumes that an FMS consists of a number of machines of different processing capability. Furthermore, in view of the inherent flexibility of an FMS, many researchers believe that 'flexible' implies that a wide variety of parts can be, and should be, processed simultaneously in an FMS. To do otherwise will inevitably mean some machines are idle and hence the FMS may become a tremendous waste. This paper is an attempt to study this issue. Unlike a job shop, which is typically an eclectic collection of machines of different process capabilities, most flexible manufacturing systems consist of only one or two types of versatile programmable machines. We contend that the FMS machines are analogous to the multi-skilled workers in lean production. In lean production, workers work in teams. It is common for each team to work on one job at a time, from start to finish. Jobs are not passed around from worker to worker. Likewise, machines in an FMS can be assigned into 'teams', where each 'team' is dedicated to process a single part type (or family) at a time. Parts do not necessarily have to move from machine to machine in a job shop manner.