Experimental investigation of an FMS due-date scheduling problem: Evaluation of machine and AGV scheduling rules

Although extensive research has been conducted to solve design and operational problems of automated manufacturing systems, many of the problems still remain unsolved. This article investigates the scheduling problems of flexible manufacturing systems (FMSs). Specifically, the relative performances of machine and automated guided vehicle (AGV) scheduling rules are analyzed against various due-date criteria. First, the relevant literature is briefly reviewed, and then the rules are tested under different experimental conditions by using a simulation model of an FMS. The sensitivity to AGV workload, buffer capacity, and processing-time distribution is also investigated to assess the robustness of the scheduling rules.     

Multiple-Objective Scheduling for the Hierarchical Control of Flexible Manufacturing Systems

This paper presents a hierarchical approach to scheduling flexible manufacturing systems (FMSs) that pursues multiple performance objectives and considers the process flexibility of incorporating alternative process plans and resources for the required operations. The scheduling problem is solved at two levels: the shop level and the manufacturing system level. The shop level controller employs a combined priority index developed in this research to rank shop production orders in meeting multiple scheduling objectives. To overcome dimensional complexity and keep a low level of work-in-process inventory, the shop controller first selects up to three production orders with the highest ranking as candidates and generates all possible release sequences for them, with or without multitasking. These sequences are conveyed to the manufacturing system controller, who then performs detailed scheduling of the machines in the FMS using a fixed priority heuristic for routing parts of multiple types while considering alternative process plans and resources for the operations. The FMS controller provides feedback to the shop controller with a set of suggested detailed schedules and projected order completion times. On receiving these results, the shop controller further evaluates each candidate schedule using a multiple-objective function and selects the best schedule for execution. This allows multiple performance objectives of an FMS to be achieved by the integrated hierarchical scheduling approach.     

Scheduling parallel machines with major and minor setup times

This article discusses the problem of scheduling a large set of parts on an FMS so as to minimize the total completion time. Here, the FMS consists of a set of parallel identical machines. Setup time is incurred whenever a machine switches from one type of part to another. The setup time may be large or small depending on whether or not the two part types belong to the same family. This article describes a fast heuristic for this scheduling problem and derives a lower bound on the optimal solution. In computational tests using random data and data from an IBM card test line, the heuristic archieves nearly optimal schedules.     

An efficient heuristic for scheduling batches of parts in a flexible flow system

Flexible manufacturing systems (FMSs) are a class of automated systems that can be used to improve productivity in batch manufacturing. Four stages of decision making have been defined for an FMS—the design, planning, scheduling, and control stages. This research focuses on the planning stage, and specifically in the area of scheduling batches of parts through the system. The literature to date on the FMS planning stage has mostly focused on the machine grouping, tool loading, and parttype selection problems. Our research carries the literature a step further by addressing the problem of scheduling batches of parts. Due to the use of serial-access material-handling systems in many FMSs, the batch-scheduling problem is modeled for a flexible flow system (FFS). This model explicitly accounts for setup times between batches that are dependent on their processing sequence. A heuristic procedure is developed for this batch-scheduling problem—the Maximum Savings (MS) heuristic. The MS heuristic is based upon the savings in time associated with a particular sequence and selecting the one with the maximum savings. It uses a two-phase method, with the savings being calculated in phase I, while a branch-and-bound procedure is employed to seek the best heuristic solution in phase II. Extensive computational results are provided for a wide variety of problems. The results show that the MS heuristic provides good-quality solutions.     

Hybrid FMS control architectures based on holonic principles

The escalation in processor technologies and the corresponding reduction in costs have enabled alternative FMS control architectures to be developed without the restrictions of “fixed machine controller boundaries”. These new architectures can be based upon the use of intelligent servo axes, which are desccribed in this article, as flexible numerical control (FNC). In current parlance, the FNC is a “part movement holon” within a manufacturing cell. The control architectures that can be derived from the FNC concept are referred to as hybrid architectures and share the emerging attributes of holonics. This article details the problems that arise in the scheduling and control of FMSs in the light of hybrid control architectures. A number of traditional scheduling approaches have been devised to cope with the scheduling of parts to discrete machines, but the problem here is to ascribe the processing (machining) of part features to axis groups. This article documents how two research programs, undertaken at the CIM Centre at Swinburne University of Technology in Hawthorn, Victoria, Australia, have endeavored to address the problem of hybrid architectures and their associated scheduling.     

A comparative study of FMS tool allocation and part type selection approaches for a varying part type mix

