Scheduling vehicles in automated transportation systems Algorithms and case study

One of the major planning issues in large scale automated transportation systems is so-called empty vehicle management, the timely supply of vehicles to terminals in order to reduce cargo waiting times. Motivated by a Dutch pilot project on an underground cargo transportation system using Automated Guided Vehicles (AGVs), we developed several rules and algorithms for empty vehicle management, varying from trivial First-Come, First-Served (FCFS) via look-ahead rules to integral planning. For our application, we focus on attaining customer service levels in the presence of varying order priorities, taking into account resource capacities and the relation to other planning decisions, such as terminal management. We show how the various rules are embedded in a framework for logistics control of automated transportation networks. Using simulation, the planning options are evaluated on their performance in terms of customer service levels, AGV requirements and empty travel distances. Based on our experiments, we conclude that look-ahead rules have significant advantages above FCFS. A more advanced so-called serial scheduling method outperforms the look-ahead rules if the peak demand quickly moves amongst routes in the system. Received: June 21, 2000 / Accepted: January 22, 2001     

A-Design: An Agent-Based Approach to Conceptual Design in a Dynamic Environment

This paper provides an introduction to a new design methodology known as A-Design, which combines aspects of multi-objective optimization, multi-agent systems, and automated design synthesis. The A-Design theory is founded on the notion that engineering design occurs in interaction with an ever-changing environment, and therefore computer tools developed to aid in the design process should be adaptive to these changes. In this paper, A-Design is introduced along with some simple test problems to demonstrate the capabilities of different aspects of the theory. The theory of A-Design is then shown as the basis for a design tool that adaptively creates electro-mechanical configuration designs for changing user preferences.     

Coordination Approaches and Systems – Part II: An Operational Perspective

This is the second of two papers surveying research in coordination approaches and systems. This paper is concerned with operational coordination, which is aimed at coordinating activities such that the design process can be performed in a near optimal manner with respect to time, and the allocation and utilisation of resources. Aspects of coordination categorised as operational include resource management, scheduling and planning. The first of these two papers presents a review of coordination from a strategic perspective, which is concerned with the decision management aspects of coordination. Greater emphasis is now being placed on the significance of organising the design process as this affects time to market, product quality, cost, and consequently product success. The aim of this paper is to present a fundamental review of operational coordination approaches and systems. The 1990s has seen much progress being made towards a greater understanding and appreciation of coordination in various disciplines through the development of a wide range of approaches and systems. However, there remains a requirement to formally identify the key issues involved in coordination such that a widely accepted representation can be agreed upon. Consequently, research should continue to be supported in the exploration for a unified approach to coordination which will permit a broader and greater understanding of those aspects involved.     

A scheduling method for Berth and Quay cranes

This paper discusses a method for scheduling Berth and Quay cranes, which are critical resources in port container terminals. An integer programming model is formulated by considering various practical constraints. A two-phase solution procedure is suggested for solving the mathematical model. The first phase determines the Berthing position and time of each vessel as well as the number of cranes assigned to each vessel at each time segment. The subgradient optimization technique is applied to obtain a near-optimal solution of the first phase. In the second phase, a detailed schedule for each Quay crane is constructed based on the solution found from the first phase. The dynamic programming technique is applied to solve the problem of the second phase. A numerical experiment was conducted to test the performance of the suggested algorithms. RID="*" ID="*" This research has been supported in part by Brain Korea 21 Program (1999–2002). Correspondence to: Y.-M. Park     

Planning and scheduling in the process industry

Since there has been tremendous progress in planning and scheduling in the process industry during the last 20 years, it might be worthwhile to give an overview of the current state-of-the-art of planning and scheduling problems in the chemical process industry. This is the purpose of the current review which has the following structure: we start with some conceptional thoughts and some comments on special features of planning and scheduling problems in the process industry. In Section 2 the focus is on planning problems while in Section 3 different types of scheduling problems are discussed. Section 4 presents some solution approaches especially those applied to a benchmark problem which has received considerable interest during the last years. Section 5 allows a short view into the future of planning and scheduling. In the appendix we describe the Westenberger-Kallrath problem which has already been used extensively as a benchmark problem for planning and scheduling in the process industr y.     

A computational study of LP-based heuristic algorithms for two-dimensional guillotine cutting stock problems

