Dynamic scheduling of manufacturing job shops using extreme value theory

Most job shop scheduling approaches reported in the literature assume that the scheduling problem is static (i.e. job arrivals and the breakdowns of machines are neglected) and in addition, these scheduling approaches may not address multiple criteria scheduling or accommodate alternate resources to process a job operation. In this paper, a scheduling method based on extreme value theory (SEVAT) is developed and addresses all the shortcomings mentioned above. The SEVAT approach creates a statistical profile of schedules through random sampling, and predicts the quality or 'potential' of a feasible schedule. A dynamic scheduling problem was designed to reflect a real job shop scheduling environment closely. Two performance measures, viz. mean job tardiness and mean job cost, were used to demonstrate multiple criteria scheduling. Three factors were identified, and varied between two levels each, thereby spanning a varied job shop environment. The results of this extensive simulation study show that the SEVAT scheduling approach produces a better performance compared to several common dispatching rules.     

A simulated annealing algorithm for job shop scheduling

In this paper, the job shop scheduling problem is considered with the objective of minimization of makespan time. We first reviewed the literature on job shop scheduling using meta-heuristics. Then a simulated annealing algorithm is presented for scheduling in a job shop. To create neighbourhoods, three perturbation schemes, viz. pairwise exchange, insertion, and random insertion are used, and the effect of them on the final schedule is also compared. The proposed simulated annealing algorithm is compared with existing genetic algorithms and the comparative results are presented. For comparative evaluation, a wide variety of data sets are used. The proposed algorithm is found to perform well for scheduling in the job shop.     

一个单件车间生产作业计划优化模拟系统

针对中小批量单件车间生产作业计划生成与再生问题,集成Visual Foxpro5.0与Siman 3.51开发了一个系统原型,包括模拟模型生成器、时间参数推算器和禁忌搜索算法。用模拟模型生成器得到一个比较详细的中小批量单件车间生产作业计划方案,以此为初始可行解,再用时间参数推算器和禁忌搜索算法进行优化,得到一个优化了的车间生产作业计划方案。实验表明,本系统较好地解决了中小批量单件车间生产作业计划生成问题。     

GLOBAL JOB SHOP SCHEDULING WITH A GENETIC ALGORITHM

This paper describes a global job shop scheduling procedure that uses a genetic algorithm to find a good schedule. Unlike previously considered algorithms, this procedure has been implemented in the scheduling system for a manufacturing facility and has led to improved scheduling. This facility is a semiconductor test area. The test area is a job shop and has sequence-dependent setup times at some operations. The concern of management is to meet their customer due dates and to increase throughput. This requires the coordination of many resources, a task beyond the ability of simple dispatching rules. We discuss a centralized procedure that can find a good schedule through the use of a detailed scheduling model and a genetic algorithm that searches over combinations of dispatching rules. We discuss our effort in developing a system that models the shop, creates schedules for the test area personnel, and makes a number of contributions to test area management.     

MRP in a job shop environment using a resource constrained project scheduling model

One of the most difficult tasks in a job shop manufacturing environment is to balance schedule and capacity in an ongoing basis. MRP systems are commonly used for scheduling, although their inability to deal with capacity constraints adequately is a severe drawback. In this study, we show that material requirements planning can be done more effectively in a job shop environment using a resource constrained project scheduling model. The proposed model augments MRP models by incorporating capacity constraints and using variable lead time lengths. The efficacy of this approach is tested on MRP systems by comparing the inventory carrying costs and resource allocation of the solutions obtained by the proposed model to those obtained by using a traditional MRP model. In general, it is concluded that the proposed model provides improved schedules with considerable reductions in inventory carrying costs.     

Evaluation of scheduling strategies for a dynamic job shop in a tool-shared,flexible manufacturing environment

