Linguistic-based meta-heuristic optimization model for flexible job shop scheduling

In this paper, a linguistic based meta-heuristic modelling and solution approach for solving the Flexible Job Shop Scheduling Problem (FJSSP) is presented. FJSSP is an extension of the classical job-shop scheduling problem. The present problem definition is to assign each operation to a machine out of a set of capable machines ( the routing problem ) and to order the operations on the machines ( the sequencing problem ), such that a predefined performance measure is optimized. The scope of the problem is widened by taking into account the alternative process plans for each part ( process plan selection problem ) in the present study. Moreover, instead of using operations to represent product processing requirements and machine processing capabilities, machine independent capability units, which are known as Resource Elements (RE), are used. Representation of unique and shared capability boundaries of machine tools and part processing requirements is possible via RE. Using REs in scheduling can also reduce the problem size. The FJSSP is presented as a grammar and the productions in the grammar are defined as controls. Using these controls and the Giffler and Thompson (1960) priority rule-based heuristic, a simulated annealing algorithm is developed to solve FJSSP. This novel approach simplifies the modelling process of the FJSSP and enables usage of existing job shop scheduling algorithms for its solution. The results obtained from the computational study have shown that the proposed algorithm can solve this complex problem effectively within reasonable time. The results have also given some insights on the effect of the selection of dispatching rules and the flexibility level on the job shop performance. It is observed that the effect of dispatching rule selection on the job shop performance diminishes by increasing the job shop flexibility.     

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.     

Integrated process planning and scheduling using an imperialist competitive algorithm

Effective performance of modern manufacturing systems requires integrating process planning and scheduling more tightly, which is consistently challenged by the intrinsic interrelation and intractability of these two problems. Traditionally, these two problems are treated sequentially or separately. Integration of process planning and scheduling (IPPS) provides a valuable approach to improve system performance. However, IPPS is more complex than job shop scheduling or process planning. IPPS is strongly NP-hard in that, compared to an NP-hard job shop scheduling problem with a determined process plan, the process plan for each job in IPPS is also to be optimised. So, an imperialist competitive algorithm (ICA) is proposed to address the IPPS problem with an objective of makespan minimisation. An extended operation-based representation scheme is presented to include information on various flexibilities of process planning with respect to determined job shop scheduling. The main steps of the proposed ICA, including empires construction, assimilation, imperialistic competition, revolution and elimination, are elaborated using an illustrative example. Performance of the proposed ICA was evaluated on four sets of experiments taken from the literature. Computational results of the ICA were compared with that of some existing algorithms developed for IPPS, which validates the efficiency and effectiveness of the ICA in solving the IPPS problem.     

An application of genetic algorithms to lot-streaming flow shop scheduling

A Hybrid Genetic Algorithm (HGA) approach is proposed for a lot-streaming flow shop scheduling problem, in which a job (lot) is split into a number of smaller sublots so that successive operations can be overlapped. The objective is the minimization of the mean weighted absolute deviation of job completion times from due dates. This performance criterion has been shown to be non-regular and requires a search among schedules with intermittent idle times to find an optimal solution. For a given job sequence, a Linear Programming (LP) formulation is presented to obtain optimal sublot completion times. Objective function values of LP solutions are used to guide the HGA's search toward the best sequence. The performance of the HGA approach is compared with that of a pairwise interchange method.     

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.     

Planning in a Total Quality Company: A Case Study of Tubemakers of Australia Limited

ABSTRACT

Tubemakers of Australia Limited is a major Australian company that has developed a strategic planning process based on the principles of total quality management (TQM). The process is highly participative, with input from the board of directors to the shop floor. This approach generates a high level of commitment to the plan at all levels. The plan, however, is not rigid, and each business unit uses its plan as its day-to-day operations manual, reviewing and updating it as often as necessary.

This planning model, as developed by this company, is effective in integrating the planning process into the company's operations. The company is now pursuing a more formalized, coordinated TQM approach, and, in conjunction with this, the planning process is being modified to more closely match the Japanese Policy Deployment (Hoshin) model. The development of an effective strategic planning process in conjunction with an effective TQM operating style should serve as a model for other organizations.     

Research on Fuzzy Decision of Resources Selection in Job-shop Scheduling for a One-of-a-Kind and Order-Oriented Production System

In a one-of-a-kind and order-oriented production corporation, job shop scheduling plays an important role in the production planning system and production process control. Since resource selection in job shop scheduling directly influences the qualities and due dates of products and production cost, it is indispensable to take resource selection into account during job shop scheduling. By analyzing the relative characteristics of resources, an approach of fuzzy decision is proposed for resource selection. Finally, issues in the application of the approach are discussed.     

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.     

A methodology for planning and controlling workload in a job-shop: a four-way decision-making problem

There has been extensive research on workload and input–output control with the objective of improving manufacturing operations in job-shops. In this paper, a multiple decision-making scheme is proposed to plan and control operations in a general job-shop, and to improve delivery and workload related performance measures. The job-shop characteristics reinforce the need for designing a global system that controls both the jobs entering (order acceptance, due date setting and job release) and the work-in-process (dispatching), leading to an improvement of operational measures. Previous research has concentrated on scheduling a set of orders through the shop floor, according to some decision mechanism, in order to optimise some measure of performance (usually total lead time). This means that, since only a part of the decision-making system is being optimised, the resulting decision may be sub-optimal. In this paper it is shown that the performance of the different decision rules changes when they are considered simultaneously. Hence, a higher level approach, where the four decisions (order acceptance, due date setting, job release and dispatching) are considered at the same time, should be adopted to improve job-shop operational performance.     

Job shop control

