A SINGULAR-ARC APPROXIMATION TO A DYNAMIC SAILPLANE FLIGHT PATH OPTIMIZATION PROBLEM

A dynamic sailplane performance problem is investigated using optimal control theory. The problem is to minimize the total flight time between successive thermals subject to zero altitude loss. From the original nonlinear optimal control problem, a singular linear/quadratic problem is derived and solved.

A relationship between the original optimal control problem and a certain parameter optimization problem is explored, and it is shown that the solution to this parameter optimization provides a lower bound for the minimum flight time of the original optimal control problem. The parameter optimization solution is adopted as the reference trajectory for the linear/quadratic problem. Finally, the linear/quadratic problem is shown to provide a good approximation to the original optimal control problem at a small fraction of the computing cost.     

A Dynamic Programming Algorithm for Facility Location and Allocation

This article considers the problem of facility location-allocation. The problem is to allocate K facilities in M facility locations and assign N demands such that the total cost is minimized. The model is formulated as a mathematical programming problem and decomposed into the recursive equations of dynamic programming. A sample problem is presented and analyzed in detail in order to demonstrate an application of the model. The procedure was coded in Fortran IV and used to obtain the sample problem results.     

Heuristics for the Common Due Date Weighted Tardiness Problem

In this paper we consider the single machine “common due date weighted tardiness problem.” Initially the problem is related to other versions of the single machine total weighted tardiness problem. Several heuristics for the problem are discussed. Three “simple” heuristics are proposed and shown to have arbitrarily bad worst case performance. A fourth heuristic is then proposed and shown to have a worst case performance bound of 2.     

Economic Lot-Sizing with Remanufacturing Options

We study a production planning problem with remanufacturing. We provide the problem's general formulation and assess its computational complexity under various cost structures. We prove that the problem is NP-complete for general concave-cost structures. When costs are linear, we obtain an 0(T³) algorithm based on transforming the problem into the transportation problem in a special way. Finally, we suggest linearizing costs as an alternative for solving the problem in the real world.     

Closed form models for determining the optimal dwell point location in automated storage and retrieval systems

This paper examines the problem of where a storage/retrieval machine should reside, or dwell, when an automated storage and retrieval system (AS/RS) becomes idle to minimize the expected value of the next transaction time. After a review of the relevant literature on AS/RS dwell point strategies, this paper proposes several analytical models of these expected response times of the AS/RS based on the relative locations of the input and output ports of the AS/RS. It uses a continuous rack approximation to provide analytical models of the dwell point location problem. These models provide closed form solutions for the dwell point location in an AS/RS. Extensions are made to consider AS/RS with a variety of configurations including multiple input and output ports. These models not only provide solutions to the dwell point location problem, but they provide considerable insight into the nature of this problem, which is particularly valuable when the requirements facing the AS/RS are uncertain.     

Algorithms for the model configuration problem

The model configuration problem is a combinatorial optimization problem that arises in the context of switching cabinet manufacturing in the telecommunication industry. We discuss the manufacturing environment and define the q-model problem in this context, for q ≥ 1. We then discuss the structural properties of the q-model problem, and propose an efficient procedure for solving the 1-model problem. We also propose several heuristic procedures for solving the 2-model problem, and present an evaluation of these procedures through an extensive computational experiment.     

Scheduling Production on One Machine with Changeover Costs

A single machine is used to produce several products so as to satisfy known demands over a fixed number of periods. Each time switches are made between products, there are changeover costs as described by a matrix C=[c_ij], where c_ij is the cost of switching from product i to product j. The problem is to find a schedule of production that minimizes the total changeover penalty while meeting the due dates of all customer orders. The function used in a forward-time dynamic program is shown to have a monotonicity property that can be used to advantage when seeking an optimal solution to the problem. This monotonicity property is applied in developing an efficient backward-time search procedure for solving the problem.     

Optimality Criteria for Flowshop Schedules

This article considers the problem of scheduling n jobs on M machines in a flowshop and examines the present formulation of the problem. To understand the true nature of the problem, this article provides economic interpretations of various optimality criteria which are being used for solving the scheduling problem. A general optimization criterion, called minimization of opportunity cost, is proposed for flow-shop scheduling problems and the results of the sensitivity analysis of various optimality criteria are reported which indicate the need to reformulate the scheduling problem.     

PLANNING TIMELY ARRIVALS TO A STOCHASTIC PRODUCTION OR SERVICE SYSTEM

A stochastic planning problem of determining the optimal arrival times for N customers, each to be assigned to one of K equal time slots, is considered. The objective is to minimize the total system cost, which is composed of the customer waiting cost and the server availability cost. This optimal arrival schedule is examined for a single server system with either exponential or Erlang-fc service time distribution.

Two versions of this planning arrival problem are considered, a dynamic version and a static version. The dynamic problem requires planning decisions to be made at the beginning of each time slot, while in the static problem all decisions must be made at the beginning of the first time slot. The dynamic problem is solved by dynamic programming. The structure of the optimal dynamic policy is identified and used to solve the dynamic problem efficiendy. A branch-and-bound algorithm, which uses the solution to the dynamic problem, is developed to solve the static problem. The results can be used to schedule material deliveries, work-in-process flows, appointments, or other similar systems.     