A two-phase approach is used to examine the impact of job scheduling rules and tool selection policies for a dynamic job shop system in a tool-shared, flexible manufacturing environment. The first phase develops a generalized simulation model and analyses 'simple' job scheduling rules and tool selection policies under various operating scenarios. The results from this investigation are then used to develop and analyse various bi-criteria rules in the second phase of this study. The results show that the scheduling rules have the most significant impact on system performance, particularly at high shop load levels. Tool selection policies affect some of the performance measures, most notably, proportion of tardy jobs, to a lesser degree. Higher machine utilizations can be obtained at higher tool duplication levels but at the expense of increased tooling costs and lower tool utilization. The results also show that using different processing time distributions may have a significant impact on shop performance.     

Dynamic selection of dispatching rules for job shop scheduling

Although the academic contribution to job shop scheduling is abundant, its impact on practice has been minimal. The most preferred approach to job shop scheduling in the industry is dispatching rules. A major criticism against dispatching rules is that there is no single universal rule. The effective choice of dispatching rules depends on the scheduling criterion and existing job shop conditions. In this paper, the authors have proposed a scheduling method based on the analytic hierarchy process, that dynamically selects the most appropriate dispatching rule from several candidate rules. The selection is based on the existing job shop conditions. This method is applied to two formal job shop problems, and the results for single dispatching rules are inferior to the method proposed in this paper.     

A Virtual Cellular Manufacturing Approach to Batch Production*

In this paper, Virtual Cellular Manufacturing (VCM), an alternative approach to implementing cellular manufacturing, is investigated. VCM combines the setup efficiency typically obtained by Group Technology (GT) cellular manufacturing (CM) systems with the routing flexibility of a job shop. Unlike traditional CM systems in which the shop is physically designed as a series of cells, family-based scheduling criteria are used to form logical cells within a shop using a process layout. The result is the formation of temporary, virtual cells as opposed to the more traditional, permanent, physical cells present in GT systems. Virtual cells allow the shop to be more responsive to changes in demand and workload patterns. Production using VCM is compared to production using traditional cellular and job shop approaches. Results indicate that VCM yields significantly better flow time and due date performance over a wide range of common operating conditions, as well as being more robust to demand variability.     

An Experimental Comparison of Time-Based and Economic-Based Scheduling Methods to Maximize Net Present Value*

In the past, performance in dynamic-scheduling environments was primarily measured in terms of time or physical shop characteristics. Objectives such as mean tardiness, flow time, and work-in-process inventory were commonly used. Today, there is increasing interest in the use of more advanced economic performance measures. These measures have the more comprehensive objective of maximizing ownership wealth by economically scheduling jobs and tasks. This study presents a large-scale experiment testing time-based and economic-based scheduling methods in a dynamic job shop. These methods are evaluated on their ability to maximize net present value (NPV). The study considers the just-in-time (JIT) delivery environment. The job shop is hypothetical, but is based on models of real production situations. Results show that the use of very detailed economic information in a sophisticated manner generally improves economic performance. Where due dates are easy to achieve, however, time-based scheduling methods are at least as good as those based on economics. Also, where utilization is high and due dates tight, early cost information in release and dispatch is detrimental to schedule value.     

Asymptotically optimal policy for stochastic job shop scheduling problem to minimize makespan

This paper studies the large-scale stochastic job shop scheduling problem with general number of similar jobs, where the processing times of the same step are independently drawn from a known probability distribution, and the objective is to minimize the makespan. For the stochastic problem, we introduce the fluid relaxation of its deterministic counterpart, and define a fluid schedule for the fluid relaxation. By tracking the fluid schedule, a policy is proposed for the stochastic job shop scheduling problem. The expected value of the gap between the solution produced by the policy and the optimal solution is proved to be O(1), which indicates the policy is asymptotically optimal in expectation.     

Shop floor control system for tool rooms

