A knowledge-based approach to scheduling in an F.M.S.

This paper reports the development of a computer-based system for production scheduling in a dedicated FMS. The system is based on the state-operator framework commonly used in artificial intelligence. Such a system consists of three components: (i) a knowledge base of states, which describes both the current task domain situation and the goal to be achieved; (ii) a set of operators that are used to manipulate the knowledge base; and (iii) a control strategy to decide which operators to apply next and to resolve conflicts. Some of the interesting features of the scheduling system include: (i) the ability to detect resource conflicts; (ii) the ability to determine alternate routes for a given part in the event of a resource conflict; and (iii) the ability to amend plans if an alternate route is found. These features allow the system to take advantage of the flexible routing for parts that an FMS allows. The system has been implemented using the XLISP programming language. Implementation considerations are discussed. A small but comprehensive example is presented. Further research directions are suggested.     

A Petri net approach to the modelling and analysis of flexible manufacturing systems

In this paper we present an approach for modelling and analyzing flexible manufacturing systems (FMSs) using Petri nets. In this approach, we first build a Petri net model (PNM) of the given FMS in a bottom-up fashion and then analyze important qualitative aspects of FMS behaviour such as existence/absence of deadlocks and buffer overflows. The basis for our approach is a theorem we state and prove for computing the invariants of the union of a finite number of Petri nets when the invariants of the individual nets are known. We illustrate our approach using two typical manufacturing systems: an automated transfer line and a simple FMS.A shorter version of this paper was presented at the 1st ORSA/TIMS Special Interest Conference on FMSs, University of Michigan, Ann Arbor, August 1984.     

Experimental investigation of real-time scheduling in flexible manufacturing systems

This paper presents a new two-phase (TP) approximate method for real-time scheduling in a flexible manufacturing system (FMS). This method combines a reduced enumeration schedule generation algorithm with a 0–1 optimization algorithm. In order to make the combined algorithm practicable, heuristic rules are introduced for the selection of jobs to be scheduled. The relative performance of the TP method vis-a-vis conventional heuristic dispatching rules such as SPT, LPT, FCFS, MWKR, and LWKR is investigated using combined process-interaction/discrete-event simulation models. An efficient experimental procedure is designed and implemented using these models, and the statistical analysis of the results is presented. For the particular case investigated, the conclusions are very encouraging. In terms of mean flow time, the TP method performs significantly better than any other tested heuristic dispatching rules. Also, the experimental results show that using global information significantly improves the FMS performance.     

An evolutionary approach to rehabilitation patient scheduling: A case study

Focusing on real settings, this study aimed to develop an evolutionary approach based on genetic algorithm for solving the problem of rehabilitation patient scheduling to increase service quality by reducing patient waiting time and improve operation efficiency by increasing the therapy equipment utilization. Indeed, due to partial precedence constraints of rehabilitation therapies, the problem can be structured as a hybrid shop scheduling problem that has received little attention to date. In addition, a mixed integer programming model was also constructed as a benchmark to validate the solution quality with small problems. Based on empirical data from a Medical Center in Taiwan, several experiments were conducted to estimate the validity of the proposed algorithm. The results showed that the proposed algorithm can reduce patient waiting time and enhance resource utilization and thus demonstrated the practicality of the proposed algorithm. Indeed, a decision support system embedded with the developed algorithm has been implemented in this medical center.     

A combined branch-and-bound and genetic algorithm based approach for a flowshop scheduling problem

In this paper, we study the application of a meta-heuristic to a two-machine flowshop scheduling problem. The meta-heuristic uses a branch-and-bound procedure to generate some information, which in turn is used to guide a genetic algorithm's search for optimal and near-optimal solutions. The criteria considered are makespan and average job flowtime. The problem has applications in flowshop environments where management is interested in reducing turn-around and job idle times simultaneously. We develop the combined branch-and-bound and genetic algorithm based procedure and two modified versions of it. Their performance is compared with that of three algorithms: pure branch-and-bound, pure genetic algorithm, and a heuristic. The results indicate that the combined approach and its modified versions are better than either of the pure strategies as well as the heuristic algorithm.     

First-order hybrid Petri nets. An application to distributed manufacturing systems

In this paper we consider Hybrid Petri Nets (HPNs), a particular formalism that combines fluid and discrete event dynamics. We first provide a survey of the main HPN models that have been presented in the literature in the last decades. Then, we focus on a particular HPN model, namely the First-Order Hybrid Petri Net (FOHPN) model, whose continuous dynamics are piece-wise constant. Here the problem of designing an optimal controller simply requires solving on-line an appropriate linear integer programming problem. In this paper we show how FOHPNs can efficiently represent the concurrent activities of Distributed Manufacturing Systems (DMS), and some interesting optimization problems are also solved via numerical simulation.     

A multi-stage stochastic programming approach in master production scheduling

