Optimisation of beam directions in intensity modulated radiation therapy planning

Abstract. In this paper we consider the problem of selecting optimal beam directions as well as optimal intensity profiles for radiation therapy. Our multiobjective mixed integer programming problem is based on and extends a multiobjective LP formulation for intensity optimisation by Hamacher and Küfer. We use a weighted sum scalarisation to explore the benefits of beam direction optimisation. We propose exact and heuristic methods for solving the problem and present some numerical results. Correspondence to: M. Ehrgott     

Strategic technology investment under uncertainty

In this paper the technology investment decision of a firm is analyzed, while competition on the output market is explicitly taken into account. Technology choice is irreversible and the firms face a stochastic innovation process with uncertainty about the speed of arrival of new technologies. The innovation process is exogenous to the firms. For reasons of market saturation and the fact that more modern technologies are invented as time passes, the demand for a given technology decreases over time. This implies that also the sunk cost investment of each technology decreases over time. The investment decision problem is transformed into a timing game, in which the waiting curve is introduced as a new concopt. An algorithm is designed for solving this (more) general timing game. The algorithm is applied to an information technology investment problem. The most likely outcome exhibits diffusion with equfal payoffs for the firms. Received: December 16, 1999 / Accepted: February 7, 2001     

The resource renting problem subject to temporal constraints

We introduce a project scheduling problem subject to temporal constraints where the resource availability costs have to be minimized. As an extension of known project scheduling problems which consider only time-independent costs, this problem includes both time-independent procurement costs and time-dependent renting costs for the resources. Consequently, in addition to projects where all resources are bought, we can deal with projects where resources are rented. Based on the enumeration of a finite set of schedules which is proved to contain an optimal schedule, we develop a depth-first branch-and-bound procedure. Computational experience with a randomly generated test set containing 10800 problem instances is reported.

---

---

Received: December 1, 1999 / Accepted: November 8, 2000     

External Support of Problem Analysis in Design Problem Solving

Design is described as creative design problem solving. The first step of the design process is to identify and analyze the design problem. This step has an important influence on the creation of an effective design solution. In two experiments, we tested the benefits that sketching provides during the analysis process in design problem solving. In particular, this paper focuses on the design process, the act of sketching, the sketch itself, and the final product. In prior studies, the process of sketching has been shown to enhance the construction of a mental representation, and thus the sketch has improved the analysis of the problem. The memory supporting effect of sketches is verified in the second experiment discussed in this paper. Finally, this paper also discusses the support possibilities the sketch offers for the early stages of the design process.     

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     

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     

A bottleneck assignment approach to the multiple container loading problem

The container loading problem addresses the question of how to store several three dimensional, rectangular items (e.g. boxes) in one or more containers in such a way that maximum use is made of the container space. The multiple container problem concentrates on the situation where the consignment to be loaded cannot be accommodated in a single container. To minimize the number of required containers the repeated application of a single container approach is often suggested in the literature. In contrast, in this paper an approach based on a set partitioning formulation of the problem is presented. Within this approach a single container algorithm is used to produce alternative loading patterns. This approach easily allows introducing additional aspects, e.g. separation of boxes or complete shipment of boxes.     

Computing the Information Content of Decoupled Designs

The information content of uncoupled designs can be computed by summing the information content associated with each functional requirement. This paper proves that information cannot be summed for decoupled designs. To overcome this problem, this paper presents two algorithms for computing information content of decoupled designs. One algorithm is applicable to any joint probability density function for the design parameters; the second algorithm applies only to uniformly distributed design parameters. The algorithm for uniform distributions is based on a recursive procedure for computing the volume of a convex polytope in n -dimensional real space, where n is the number of design parameters. An engineering application of the algorithms is presented. The example demonstrates that summing information content can significantly over-estimate total information when compared to an algorithm that accounts for correlation. The example also demonstrates that decoupled designs can have lower information content than uncoupled systems with the same functional requirements and similar components.     

An integrated system solution for supply chain optimization in the chemical process industry

This paper considers a complex scheduling problem in the chemical process industry involving batch production. The application described comprises a network of production plants with interdependent production schedules, multi-stage production at multi-purpose facilities, and chain production. The paper addresses three distinct aspects: (i) a scheduling solution obtained from a genetic algorithm based optimizer, (ii) a mechanism for collaborative planning among the involved plants, and (iii) a tool for manual updates and schedule changes. The tailor made optimization algorithm simultaneously considers alternative production paths and facility selection as well as product and resource specific parameters such as batch sizes, and setup and cleanup times. The collaborative planning concept allows all the plants to work simultaneously as partners in a supply chain resulting in higher transparency, greater flexibility, and reduced response time as a whole. The user interface supports monitoring production schedules graphically and provides custom-built utilities for manual changes to the production schedule, investigation of various what-if scenarios, and marketing queries. RID="*" ID="*" The authors would like to thank Hans-Otto Günther and Roland Heilmann for helpful comments on draft versions of this paper.     

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.     

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     

Modeling returns of merchandise in an inventory system

Returns of merchandise occur commonly in the retail and rental businesses. This paper presents a new continuous review (s, S) inventory system with returns. The system is fairly complicated as its performance is a function of important factors such as demand rate, return time, return rate and replenishment frequency. Based on a Markovian approach, we derive essential operating characteristics of the system, and propose an algorithm to search for the optimal replenishment parameters. The results enable us to obtain valuable insights into the rental system, such as the impact of partial returns. Received: 12 November 1996 / Accepted: 18 December 1997     

A survey and annotated bibliography of multiobjective combinatorial optimization