Hankins and Rovito (1984) examined the impact of different tool policies on cutting tool inventory levels and spindle utilization for a flexible manufacturing system (FMS). This study provides a broader perspective of the impact of tool allocation approaches on flow times, tardiness, percent of orders tardy, machine utilization, and robot utilization. Part type selection procedures have been suggested for the FMS prerelease planning problem. However, very little research has specifically evaluated the part type selection procedures across different tool allocation approaches. Also, with the exception of Stecke and Kim (1988, 1991) no other known study has provided any insights on what tool allocation approaches are appropriate when processing different mixes of part types. This research is devoted to addressing those issues. Three tool allocation approaches, three production scheduling rules, and three levels of part mix are evaluated in this study through a similation model of a flexible manufacturing system. The specific impacts of the tool approaches, their interaction effects with the part type selection rules, and their effectiveness at different part type mix levels are provided through the use of a regression metamodel.     

Production planning of a flexible manufacturing system in a material requirements planning environment

Early flexible manufacturing system (FMS) production planning models exhibited a variety of planning objectives; typically, these objectives were independent of the overall production environment. More recently, some researchers have proposed hierarchical production planning and scheduling models for FMS. In this article, we examine production planning of FMS in a material requirements planning (MRP) environment. We propose a hierarchical structure that integrates FMS production planning into a closed-loop MRP system. This structure gives rise to the FMS/MRP rough-cut capacity planning (FMRCP) problem, the FMS/MRP grouping and loading (FMGL) problem, and the FMS/MRP detailed scheduling problem. We examine the FMRCP and FMGL problems in detail and present mathematical programming models for each of these problems. In particular, the FMRCP problem is modeled as a generalized assignment problem (GAP), and a GAP-based heuristic procedure is defined for the problem. We define a two-phase heuristic for the FMGL problem and present computational experience with both heuristics. The FMRCP heuristic is shown to solve problems that exhibit a dependent-demand relation within the FMS and with FMS capacity utilization as high as 99 percent. The FMGL heuristic requires very little CPU time and obtains solutions to the test problems that are on average within 1.5 percent of a theoretical lower bound. This FMS/MRP production planning framework, together with the resulting models, constitutes an important step in the integration of FMS technology with MRP production planning. The hierarchical planning mechanism directly provides for system-level MRP planning priorities to induce appropriate production planning and control objectives on the FMS while simultaneously allowing for necessary feedback from the FMS. Moreover, by demonstrating the tractability of the FMRCP and FMGL problems, this research establishes the necessary groundwork upon which to explore systemwide issues pertaining to the coordination of the hierarchical structure.     

Dynamic flexibility metrics for capability and capacity

In production environments, such as Flexible Manufacturing Systems (FMSs), the schedule can be disturbed by the occurrence of unplanned events. Machines stop for major failures, maintenance, tool changes due to wear, or tool reassignments. The rescheduling process, however, can be costly. In this study, a dynamic measure of flexibility which helps to determine an appropriate time for rescheduling an FMS has been defined and investigated. Flexibility is defined as a function of Capability and Capacity. Accordingly, two metrics have been developed to monitor the capability and capacity efficiency of each machine in the system for responding to the dynamic system status. The value of each metric falls between 0 and 1 at all times. Higher values in the capability metric mean better machine selection and part distribution strategies among the machines. Higher values for the capacity metric mean higher machine utilization in the production plan. Based on the interaction between the metrics and their respective behavior in the system, four states have been identified and characterized. Simulations of various scenarios can be used to demonstrate the use of these metrics for monitoring FMS operations and determining appropriate times for rescheduling and tool reassignment.     

Dissimilarity Maximization Method for Real-time Routing of Parts in Random Flexible Manufacturing Systems

This paper presents a dissimilarity maximization method (DMM) for real-time routing selection and compares it via simulation with typical priority rules commonly used in scheduling and control of flexible manufacturing systems (FMSs). DMM aims to reduce the congestion in the system by selecting a routing for each part among its alternative routings such that the overall dissimilarity among the selected routings is maximized. In order to evaluate the performance of DMM, a random FMS, where the product mix is not known prior to production and off-line scheduling is not possible, is selected for the simulation study. A software environment that consists of a computer simulation model, which mimics a physical system, a C++ module, and a linear program solver is used to implement the DMM concept. In addition to DMM, the simulation study uses two priority rules for routing (i.e., machine) selection and seven priority rules for selecting parts awaiting service at machine buffers. The results show (1) DMM outperforms the other two routing selection rules on production rate regardless of the part selection rule used, and (2) its performance is highly dependent on the part selection rules it is combined with.     

Enriching the tactical network design of express service carriers with fleet scheduling characteristics