Master Production Schedules (MPS) are widely used in industry, especially within Enterprise Resource Planning (ERP) software. The classical approach for generating MPS assumes infinite capacity, fixed processing times, and a single scenario for demand forecasts. In this paper, we question these assumptions and consider a problem with finite capacity, controllable processing times, and several demand scenarios instead of just one. We use a multi-stage stochastic programming approach in order to come up with the maximum expected profit given the demand scenarios. Controllable processing times enlarge the solution space so that the limited capacity of production resources are utilized more effectively. We propose an effective formulation that enables an extensive computational study. Our computational results clearly indicate that instead of relying on relatively simple heuristic methods, multi-stage stochastic programming can be used effectively to solve MPS problems, and that controllability increases the performance of multi-stage solutions.     

A global MILP model for FMS scheduling

Flexible manufacturing systems (FMS) require intelligent scheduling strategies to achieve their principal benefit — combining high flexibility with high productivity. A mixed-integer linear programming model (MILP) is presented here for FMS scheduling. The model takes a global view of the problem and specifically takes into account constraints on storage and transportation. Both of these constrained resources are critical for practical FMS scheduling problems and are difficult to model. The MILP model is explained and justified and its complexity is discussed. Two heuristic procedures are developed, based on an analysis of the global MILP model. Computational results are presented comparing the performance of the different solution strategies. The development of iterative global heuristics based on mathematical programming formulations is advocated for a wide class of FMS scheduling problems.     

Cyclic multiple-robot scheduling with time-window constraints using a critical path approach

An automated production system is considered in which several robots are used for transporting parts between workstations following a given route in a carousel mode. The problem is to maximize the throughput rate. Extending previous works treating scheduling problems for a single robot, we consider a more realistic case in which workstations are served by multiple robots. A graph model of the production process is developed, making it possible to apply PERT–CPM solution techniques. The problem is proved to be solvable in polynomial time.     

A lexicographic approach to bi-objective scheduling of single-period orders in make-to-order manufacturing

This paper presents a lexicographic approach and integer programming formulations for a dual-objective, long-term production scheduling in make-to-order manufacturing environment. The problem objective is to assign single-period customer orders for various product types to planning periods to complete all the orders with minimum number of tardy orders as a primary criterion and to level the aggregate production or the total capacity utilization over a planning horizon as a secondary criterion. Each order must be completed during one planning period. The basic integer programming formulation has been strengthened by the addition of some cutting constraints derived by relating the demand on required capacity to available capacity for each subset of orders with the same due date. The approach has been applied to optimize production schedules in a flexible flowshop made up of several processing stages in series, with identical, parallel machines, and an output buffer of limited capacity for holding completed products before delivery to the customers. Numerical examples modeled after a real-world make-to-order flexible assembly line in the electronics industry are provided and some computational results are reported.     

A polynomial algorithm for no-wait cyclic hoist scheduling in an extended electroplating line

This paper addresses cyclic hoist scheduling in a no-wait electroplating line where a part visits some processing tanks more than once and multiple duplicate tanks are used at some production stages. We prove that such an extended problem can be solved in polynomial time.     

A comprehensive approach of planning and scheduling based on petri nets

The main results available on the use of black-and-white Petri nets for modelling, planning and scheduling manufacturing systems are presented. In the first part of the paper, the basics of Petri nets necessary to understand the subsequent presentation are introduced. Particular attention is paid to event graphs, a particular type of Petri nets used for modelling and evaluating ratio-driven systems. The second part of the paper is devoted to ratio-driven systems, their modelling and their scheduling. Job-shops, assembly systems, and KANBAN systems are used to illustrate this section. Finally, the general case is investigated of manufacturing systems subject to changing demands. An approach based on conflict-free Petri nets with input and output transitions is proposed for planning and scheduling this type of system.     

A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem

This paper presents a genetic algorithm for solving the resource-constrained project scheduling problem. The innovative component of the algorithm is the use of a magnet-based crossover operator that can preserve up to two contiguous parts from the receiver and one contiguous part from the donator genotype. For this purpose, a number of genes in the receiver genotype absorb one another to have the same order and contiguity they have in the donator genotype. The ability of maintaining up to three contiguous parts from two parents distinguishes this crossover operator from the powerful and famous two-point crossover operator, which can maintain only two contiguous parts, both from the same parent. Comparing the performance of the new procedure with that of other procedures indicates its effectiveness and competence.     

Preemptive scheduling with staircase and piecewise linear resource availability

Some variations are presented for the preemptive scheduling problem on unrelated processors, one shows how nonrenewable resources with a time-varying supply may be taken into account in an extension of the two-phase method; phase 1 consists in solving an LP problem and phase 2 is the construction of the schedule; such a construction reduces to the determination of integral vectors in polyhedra defined by totally unimodular matrices. In special cases, this is simply a compatible flow problem.

---

