Search

This paper studies the linear programming problem in which all coefficients (even those of the stipulations matrix) are rational functions of a single parameter t called ‘time,’ and provides an algorithm that can serve problems of the following two types: (1) Steady-state behavior [the algorithm can be used to determine the functional form x(t) of the optimal solution as a function of t, this form being valid for all ‘sufficiently large’ values of t], and (2) sensitivity analysis [if a value t0 of ‘time’ is given, the algorithm can be used to determine the two possible functional forms of the optimal solution for all values of t ‘sufficiently dose’ to t0 (the first functional form valid for t«t0, the second for t»t0)]. In addition, the paper gives certain qualitative information regarding steady-state behavior, including the following result: If for some one of the properties of consistency, boundedness, or bounded constraint set, there exists a sequence tn↗+∞ such that the linear program at tn has this property for all n, then the program has this property for all ‘sufficiently large’ values of t. [ABSTRACT FROM AUTHOR]

One approach to coping with the apparent difficulty of many schedule-optimization problems, such as occur in machine shops and computer processing, is to devise efficient algorithms that find schedules guaranteed to be "near-optimal." This paper presents an introduction to this approach by describing its application to a well-known multiprocessor scheduling model and illustrating the variety of algorithms and results that are possible. The paper concludes with a brief survey of what has been accomplished to date in the area of scheduling using this approach. [ABSTRACT FROM AUTHOR]

This paper develops a methodology to evaluate various aspects of logistics supply support of space bases. It is assumed that there exists at the space base a schedule of operations that reflects the day-to-day living, build-up, and scientific experimental activities that are to be carried on. These activities, in turn, set a series of demands or requirements for products over a time spectrum. The supply system must deliver products so as to meet the amounts and times of the product requirements. Each product or module has an earliest and latest time by which it must be delivered. A mathematical model is developed that plans a series of trips, the dates at which each is to be sent, and the composition of the cargoes on each trip that satisfy the series of requirements over a time spectrum imposed by the activities at the space base. The series of trips are an expression of an efficient plan that simultaneously considers demands for different products at different future times and observes the various constraints of the system (e.g., cargo capacity of spaceships). The mathematical formulation of this scheduling problem is a simple non- linear discrete programming problem. An algorithm has been developed for its solution, and a description thereof is presented. The model is illustrated by showing how it would supply a long-term lunar base. Various uses of the model are described. [ABSTRACT FROM AUTHOR]

Two major decisions are made when scheduling the operations of a fossil-fuel power-generating system over a short time horizon. The "unit commitment" decision indicates what generating units are to be in use at each point in time. The "economic dispatch" decision is the allocation of system demand among the generating units in operation at any point in time. Both these decisions must be considered to achieve a least-cost schedule over the short time horizon. In this paper we present a mixed integer programming model for the short time horizon power-scheduling problem. The objective of the model is to minimize the sum of the unit commitment and economic dispatch costs subject to demand, reserve, and generator capacity and generator schedule constraints. A branch-and-bound algorithm is proposed using a Lagrangian method to decompose the problem into single generator problems. A subgradient method is used to select the Lagrange multipliers that maximize the lower bound produced by the relaxation. We present computational results that indicate the technique is capable of solving large problems to within acceptable error tolerances. [ABSTRACT FROM AUTHOR]

This paper discusses the distributional Little's law and examines its applications in a variety of queueing systems. The distributional law relates the steady-state distributions of the number in the system (or in the queue) and the time spent in the system (or in the queue) in a queueing system under FIFO. We provide a new proof of the distributional law and in the process we generalize a well known theorem of Burke on the equality of pre-arrival and postdeparture probabilities. More importantly, we demonstrate that the distributional law has important algorithmic and structural applications and can be used to derive various performance characteristics of several queueing systems which admit distributional laws. As a result, we believe that the distributional law is a powerful tool for the derivation of performance measures in queueing systems and can lead to a certain unification of queueing theory. [ABSTRACT FROM AUTHOR]

This paper investigates the application of a new class of neighborhood search algorithms--cyclic transfers--to multivehicle routing and scheduling problems. These algorithms exploit the two-faceted decision structure inherent to this problem class: First, assigning demands to vehicles and, second, routing each vehicle through its assigned demand stops. We describe the application of cyclic transfers to vehicle routing and scheduling problems. Then we determine the worst-case performance of these algorithms for several classes of vehicle routing and scheduling problems. Next, we develop computationally efficient methods for finding negative cost cyclic transfers. Finally, we present computational results for three diverse vehicle routing and scheduling problems, which collectively incorporate a variety of constraint and objective function structures. Our results show that cyclic transfer methods are either comparable to or better than the best published heuristic algorithms for several complex and important vehicle routing and scheduling problems. Most importantly, they represent a novel approach to solution improvement which holds promise in many vehicle routing and scheduling problem domains. [ABSTRACT FROM AUTHOR]

Partitioning methods lend themselves very well to implementation on parallel computers. In recent years, branch-and-bound algorithms have been tested on various types of architectures. In this paper, we develop a queueing network model for the analysis of a class of branch-and-bound algorithms on a master-slave architecture. The analysis is based on a fluid flow approximation. Numerical examples illustrate the concepts developed. Finally, related branch-and-bound algorithms are studied using a machine repair queueing model. [ABSTRACT FROM AUTHOR]

This paper considers a version of the economic lot sizing problem for a single product produced in a facility of finite capacity over a finite time horizon with specifiable start and end conditions. A set of algorithms is presented that will approximate the optimal production schedule to a given allowable error (e). Algorithms with computation time bounds of O(l/e[sup 2]) are presented which allow for setups of finite length, setups with or without direct cash flow, quite general cost and demand functions, and a wide variety of production policy constraints. The procedures make no a priori assumptions about the form of the optimal solution. Numerical results are included. [ABSTRACT FROM AUTHOR]

This paper studies an M/G/1 queueing system with a finite waiting room and with server vacation times consisting of periods of time that the server is away from the queue doing additional work. This model has been used in conjunction with a related model to analyze the performance of a processor with a cyclic scheduling algorithm and where, due to finite queueing capacities, losses are a primary concern. Service at the queue is exhaustive, in that a busy period at the queue ends only when the queue is empty. At each termination of a busy period, the server takes an independent vacation. The queue length process is studied using the embedded Markov chain. Using a combination of the supplementary variable and sample biasing techniques, we derive the general queue length distribution of the time continuous process, as well as the blocking probability of the system, due to the finite waiting room in the queue. We also obtain the busy period and waiting time distributions. [ABSTRACT FROM AUTHOR]

A previous research report of the authors presented a formal model of the one-machine job-shop scheduling problem with variable labor capacity. This report presents some computational experience with the algorithm proposed previously and a discussion of the structural aspects of the problem. Extensions and refinements of the algorithm are introduced to deal with nonsimultaneous job arrivals and the production smoothing problem. These results provide insight into the structure of the aggregate-detailed cost trade-off problem and suggest a good heuristic decision rule for problems of realistic size and complexity. [ABSTRACT FROM AUTHOR]