This paper provides a survey of the research in and an annotated bibliography of multiple objective combinatorial optimization, MOCO. We present a general formulation of MOCO problems, describe the main characteristics of MOCO problems, and review the main properties and theoretical results for these problems. The main parts of the paper are a section on the review of the available solution methodology, both exact and heuristic, and a section on the annotation of the existing literature in the field organized problem by problem. We conclude the paper by stating open questions and areas of future research. Received: February 7, 2000 / Accepted: April 14, 2000     

Combined strategic and operational planning – an MILP success story in chemical industry

We describe and solve a real world problem in chemical industry which combines operational planning with strategic aspects. In our simultaneous strategic & operational planning (SSDOP) approach we develop a model based on mixed-integer linear (MILP) optimization and apply it to a real-world problem; the approach seems to be applicable in many other situations provided that people in production planning, process development, strategic and financial planning departments cooperate. The problem is related to the supply chain management of a multi-site production network in which production units are subject to purchase, opening or shut-down decisions leading to an MILP model based on a time-indexed formulation. Besides the framework of the SSDOP approach and consistent net present value calculations, this model includes two additional special and original features: a detailed nonlinear price structure for the raw material purchase model, and a detailed discussion of transport times with respect to the time discretization scheme involving a probability concept. In a maximizing net profit scenario the client reports cost saving of several millions US$. The strategic feature present in the model is analyzed in a consistent framework based on the operational planning model, and vice versa. The demand driven operational planning part links consistently to and influences the strategic. Since the results (strategic desicions or designs) have consequences for many years, and depend on demand forecast, raw material availability, and expected costs or sales prices, resp., a careful sensitivity analysis is necessary showing how stable the decisions might be wit h respect to these input data.     

Resource–constrained project scheduling: a heuristic for the multi–mode case

This paper presents a heuristic solution procedure for a very general resource–constrained project scheduling problem. Here, multiple execution modes are available for the individual activities of the project. In addition, minimum as well as maximum time lags between different activities may be given. The objective is to determine a mode and a start time for each activity such that the temporal and resource constraints are met and the project duration is minimized. Project scheduling problems of this type occur e.g. in process industries. The heuristic is a multi–pass priority–rule method with backplanning which is based on an integration approach and embedded in random sampling. Its performance is evaluated within an experimental performance analysis for problem instances of real–life size with 100 activities and up to 5 modes per activity.

---

---

Received: September 22, 2000 / Accepted: May 18, 2001     

Advanced production scheduling for batch plants in process industries

An Advanced Planning System (APS) offers support at all planning levels along the supply chain while observing limited resources. We consider an APS for process industries (e.g. chemical and pharmaceutical industries) consisting of the modules network design (for long–term decisions), supply network planning (for medium–term decisions), and detailed production scheduling (for short–term decisions). For each module, we outline the decision problem, discuss the specifi cs of process industries, and review state–of–the–art solution approaches. For the module detailed production scheduling, a new solution approach is proposed in the case of batch production, which can solve much larger practical problems than the methods known thus far. The new approach decomposes detailed production scheduling for batch production into batching and batch scheduling. The batching problem converts the primary requirements for products into individual batches, where the work load is to be minimized. We formulate the batching problem as a nonlinear mixed–integer program and transform it into a linear mixed–binary program of moderate size, which can be solved by standard software. The batch scheduling problem allocates the batches to scarce resources such as processing units, workers, and intermediate storage facilities, where some regular objective function like the makespan is to be minimized. The batch scheduling problem is modelled as a resource–constrained project scheduling problem, which can be solved by an efficient truncated branch–and–bound algorithm developed recently. The performance of the new solution procedures for batching and batch scheduling is demonstrated by solving several instances of a case study from process industries.     

An Efficient Algebraic Algorithm for the Geometric Completion to Involution

 We describe an adaption of a differential algebraic completion algorithm for linear systems of partial differential equations that allows us to deduce intrinsic differential geometric information like the number of prolongations and projections needed for the completion. This new hybrid algorithm represents a much more efficient realisation of the classical Cartan–Kuranishi completion than previous purely geometric ones. A classical problem in geometric completion theory is the existence of δ-singular coordinate systems in which the algorithms do not terminate. We develop a new and a very simple criterion for δ-singularity based on a comparison of the Janet and the Pommaret division. This criterion can also be used for the direct construction of δ-regular coordinates. Received: July 28, 2000; revised version: October 16, 2001     

Automatic Meshing and Remeshing in the Simultaneous Engineering Context

This paper presents a method to integrate in a better way the finite element method in the CAD/CAM process for two-dimensional problems, through efficient and automatic meshing and remeshing procedures. During the design step, the lack of integration between geometric modeling and numerical analysis remains a crucial problem and it still tends to restrain the use of finite element methods to a small number of engineers. Here we tackle the problem of the automatic remeshing of an object in the context of minor changes in its geometry and topology without restarting the mesh generation from the beginning. We have developed a mesh generator that is able to adapt a previous mesh, through two complementary strategies (for 2D cases) to a new geometry without destroying the whole initial discretization. We also present the possible extension of these concepts to three-dimensional problems.     

Optimal tax depreciation lives and charges under regulatory constraints

Depreciation is not only a representation of the loss in asset-value over time. It is also a strategic tool for management and can be used to minimize tax payments. In this paper we derive the depreciation scheme that minimizes the expected value of the present value of future tax payments for two types of constraints on the depreciation method. We show how the optimal scheme depends on the discount factor and the cash flow distributions. Moreover, we find the somewhat surprising result that the way in which the optimum is affected by uncertainty depends crucially on the type of regulatory constraint. Received: January 9, 2001 / Accepted: Feburary 25, 2002