In this paper we develop and compare several heuristic methods for solving the general two-dimensional cutting stock problem. We follow the Gilmore-Gomory column generation scheme in which at each iteration a new cutting pattern is obtained as the solution of a subproblem on one stock sheet. For solving this subproblem, in addition to classical dynamic programming, we have developed three heuristic procedures of increasing complexity, based on GRASP and Tabu Search techniques, producing solutions differing in quality and in time requirements. In order to obtain integer solutions from the fractional solutions of the Gilmore-Gomory process, we compare three rounding procedures, rounding up, truncated branch and bound and the solution of a residual problem. We have coded and tested all the combinations of algorithms and rounding procedures. The computational results obtained on a set of randomly generated test problems show their relative efficiency and allow the potential user to choose from among them, according to the available computing time. Rceived: January 9, 2001 / Accepted: December 10, 2001     

Truncated branch-and-bound,schedule-construction,and schedule-improvement procedures for resource-constrained project scheduling

We present heuristic procedures for approximately solving large project scheduling problems with general temporal and resource constraints. In particular, we propose several truncated branch-and-bound techniques, priority-rule methods, and schedule-improvement procedures of types tabu search and genetic algorithm. A detailed experimental performance analysis compares the different heuristics devised and shows that large problem instances with up to 1000 activities and several resources can efficiently be solved with sufficient accuracy.

---

---

Received: July 26, 2000 / Accepted: May 15, 2001     

Reduced outpatient waiting times with improved appointment scheduling: a simulation modelling approach

Abstract. An outpatient department represents a complex system through which many patients with varying needs pass each day. An effective appointment system is a critical component in controlling patient waiting times within clinic sessions. Current waiting times are often unacceptable and place great stress on clinic staff. This paper describes the development and use of a detailed simulation model of an Ear, Nose and Throat (ENT) outpatient department. The simulation allows various appointment schedules to be examined and their effects on the clinic evaluated. The model has been used to identify a number of critical factors that influence patient waiting times and the build up of queues in the clinic. Alternative appointment schedules have been shown to drastically reduce patient waiting times, without the need for extra resources, and enable the department to move towards meeting the UK Government's Patient's Charter. RID="*" ID="*" The authors would like to express their thanks for the valuable support provided by the anonymous participants (outpatient department staff). Thanks also to Helen Gilby, Dr Arjan Shahani and Professor Valter de Senna for their useful comments and help during the research. Correspondence to: P.R. Harper     

Numerical Modeling of a Post & Dome Snap-Fit Feature

Snap-fits are often designed using guides that rely on classic beam theory, with the basic assumption that the beam undergoes small rotations and displacements. This is a poor assumption, for they typically experience both large rotations and displacements due to loading offset from the neutral axis and axial loading. This paper investigates the performance of the post & dome feature, establishes its nomenclature, and derives the equations needed to intelligently design different variations of it. The post & dome feature was selected for analysis because it is a high performance snap-fit that is self-datuming and can withstand some shear loading in addition to retention. The design equations were generated in three steps. First, an experimental array was created using a design of experiments approach. Finite element methods and multiple regression techniques were used in lieu of beam equations models for each of the trials in the experimental array. Finally, response surface methods were used to develop response curves based on the performance data generated by the finite element models. Sensitivity data was plotted for both the main effects and selected variable interactions. The traditional benchmarks for defining high performance snap-fits are retention strength, insertion force, and insertion strain. This paper uses an expanded definition of these benchmarks that also includes locking ratio (the ratio of retention force to insertion force).     

Lot-sizing for a single-stage single-product production system with rework of perishable production defectives

We consider a single-stage single-product production system. Produced units may be non-defective, reworkable defective, or non-reworkable defective. The system switches between production and rework. After producing a fixed number (N) of units, all reworkable defective units are reworked. Reworkable defectives are perishable or can become technologically obsolete. We assume that the rework time and the rework cost increase linearly with the time that a unit is held in stock. Therefore, N should not be too large. On the other hand, N should not be too small either, since there are set-up times and costs associated with switching between production and rework. For a given N, we derive an explicit expression for the average profit (sales revenue minus costs). Using this expression, the optimal value for N can be determined numerically. Moreover, it is easy to perform a sensitivity analysis, as we illustrate. RID="*" ID="*"The research of Dr. Ruud H. Teunter has been made possible by a fellowship of the Royal Netherlands Academy of Arts and Sciences. The research presented in this paper is part of the research on re-use in the context of the EU sponsored TMR project REVersed LOGistics (ERB 4061 PL 97-5650) in which take part the Otto-von-Guericke Universitaet Magdeburg (D), the Erasmus University Rotterdam (NL), the Eindhoven University of Technology (NL), INSEAD (F), the Aristoteles University of Thessaloniki (GR), and the University of Piraeus (GR). We thank the anonymous referees for their many helpful comments. Correspondence to: R. H. Teunter     