A shop floor control system (SFCS), which is the most important component of any production control system, ff has a direct e ect on the productivity of a tool room. The SFCS presented in this paper aims at streamlining various tool room activities, such as process planning, operations scheduling, loading, progress monitoring, and performance monitoring. The system discussed in this paper is characterized by simplicity and is user friendly. Basic information, consisting of three types of information (order details, process details, and part details), is input through interactive dialogue sessions. On-line updating of the process information is carried out, again through interactive dialogue sessions. The basic input to the system along with the on-line updating enables a number of useful and important reports and documents to be generated ff by the system for e ective control of the shop floor. The reports generated include operations scheduling, process sheet, part list, ffi job card, load pending report, e ciency report, etc. This SFCS is developed for a medium sized tool room in an automotive company and its successful implemention reduced paperwork and improved resource management and has resulted in productivity. It can be said that this system offers a first venture into computer integrated manufacturing (CIM) for a tool room.     

The flexible blocking job shop with transfer and set-up times

The Flexible Blocking Job Shop (FBJS) considered here is a job shop scheduling problem characterized by the availability of alternative machines for each operation and the absence of buffers. The latter implies that a job, after completing an operation, has to remain on the machine until its next operation starts. Additional features are sequence-dependent transfer and set-up times, the first for passing a job from a machine to the next, the second for change-over on a machine from an operation to the next. The objective is to assign machines and schedule the operations in order to minimize the makespan. We give a problem formulation in a disjunctive graph and develop a heuristic local search approach. A feasible neighborhood is constructed, where typically a critical operation is moved (keeping or changing its machine) together with some other operations whose moves are “implied”. For this purpose, we develop the theoretical framework of job insertion with local flexibility, based on earlier work of Gröflin and Klinkert on insertion. A tabu search that consistently generates feasible neighbor solutions is then proposed and tested on a larger test set. Numerical results support the validity of our approach and establish first benchmarks for the FBJS.     

Multi-objective permutation flow shop scheduling problem: Literature review,classification and current trends

The flow shop scheduling problem is finding a sequence given n jobs with same order at m machines according to certain performance measure(s). The job can be processed on at most one machine; meanwhile one machine can process at most one job. The most common objective for this problem is makespan. However, many real-world scheduling problems are multi-objective by nature. Over the years there have been several approaches used to deal with the multi-objective flow shop scheduling problems (MOFSP). Hence, in this study, we provide a brief literature review of the contributions to MOFSP and identify areas of opportunity for future research.     

A STOCHASTIC DOMINANCE ORDERING OF SCHEDULING RULES

This paper applies stochastic dominance (SD) preference-ordering criteria to job shop scheduling rules. A simulation model of a hypothetical dual-constrained job shop is used to derive several measures of shop performance for a number of dispatching/due-date scheduling policies. The results presented suggest that previous research conclusions concerning the relative performance of dispatching scheduling rules may need to be reconsidered if production schedulers are risk-averse utility maximizers.     

The blocking job shop with rail-bound transportation

The blocking job shop with rail-bound transportation (BJS-RT) considered here is a version of the job shop scheduling problem characterized by the absence of buffers and the use of a rail-bound transportation system. The jobs are processed on machines and are transported from one machine to the next by mobile devices (called robots) that move on a single rail. The robots cannot pass each other, must maintain a minimum distance from each other, but can also “move out of the way”. The objective of the BJS-RT is to determine for each machining operation its starting time and for each transport operation its assigned robot and starting time, as well as the trajectory of each robot, in order to minimize the makespan. Building on previous work of the authors on the flexible blocking job shop and an analysis of the feasible trajectory problem, a formulation of the BJS-RT in a disjunctive graph is derived. Based on the framework of job insertion in this graph, a local search heuristic generating consistently feasible neighbor solutions is proposed. Computational results are presented, supporting the value of the approach.     

Overtime usage in a job shop environment