Maximizing pseudoconvex transportation problem: a special type

The paper discusses a non-concave fractional programming problem aiming at maximization of a pseudoconvex function under standard transportation conditions. The pseudoconvex function considered here is the product of two linear functions contrasted with a positive valued linear function. It has been established that optimal solution of the problem is attainable at an extreme point of the convex feasible region. The problem is shown to be related to indefinite quadratic programming which deals with maximization of a convex function over the given feasible region. It has been further established that the local maximum point of this quadratic programming problem is the global maximum point under certain conditions, and its optimal solution provides an upper bound on the optimal value of the main problem. The extreme point solutions of the indefinite quadratic program are ranked to tighten the bounds on the optimal value of the main problem and a convergent algorithm is developed to obtain the optimal solution.     

The Cost of Consecutivity in the (5, 7) Cyclic Staffing Problem

The (5, 7) cyclic staffing problem is the problem of finding the least number of workers assigned to a 7 day cyclic schedule, so that sufficient workers are present during day i to meet requirement b_i and each person works a shift of 5 consecutive days and is idle for the other 2. In this paper we derive an expression for the minimal workforce size in the problem in terms of the b_i's. This result is interesting because it shows the extra number of workers needed by insisting that each person's idle days are consecutive.     

Capacitated disassembly scheduling with random demand

This paper considers disassembly scheduling, which is the problem of determining the quantity and timing of the end-of-use/life products to be disassembled while satisfying the demand for their parts obtained from disassembling the products over a planning horizon. This paper focuses on the problem with stochastic demand of parts/modules, capacity restrictions on disassembly resources, and multiple product types with a two-level product structure. The two-level product structure implies that an end-of-use/life product is hierarchically decomposed into two levels where the first level corresponds to the parts/modules and the second level corresponds to the product. We formulate the problem as a stochastic inventory model and to solve the problem we propose a Lagrangian heuristic algorithm as well as an optimisation algorithm for the sub-problems obtained from Lagrangian decomposition. The test results on randomly generated problems show that the Lagrangian heuristic algorithm demonstrates good performance in terms of solution quality and time.     

Tooling choices and product performance

One of the dilemmas that manufacturers face involves the tradeoff between the cost of maintaining a variety of production processes, and the cost of not having the ideal process for every product that they produce. This issue is continuing to become more of a problem as manufacturers are forced by market conditions to offer a wider selection of products. We study an instance of this problem in the manufacture of sheet metal parts. We model the problem of selecting and/or designing tools to punch holes in these parts. The cost of not having an “ideal process” is the cost of not having a tool that precisely matches a hole's design diameter. We consider both general “process deviation” costs as well as the Taguchi loss function. Solution procedures are provided for several versions of the problem.     

The orienteering problem with stochastic profits

Given a graph G = (N, E), N representing the set of nodes associated with Normally distributed random profits and E representing the set of edges with associated travel times, we define the Orienteering Problem with Stochastic Profits (OPSP) as the problem of finding a tour that visits a subset of N within a prespecified time limit and maximizes the probability of collecting more than a prespecified target profit level. We develop an exact solution scheme based on a parametric formulation of the problem and present a bi-objective genetic algorithm. We also analyze the characteristics of the problem and test the algorithms computationally. The experimental results identify conditions under which the OPSP results in significant improvements in reaching the target profit when compared with the solution from the deterministic variant of the problem.     

Solving the facility and layout and location problem by ant-colony optimization-meta heuristic

This paper describes a heuristic algorithm for solving the plant/facility location problem by applying ant-colony optimization meta-heuristic. The facility location problem is discussed, and a mathematical formulation is presented. The problem is then modelled as a quadratic assignment problem. An ant algorithm is developed to solve the problem. The results reveal that the proposed algorithm can be adaptively constructed to solve discrete plant location problems. This has been applied to a set of known test problems and appears to be able to compete with other current solutions with encouraging results.     

The interaction of location and inventory in designing distribution systems

Many companies face the strategic decision of deciding on the number of Distribution Centers (DCs), their location, and which customers they serve. One objective for a company facing this decision is to maintain acceptable service while minimizing the fixed costs of operating the DCs, inventory holding costs at the DCs, and transportation costs between plants and DCs, and DCs and customers. For insight into this problem, we develop an analytical model for a stylized version of it. However, since the general version of the problem is NP-Hard, we also develop heuristic procedures. We solve a variety of example problems to test the performance of these heuristics relative to optimal solutions and a lower bound based on a relaxation of the original problem. Managerial insight based on our computational studies is provided. We also present a small case-study example motivated by our interaction with Frito-Lay, Inc     

A Heuristic Production Lot Scheduling Model

This article describes a model which seeks to schedule the production of m products over the next n production planning periods in a manner which minimizes total setup, production, and inventory costs while observing all constraints imposed by the capacities of the productive resources. The model formulates this problem as a fixed charge problem, and then uses a modified version of the simplex method to locate optimal or near optimal solutions of this nonlinear programming problem. A discrete optimizing approach is used to estimate the effectiveness of the model.