Intensity-modulated radiotherapy – a large scale multi-criteria programming problem

Abstract. Radiation therapy planning is often a tight rope walk between dangerous insufficient dose in the target volume and life threatening overdosing of organs at risk. Finding ideal balances between these inherently contradictory goals challenges dosimetrists and physicians in their daily practice. Todays inverse planning systems calculate treatment plans based on a single evaluation function that measures the quality of a radiation treatment plan. Unfortunately, such a one dimensional approach cannot satisfactorily map the different backgrounds of physicians and the patient dependent necessities. So, too often a time consuming iterative optimization process between evaluation of the dose distribution and redefinition of the evaluation function is needed. In this paper we propose a generic multi-criteria approach based on Pareto's solution concept. For each entity of interest – target volume or organ at risk – a structure dependent evaluation function is defined measuring deviations from ideal doses that are calculated from statistical functions. A reasonable bunch of clinically meaningful Pareto optimal solutions are stored in a data base, which can be interactively searched by physicians. The system guarantees dynamic planning as well as the discussion of tradeoffs between different entities. Mathematically, we model the inverse problem as a multi-criteria linear programming problem. Because of the large scale nature of the problem it is not possible to solve the problem in a 3D-setting without adaptive reduction by appropriate approximation schemes. Our approach is twofold: First, the discretization of the continuous problem results from an adaptive hierarchical clustering process which is used for a local refinement of constraints during the optimization procedure. Second, the set of Pareto optimal solutions is approximated by an adaptive grid of representatives that are found by a hybrid process of calculating extreme compromises and interpolation methods. Correspondence to: K.-H. Küfer     

Performance analysis of parallel identical machines with a generalized shortest queue arrival mechanism

In this paper we study a production system consisting of a group of parallel machines producing multiple job types. Each machine has its own queue and it can process a restricted set of job types only. On arrival a job joins the shortest queue among all queues capable of serving that job. Under the assumption of Poisson arrivals and identical exponential processing times we derive upper and lower bounds for the mean waiting time. These bounds are obtained from so-called flexible bound models, and they provide a powerful tool to efficiently determine the mean waiting time. The bounds are used to study how the mean waiting time depends on the amount of overlap (i.e. common job types) between the machines.

---

---

Received: February 8, 2000 / Accepted: November 28, 2000     

On the steady state of the replicating portfolio: accounting for a growth rate

For the risk management and transfer pricing of non-maturity liabilities, banks in Europe often use a so-called replicating portfolio technique. A commonly used implementation is replication of a fixed investment rule every time period. This paper deals with the development of the portfolio in the long run, when using this methodology. Applying this replicating portfolio technique yields, after a while, a steady state. Besides the straightforward result when volume is constant, we solve the steady states for the case where the funds (volume) grow with a fixed rate (e.g. due to credited interest or growth in GDP). We therefore define a system growth process, alternative to the Markov process (when volume is constant). From a transfer pricing and risk-management point of view, the resulting portfolio should satisfy certain requirements concerning return and flexibility. Once the steady state can be calculated for given growth rates, the investment policy can be specified. The importance of taking account of a growth rate is illustrated. Growth in volume implies that a different rule will converge to the desired steady state. This is illustrated analytically and with numerical examples. The purpose of the paper is not to find the ideal hedge strategy for non-maturity liabilities, but to improve the existing risk management without any implementation costs for the banks. Given the currently used methodology, accounting for a growth rate can significantly improve the risk management of non-maturity liabilities. RID="*" ID="*" I thank Anja De Waegenaere, Peter Kort and an anonymous referee for useful comments on an earlier draft.     

Meta-heuristic based decision support for portfolio optimization with a case study on tracking error minimization in passive portfolio management

In this paper we describe the concept and design of a meta-heuristic based decision support system generator (DSS-generator) for portfolio optimization. We report extensively on experience with the application of a specific DSS that has been customized for controlling and optimizing passively managed stock funds. Here, the constraints from the law on investment trust companies as well as several fund specific guidelines prohibit that the benchmark can be identically reproduced. For measuring the performance of the portfolio a tracking error model with data stemming from a factor model is applied. Our results show that the system provides proposals for the fund manager in acceptable time which are feasible with respect to the guidelines and excellent in quality.     