Zusammenfassung Es werden Variationen für Reihenfolgeprobleme mit Unterbrechungen betrachtet bei denen die Aufgaben mit unterschiedlicher Bearbeitungszeit auf den einzelnen Maschinen gelöst werden können. Insbesondere wird ein Problem mit nichterneuerbaren Resourcen und zeitabhängigen Nachfragen behandelt und es wird gezeigt, daß dieses Problem durch eine Erweiterung der 2-Phasenmethode gelöst werden kann. In Phase 1 wird ein LP gelöst, während in Phase 2 ein zugehöriger Schedule konstruiert wird. Diese Konstruktion erfolgt durch die Bestimmung ganzzahliger Vektoren, die Ecken eines Polyeders entsprechen, der durch eine vollständig unimodulare Matrix definiert wird. In Spezialfällen reduziert sich dies auf Flußprobleme.

     

Some open problems in the design and use of modern production systems

During the past two decades, manufacturing systems have moved towards automation, integration and modularity. These trends will certainly continue in the future due to the constraints of the market and to evolution of resources and worker requirements. As a consequence, the design and use of manufacturing systems are increasingly expensive. Numerous methods and tools have been developed to face up to this situation, but some complementary aids could be provided for designers and manufacturing engineers. The goal of this paper is to present important open problems whose solutions could certainly significantly improve the design and use of modern production systems.     

A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem

In this paper we present a genetic algorithm for the multi-mode resource-constrained project scheduling problem (MRCPSP), in which multiple execution modes are available for each of the activities of the project. We also introduce the preemptive extension of the problem which allows activity splitting (P-MRCPSP). To solve the problem, we apply a bi-population genetic algorithm, which makes use of two separate populations and extend the serial schedule generation scheme by introducing a mode improvement procedure. We evaluate the impact of preemption on the quality of the schedule and present detailed comparative computational results for the MRCPSP, which reveal that our procedure is amongst the most competitive algorithms.     

An integrated approach for scheduling health care activities in a hospital

To effectively utilise hospital beds, operating rooms (OR) and other treatment spaces, it is necessary to precisely plan patient admissions and treatments in advance. As patient treatment and recovery times are unequal and uncertain, this is not easy. In response, a sophisticated flexible job-shop scheduling (FJSS) model is introduced, whereby patients, beds, hospital wards and health care activities are respectively treated as jobs, single machines, parallel machines and operations. Our approach is novel because an entire hospital is describable and schedulable in one integrated approach. The scheduling model can be used to recompute timings after deviations, delays, postponements and cancellations. It also includes advanced conditions such as activity and machine setup times, transfer times between activities, blocking limitations and no wait conditions, timing and occupancy restrictions, buffering for robustness, fixed activities and sequences, release times and strict deadlines. To solve the FJSS problem, constructive algorithms and hybrid meta-heuristics have been developed. Our numerical testing shows that the proposed solution techniques are capable of solving problems of real world size. This outcome further highlights the value of the scheduling model and its potential for integration into actual hospital information systems.     

SimHPN: A MATLAB toolbox for simulation, analysis and design with hybrid Petri nets

This paper presents a MATLAB embedded package for hybrid Petri nets called SimHPN. It offers a collection of tools devoted to simulation, analysis and synthesis of dynamical systems modeled by hybrid Petri nets. The package supports several server semantics for the firing of both, discrete and continuous, types of transitions. Besides providing different simulation options, SimHPN offers the possibility of computing steady state throughput bounds for continuous nets. For such a class of nets, optimal control and observability algorithms are also implemented. The package is fully integrated in MATLAB which allows the creation of powerful algebraic, statistical and graphical instruments that exploit the routines available in MATLAB.     

Integrated scheduling and batch ordering for construction project

Multi-Mode Resource Constrained Project Scheduling Problem and material batch ordering for construction project are integrated to help project manager consider various trade-offs among several costs, such as renewable resources’ cost, material price, ordering cost, back-ordering cost, inventory holding cost and reward/penalty for early/late project completion. Therefore, we prove a mixed integer programming model and impel to calculate inventory holding cost and back order cost in objective function. Moreover, a hybrid algorithm combined adapted harmony search and genetic algorithm is proposed correspondingly. In order to inherit elitist solution and maintain population’s diversity simultaneously, we add a selection operator when the harmony memory is initialized and modify the replacement operator based on distance. Besides, genetic algorithm is adopted based on a ‘012’ coding scheme. Finally, algorithm and model performance is presented and several project instances are provided with different network structures and realizations to discuss the factors on total cost.     

Project scheduling problem with mixed uncertainty of randomness and fuzziness

Project scheduling problem is to determine the schedule of allocating resources so as to balance the total cost and the completion time. This paper considers project scheduling problem with mixed uncertainty of randomness and fuzziness, where activity duration times are assumed to be random fuzzy variables. Three types of random fuzzy models as expected cost minimization model, (α, β)-cost minimization model and chance maximization model are built to meet different management requirements. Random fuzzy simulations for some uncertain functions are given and embedded into genetic algorithm to design a hybrid intelligent algorithm. Finally, some numerical experiments are given for the sake of illustration of the effectiveness of the algorithm.