Express service carriers provide time-guaranteed deliveries of parcels via a network consisting of nodes and hubs. In this, nodes take care of the collection and delivery of parcels, and hubs have the function to consolidate parcels in between the nodes. The tactical network design problem assigns nodes to hubs, determines arcs between hubs, and routes parcels through the network. Afterwards, fleet scheduling creates a schedule for vehicles operated in the network. The strong relation between flow routing and fleet scheduling makes it difficult to optimise the network cost. Due to this complexity, fleet scheduling and network design are usually decoupled. We propose a new tactical network design model that is able to include fleet scheduling characteristics (like vehicle capacities, vehicle balancing, and drivers’ legislations) in the network design. The model is tested on benchmark data based on instances from an express provider, resulting in significant cost reductions.     

Effectiveness of flexible routing control

Flexibility in part process representation and in highly adaptive routing algorithms are two major sources for improvement in the control of flexible manufacturing systems (FMSs). This article reports the investigation of the impact of these two kinds of flexibilities on the performance of the system. We argue that, when feasible, the choices of operations and sequencing of the part process plans should be deferred until detailed knowledge about the real-time factory state is available. To test our ideas, a flexible routing control simulation system (FRCS) was constructed and a programming language for modeling FMS part process plans, control strategies, and environments of the FMS was designed and implemented. In addition, a scheme for implementing flexible process routing called data flow dispatching rule (DFDR) was derived. The simulation results indicate that flexible processing can reduce mean flow time while increasing system throughput and machine utilization. We observed that this form of flexibility makes automatic load balancing of the machines possible. On the other hand, it also makes the control and scheduling process more complicated and calls for new control algorithms.     

A DSS for job scheduling under process interruptions

The primary objective of this research is to solve the job-shop scheduling problems (JSSPs), by minimizing the makespan, with and without process interruptions. In this paper, we first developed a genetic algorithm for solving JSSPs, and then improved the algorithm by integrating it with two simple priority rules and a hybrid rule. The performance of the developed algorithm was tested by solving 40 benchmark problems and comparing their results with that of a number of well-known algorithms. In addition, we have studied the job-shop scheduling under process interruptions such as machine unavailability and breakdown. For convenience of implementation, we have developed a decision support system (DSS). In the DSS, we built a graphical user interface for user friendly data inputs, model choices, and output generation. An overview of the DSS and an analysis of the experimental results are provided. The incorporation of priority rules, and a hybrid rule, not only improves the solutions but also reduces the overall computational time. The experimental results show that when the machine unavailability information is known in advance, the effect on the schedule is very little compared to the sudden machine breakdown scenario.     

Work flow control in the flexible flow line

This research involves the development and evaluation of a part flow control model for a type of flexible manufacturing system (FMS) called a dedicated flexible flow line (FFL). In the FFL, all part types flow along the same path between successive machine groups. The specific objective of the part flow control model for the FFL is to minimize makespan for a given set of parts produced in a FFL near-term schedule, given fixed available buffer constraints. The control model developed in this research involved the repeated, real-time execution of a mathematical programming algorithm. The algorithm attempts to release the right mix of parts at the tight time to keep the FFL operating smoothly. The focus of the approach is directed toward managing WIP buffers for each machine group queue. The algorithm specifically incorporates stochastic disturbance factors such as machine failures. Through a limited number of simulation experiments, performance of the control model is shown to be superior to other parts releasing and control methods reported in the literature.     

Algorithms for efficient planning and operation of a particular FMS

This article is a detailed case study of a particular FMS that will be operational in 1989. It describes the daily planning and operating problems that will need to be addressed. The algorithms that will operate this system are presented. Given the daily changing production requirements, the algorithms begin with an aggregate planning feasibility check. Then planning, scheduling, inventory management, and breakdowns are addressed. The key problems in operating this system are tool management problems. Detailed tooling data and their analysis are presented in an appendix to address these problems.     

Intelligent scheduling of FMSs with inductive learning capability using neural networks

With the growing uncertainty and complexity in the manufacturing environment, most scheduling problems have been proven to be NP-complete and this can degrade the performance of conventional operations research (OR) techniques. This article presents a system-attribute-oriented knowledge-based scheduling system (SAOSS) with inductive learning capability. With the rich heritage from artificial intelligence (AI), SAOSS takes a multialgorithm paradigm which makes it more intelligent, flexible, and suitable than others for tackling complicated, dynamic scheduling problems. SAOSS employs an efficient and effective inductive learning method, a continuous iterative dichotomister 3 (CID3) algorithm, to induce decision rules for scheduling by converting corresponding decision trees into hidden layers of a self-generated neural network. Connection weights between hidden units imply the scheduling heuristics, which are then formulated into scheduling rules. An FMS scheduling problem is also given for illustration. The scheduling results show that the system-attribute-oriented knowledge-based approach is capable of addressing dynamic scheduling problems.     