The paper defines batch or job shop production and reviews the functions of production planning and production control in a job shop manufacturing situation. It argues that the separation of planning and control has resulted in the artificial isolation of the sequencing problem in job shop research. It attempts to redefine the production control function for a job shop, now called job shop control, and discuss the activities it involves. The major decision-making problems associated with job shop control are highlighted and an objective function of costs to aid in management decision making is evolved.     

Lead time prediction in unbalanced production systems

Whether job due dates are set internally or externally, it is critical for the shop floor controller to be able to accurately predict job lead times. Previous research has shown that utilizing information on the congestion levels along a job's route is more valuable than overall shop congestion levels when predicting job lead times. While this information is easily attained in a simulation model, in industrial applications the task may be considerably more difficult, especially when lot splitting is used to accelerate material flow. We examine the effectiveness of three lead time estimation procedures which utilize different shop information in bottleneck-constrained production systems where lot splitting is practiced under a variety of experimental conditions. The results indicate that accurate lead time estimates can be obtained using information pertaining solely to the bottleneck work centre when the bottleneck is at an entry work centre. This offers operations managers a substantial ease in implementation over previously reported methods. The results also show that the operations managers interested in accurately estimating job lead times are well advised to take advantage of the excess capacity at non-bottleneck work centres by performing additional setups, and take measures that reduce bottleneck shiftiness.     

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.     

Optimal due-date assignment in a job shop†

This paper presents an analytical model for determining the optimal processing-time and number of operations multiples for the TWK and TWK + NOP due-date assignment methods in a dynamic job shop subject to restrictive assumptions on queue discipline and processing time distribution. The analytical results are compared with the experimental results obtained from simulation of a hypothetical job shop under various shop conditions. The close agreement of the results reveals the validity of the analytical model. In addition, the results show that the TWK + NOP method is more effective in minimizing the missed due-date cost in a job shop.     

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 general search sequencing rule for job shop sequencing

This paper sets out, an approach to the job shop sequencing problem by determining the priority of a job from a linear combination of the basic quantities of operation times and due date. This achieves a simple yet unified format. Furthermore, since these basic quantities are used in fixed linear combinations in the majority of well-known simple heuristics, the rule outlined in the paper is capable of representing such heuristics as special cases within its framework. A performance function is used to assess the effectiveness of the rule and no limitations are imposed on its structure. The form of the variable priority rule is then determined by a computer search routine basing its decisions on the values of the performance function. This overall approach to job shop sequencing we term the search sequencing rule (SSR).     

The design and validation of a digital simulation model for job shop control decision making

A previous paper (Browne et al. 1981) identified the decision making problems associated with job shop control and presented an objective function for measuring its performance. Given that definition of job shop control and cost-based objective function, simulation modelling offers the best prospect of a solution of the problem of providing a management tool to aid in the decision making associated with job shop control. This paper provides a detailed analysis of the design of such a model. The model, written in the GASP fV simulation language and running on a CDC 7600 computer, is based on the job shop of a major machine tool manufacturer and has been validated against actual job shop performance.     

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.     

A multi-attribute dispatching rule for automated guided vehicle systems

This paper considers the dispatching problem associated with operations of automated guided vehicles (AGVs). A multi-attribute dispatching rule for dispatching of an AGV is developed and evaluated. The multi-attribute rule, using the additive weighting method, considers three system attributes concurrently: the remaining space in the outgoing buffer of a workstation, the distance between an idle AGV and a workstation with a job waiting for the vehicle to be serviced, and the remaining space in the input buffer of the destination workstation of a job. A neural network approach is used to obtain dynamically adjusting attribute weights based on the current status of the manufacturing system. Simulation analysis of a job shop is used to compare the multi-attribute dispatching rule with dynamically adjusting attribute weights to the same dispatching rule with fixed attribute weights and to several single attribute rules. Results show that the multi-attribute dispatching rule with the ability to adapt attribute weights to job shop operational conditions provides a better balance among the performance measures used in the study.     

The trials, tribulations, and thrills of setting up and operating a one-person computer job shop for calculating magnetics fields and other sundry things

A brief history of job shops since the caveman era is surveyed, and the essential elements of a job shop are found to be: to earn your living performing a useful service, or creating a useful object, for your contemporaries. The complexities of setting up a computer job shop are described. Inspection of a symbolic floor plan of the shop shows a Program Development, Installation, and Repair Lab that operates with the well-known pitfalls and traps that occur when a real live person interacts with a large, stupid computer. The Output Assembly and Analysis Lab is the holding area where up to N projects are worked on simultaneously. On the main floor of the shop resides the program load modules, some of which are described in detail. Separate from the main shop area is the Remote Job Entry Lab, affectionately called the Physics Group Zoo. The creatures that dwell there are also described to illustrate the difficulty in data preparation and job submission. In spite of all these adversities, the thrill of solving complex problems makes it all worthwhile.     

Priority scheduling policies for repair shops

The use of repair as an alternative to the replacement of products is a growing trend in many industries, especially those employing expensive assets. Repair shop environments are characterized by a greater degree of uncertainty than traditional job or assembly shop environments, and this introduces unique managerial complications. In this study, scheduling policies are examined in the repair shop environment where no end-item spares are available or where the spares stocking decision is deferred until the minimum obtainable flowtimes for enditems are established. Previous studies of scheduling policies have focused on the case where spares are allowed and have not considered all of the sources of variation in the repair environment. The model developed in this study incorporates these sources of uncertainty, as well as other factors likely to influence repair shop performance. The results show that the variability in repair shops is sufficiently higher than in traditional job or assembly shops to warrant different scheduling policies than those previously reported. The choice of scheduling policy to provide minimum flowtimes and RMS tardiness is operating-environment specific, and clear guidelines are presented for the manager in a repair shop environment.