Analysis of a single stage production system with heterogeneous machines

The performance of a single stage production system with two heterogeneous machines and two classes of jobs is investigated. The machines have a common buffer with jobs of both classes waiting for service. The arrivals are assumed to follow a Poisson process and the service times to be distributed exponentially. The evaluated production system differs from a classical homogeneous multiple server queueing system with regard to inhomogeneities of the two machines. Time inhomogeneity – the service times of the two machines being unequal – and functional inhomogeneity – one of the machines can handle only one class (A) of jobs – are to be distinguished. In the case of time inhomogeneity the calculation of system performance parameters may be carried out using an explicit formula, whereas for the analysis of functional inhomogeneity a numerical solution has to be derived. The impact of time inhomogeneity is very small and decreases with the system workload. On the contrary, functional inhomogeneity leads to elevated cycle times of up to 40% depending on the degree of inhomogeneity (measured by the fraction of A jobs) and the workload. Therefore, in contrast to the time-inhomogeneous case, single stage production systems with functional inhomogeneity can only be approximated tolerably by a homogeneous multiple server queueing system if the fraction of one-machine jobs is less than 30%. The increased throughput times above 30% are supplied by the diagram developed from the numerical solutions. RID="*" ID="*" While this research was constructed the author was affiliated to Institute of Conveying Technology and Logistics. Correspondence to: C. R. Lippolt     

A Taxonomy for Design Requirements from Corporate Customers

We have developed a taxonomy that classifies those needs of a corporation that impact product design. We call these needs corporate requirements. In contrast to the consumer or end-user requirements, corporate requirements come from internal sources such as marketing, finance, manufacturing, and service. This taxonomy allows for an organized method of gathering, managing, and retrieving the requirements. The taxonomy also helps to facilitate a broader, clearer form of Quality Function Deployment. Generic in nature, this taxonomy provides a template with which to create taxonomies for a given product within a given company or industry. We include an industrial case study to demonstrate this concept.     

A Study on Engineering History Base

During engineering processes, many kinds and amounts of information are used and produced. Such information is useful in successive cases, and thus its reuse is desired. In this paper, information on attributes of the products is referred to as ‘product information’, and information on the reasons for and/or history of a designer’s thought process is referred to as ‘process information’. According to this classification, process information can be used for obtaining an explanation of product information. The purpose of this work is to build a database, called an ‘engineering history base’, from which engineers can retrieve explanations to enable the reuse of product information. In this paper, explanation from the ‘process’ viewpoint is thought to be important in promoting the reuse of product information. There are two types of explanation for the process: teleological and causal. However, until now, little attention has been paid to the causal explanation for the process. Thus, in this paper, an information model which focuses on both types of explanation is proposed. The model is adopted for the engineering history base and a prototype system is developed. The appropriateness of this model is discussed by analyzing the actual data in the development of a color video printer.     

Resource allocation for HIV/AIDS control programs: a model-based policy analysis

The World Health Organization reported that in 1996, for the first time in the course of the AIDS epidemic, there had been a marked decrease in deaths among people with AIDS in many industrialized countries due to the administration of advanced drug therapies and the performance of prevention programs. In response to such changes, policy makers can use our strategic decision support system to determine cost-effective prevention programs. We illustrate the model by analyzing the administration of advanced drug therapies combined with different assumptions for the behavior of the population of Vienna. We estimate that the city of Vienna will have to provide at most 5.6 billion Austrian Schillings for drug therapies, additional treatment, and HIV screening during the period from 1996 to 2005, depending on whether or not these more costly drug therapies reduce the additional treatment costs of HIV-infected and AIDS-diseased individuals. Received: June 12, 2000 / Accepted: August 31, 2001     

Influences on Solution Search Processes in Design Organisations

A study was conducted of what influenced solution search activity in three design organisations. The influences were analysed in terms of how they affected search, whether their effect tended to be conservative or innovative, and the directness of the evidence they provided. Overall, the environment was found to provide more innovative influences than conservative ones. Innovative influences were mostly connected with the triggering of search activity, while conservative influences were mostly linked with restricting the search space of potential solutions. Also, search candidates were often evaluated in terms of their associations rather than their intrinsic merits, and ultimately this makes human judgment an essential component of search and evaluation activity. Finally, the environment provides many ‘seeds’ for effects like design fixation and functional fixedness but also provides strong incentives to positively avoid these effects.