Aproximating static list schedules in dynamic multithreaded applications

List scheduling algorithms are known to be efficient when the application to be executed can be described statically as a Directed Acyclic Graph (DAG) of tasks. Regardless of knowing the entire DAG beforehand, obtaining an optimal schedule in a parallel machine is a NP-hard problem. Moreover, many programming tools propose the use of scheduling techniques based on list strategies. This paper presents an analysis of scheduling algorithms for multithread programs in a dynamic scenario where threads are created and destroyed during execution. We introduce an algorithm to convert DAGs, describing applications as tasks, into Directed Cyclic Graphs (DCGs) describing the same application designed in a multithread programming interface. Our algorithm covers case studies described in previous works, successfully mapping from the abstract level of graphs to the application environment. These mappings preserve the guarantees offered by the abstract model, providing efficient scheduling of dynamic programs that follow the intended multithread model. We conclude the paper presenting some performance results we obtained by list schedulers in dynamic multithreaded environments. We also compare these results with the best scheduling we could obtain with similar static task schedulers.     

Impact of Interruptions on Schedule Execution in Flexible Manufacturing Systems

Finite capacity scheduling software packages provide a detailed advance plan of production events. However, the execution of this advance plan is disrupted by a myriad of unanticipated interruptions, such as machine breakdowns, yield variations, and hot jobs. The alternatives available to respond to such interruptions include modifying the existing schedule, regenerating the complete schedule, or doing nothing and letting the production system gradually absorb the impact of the interruption. This article reports on a simulation study aimed at understanding the impact of an interruption on a schedule in order to build a knowledge base for intelligent selection of a response from a set of alternatives. The results of the experimental study are used to identify significant major factors and their interactions. The results are discussed to draw insights into the performance of a flexible manufacturing system following an interruption. The causes leading to particular performance anomalies are extensively discussed and mechanisms for propagation and absorption of the effect of interruptions in manufacturing systems are inferred. Practical implications for the development and implementation of schedules are deduced and areas for further research proposed. This study provides the groundwork necessary to proceed with the development of strategies for responding to interruptions.     

Scheduling data analytics work with performance guarantees: queuing and machine learning models in synergy

In today’s scaled out systems, co-scheduling data analytics work with high priority user workloads is common as it utilizes better the vast hardware availability. User workloads are dominated by periodic patterns, with alternating periods of high and low utilization, creating promising conditions to schedule data analytics work during low activity periods. To this end, we show the effectiveness of machine learning models in accurately predicting user workload intensities, essentially by suggesting the most opportune time to co-schedule data analytics work. Yet, machine learning models cannot predict the effects of performance interference when co-scheduling is employed, as this constitutes a “new” observation. Specifically, in tiered storage systems, their hierarchical design makes performance interference even more complex, thus accurate performance prediction is more challenging. Here, we quantify the unknown performance effects of workload co-scheduling by enhancing machine learning models with queuing theory ones to develop a hybrid approach that can accurately predict performance and guide scheduling decisions in a tiered storage system. Using traces from commercial systems we illustrate that queuing theory and machine learning models can be used in synergy to surpass their respective weaknesses and deliver robust co-scheduling solutions that achieve high performance.     

Genetic Algorithm Based Scheduling of Meta-Tasks with Stochastic Execution Times in Heterogeneous Computing Systemst1

In this study, we address the meta-task scheduling problem in heterogeneous computing (HC) systems, which is to find a task assignment that minimizes the schedule length of a meta-task composed of several independent tasks with no data dependencies. The fact that the meta-task scheduling problem in HC systems is NP-hard has motivated the development of many heuristic scheduling algorithms. These heuristic algorithms, however, neglect the stochastic nature of task execution times in an attempt to minimize a deterministic objective function, which is the maximum of the expected values of machine loads. Contrary to existing heuristics, we account for this stochastic nature by modeling task execution times as random variables. We, then, formulate a stochastic scheduling problem where the objective is to minimize the expected value of the maximum of machine loads. We prove that this new objective is underestimated by the deterministic objective function and that an optimal task assignment obtained with respect to the deterministic objective function could be inefficient in a real computing platform. In order to solve the stochastic scheduling problem posed, we develop a genetic algorithm based scheduling heuristic. Our extensive simulation studies show that the proposed genetic algorithm can produce better task assignments as compared to existing heuristics. Specifically, we observe a performance improvement on the relative cost heuristic (M.-Y. Wu and W. Shu, A high-performance mapping algorithm for heterogeneous computing systems, in: Int. Parallel and Distributed Processing Symposium, San Francisco, CA, April 2001) by up to 61%.