Problems are encountered in a job shop which has a fixed capacity if the total work content of the jobs passing through the shop increases sufficiently. Even the use of effective priority dispatching rules and/or expediting does not adequately shorten the queues which develop if the total work content continually exceeds shop capacity. To avoid losing job orders because the orders are unduly delayed, the job shop might resort to overtime usage. This study examines the efficient and economic use of overtime to relieve the backlog problem and uses overtime as the basic criterion for evaluation of overtime usage. The study employs GPSS V programming language to simulate a hypothetical job shop. The shop is loaded to various proportions of its normal capacity and various levels of overtime are tested. Findings show that overtime should not be assigned indiscriminately but rather should be based on a shop's unique conditions of overtime cost, the priority rule being employed, and the level of capacity utilization. Marginal benefit-cost ratio curves are developed to determine whether overtime usage is economically reasonable. These curves may also be used to determine the maximum or limiting amount of overtime to use under specific shop conditions.     

The no-wait job shop with regular objective: a method based on optimal job insertion

The no-wait job shop problem (NWJS-R) considered here is a version of the job shop scheduling problem where, for any two operations of a job, a fixed time lag between their starting times is prescribed. Also, sequence-dependent set-up times between consecutive operations on a machine can be present. The problem consists in finding a schedule that minimizes a general regular objective function. We study the so-called optimal job insertion problem in the NWJS-R and prove that this problem is solvable in polynomial time by a very efficient algorithm, generalizing a result we obtained in the case of a makespan objective. We then propose a large neighborhood local search method for the NWJS-R based on the optimal job insertion algorithm and present extensive numerical results that compare favorably with current benchmarks when available.     

Order Dispatching and Labor Assignment in Cellular Manufacturing Systems

Although order and labor dispatching in the job shop manufacturing setting have been investigated extensively over the last three decades, its representation of actual processes found in practice today is limited due to the move to cellular manufacturing (CM). Manufacturing cells have become an important approach to batch manufacturing in the last two decades, and their layout structure provides a dominant flow structure for the part routings. The flow shop nature of manufacturing cells adds a simplifying structure to the problem of planning worker assignments and order releases, which makes it more amenable to the use of optimization techniques. In this paper we exploit this characteristic and present two mathematical modeling approaches for making order dispatching and labor assignment/reassignment decisions in two different CM settings. The two formulations are evaluated in a dynamic simulation setting and compared to a heuristic procedure using tardiness as the primary performance measure. The formulations are superior to the heuristic approach and can be incorporated into detail scheduling systems that are being implemented by corporations employing enterprise resource planning (ERP) systems today.     

Alternate Routing Strategies in Batch Manufacturing: An Evaluation

Batch manufacturing firms are experiencing significant changes because of technological developments in work center design, such as flexible manufacturing systems (FMS) and planning/control tools like computer-aided process planning (CAPP). These new developments provide production managers with some solutions to a number of complex problems. For example, numerical-controlled (NC) machine center installations are effective in providing quality parts because of tight tolerance specifications built into the equipment. However, these highly efficient centers create bottlenecks that constrain shop throughput, since production planners tend to rely too much on them. To help improve manufacturing planning, we introduce an important element to the batch production scheduling component of CAPP's mission—evaluating possible alternate routes. Production scheduling encompasses job route selection as well as machine center assignment (loading), job releasing, and setting due dates. In this paper, three routing strategies requiring different levels of shop floor information are tested and evaluated using computer simulation. Shop performance is measured by total cost and traditional measures of job flow time, lateness, and tardiness.     

A mathematical model for job shop scheduling with multiple process plan consideration per job

In this paper, a mixed integer programming model is formulated for scheduling a set of jobs through a shop when each job is supplied or provided with multiple process plans or process routings. Simultaneous selection of a process plan for each job and the sequencing of the jobs through the machines in the shop based on the set of selected process plans is addressed. The procedure developed seeks to integrate the selection of machines for each job and the sequencing of jobs on each machine based on the objective of minimizing production makespan. the application of the procedure is demonstrated with an example problem. The following conclusions were drawn as a result of the research: (1) the procedure developed produces optimal or near optimal solution; (2) the benefit from the developed approach is that it allows a shop to adaptively select process plans for jobs to optimize on production makespan. By combining solution quality with scheduling flexibility and efficiency, the productivity of a shop can be greatly enhanced.