Introduction

The subject of spacecraft trajectory optimization has a long and interesting history. The problem can be simply stated as the determination of a trajectory for a spacecraft that satisfies specified initial and terminal conditions, that is conducting a required mission, while minimizing some quantity of importance. The most common objective is to minimize the propellant required or equivalently to maximize the fraction of the spacecraft that is not devoted to propellant. Of course, as is common in the optimization of continuous dynamical systems, it is usually necessary to provide some practical upper bound for the final time or the optimizer will trade time for propellant. There are also spacecraft trajectory problems where minimizing flight time is the important thing, or problems, for example those using continuous thrust, where minimizing flight time and minimizing propellant use are synonymous.

Except in very special (integrable) cases, which reduce naturally to parameter optimization problems, the problem is a continuous optimization problem of an especially complicated kind.

Introduction

The analysis of optimal low-thrust orbit transfer using averaging methods has benefited from the contributions in. In particular the minimum-time transfer between inclined circular orbits was solved in by rotating the orbit plane around the relative line of nodes of initial and final orbits using a piecewise-constant out-of-plane thrust angle switching signs at the relative antinodes while simultaneously changing the orbit size from its initial to its final required value. The original analysis in was further reformulated in in order to arrive at expressions that depict the evolutions of the transfer parameters in a uniform manner valid for all transfers. Further contributions using both analytic and numerical approaches were also carried out in and to solve increasingly more difficult problems, such as by considering realistic constraints and orbit precession due to the important second zonal harmonic J2, while also considering various averaging schemes for rapid computation of the solutions.

The first part of this chapter presents the reformulated Edelbaum problem of the minimum-time low-thrust transfer between inclined circular orbits by further extending it in order to constrain the intermediate orbits during the transfer to remain below a given altitude. The minimum-time problem involving an inequality constraint on the orbital velocity is shown to be equivalent to one involving an equality constraint in terms of the thrust yaw angle representing the control variable that is optimized resulting in the minimum-time solution.

Introduction

A spacecraft in flight is a dynamical system. As dynamical systems go, it is comparatively straightforward; the equations of motion are continuous and deterministic, for the unforced case they are essentially integrable, and perturbations, such as the attractions of bodies other than the central body, are usually small. The difficulties arise when the complete problem, corresponding to a real space mission, is considered. For example, a complete interplanetary flight, beginning in Earth orbit and ending with insertion into Mars orbit, has complicated, time-dependent boundary conditions, straightforward equations of motion but requires coordinate transformations when the spacecraft transitions from planet-centered to heliocentric flight (and vice versa), and likely discrete changes in system states as the rocket motor is fired and the spacecraft suddenly changes velocity and mass. If low-thrust electric propulsion is used, the system is further complicated as there no longer exist integrable arcs and the decision variables, which previously were discrete quantities such as the times, magnitudes and directions of rocket-provided impulses, now also include continuous time histories, that is, of the low-thrust throttling and of the thrust pointing direction. In addition, it may be optimizing to use the low-thrust motor for finite spans of time and “coast” otherwise, with the optimal number of these thrust arcs and coast arcs a priori unknown.

Since the cost of placing a spacecraft in orbit, which is usually the first step in any trajectory, is so enormous, it is particularly important to optimize space trajectories so that a given mission can be accomplished with the lightest possible spacecraft and within the capabilities of existing (or affordable) launch vehicles.

Introduction

Multiple gravity assist (MGA) trajectories represent a particular class of space trajectories in which a spacecraft exploits the encounter with one or more celestial bodies to change its velocity vector. If deep space maneuvers (DSM) are inserted between two planetary encounters, the number of alternative paths can grow exponentially with the number of encounters and the number of DSMs. The systematic scan of all possible trajectories in a given range of launch dates quickly becomes computationally intensive even for moderately short sequences of gravity assist maneuvers and small launch windows. Thus finding the best trajectory for a generic transfer can be a challenge. The search for the best transfer trajectory can be formulated as a global optimization problem. An instance of this global optimization problem can be identified through the combination of a particular trajectory model, a particular sequence of planetary encounters, a number of DSMs per arc, a particular range for the parameters defining the trajectory model, and a particular optimality criterion. Thus a different trajectory model would correspond to a different instance of the problem even for the same destination planet and sequence of planetary encounters. Different models as well as different sequences and ranges of the parameters can make the problem easily solvable or NP-hard. However, the physical nature of this class of transfers allows every instance to be decomposed into subproblems of smaller dimension and smaller complexity.

It has been a very long time since the publication of any volume dedicated solely to space trajectory optimization. The last such work may be Jean-Pierre Marec's Optimal Space Trajectories. That book followed, after 16 years, Derek Lawden's pioneering Optimal Trajectories for Space Navigation of 1963. If either of these books can be found now, it is only at a specialized used-book seller, for “astronomical” prices.

In the intervening several decades, interest in the subject has only grown, with space missions of sophistication, complexity, and scientific return hardly possible to imagine in the 1960s having been designed and flown. While the basic tools of optimization theory – such things as the calculus of variations, Pontryagin's principle, Hamilton-Jacobi theory, or Bellman's principle, all of which are useful tools for the mission designer – have not changed in this time, there has been a revolution in the manner in which they are applied and in the development of numerical optimization. The scientists and engineers responsible have thus learned what they know about spacecraft trajectory optimization from their teachers or colleagues, with the assistance, primarily, of journal and conference articles, some of which are now “classics” in the field.

This volume is thus long overdue. Of course one book of ten chapters cannot hope to comprehensively describe this complex subject or summarize the advances of three decades. While it purposely includes a variety of both analytical and numerical approaches to trajectory optimization, it is bound to omit solution methods preferred by some researchers.

Introduction

The three-body system has been of interest to mathematicians and scientists for well over a century dating back to Poincaré. Much of the interest in recent years has focused on using the interesting dynamics present around libration points to create trajectories that can travel vast distances around the solar system for almost no fuel expenditure traversing the so-called “Interplanetary Super Highway” (IPS). It has also been proposed to use Lagrange points as staging bases for more ambitious missions.

Lagrange points are equilibrium points of the three-body system that describes the motion of a massless particle in the presence of two massive primaries in a reference frame that rotates with the primaries. There are five Lagrange points (labeled L1,…,L5), the three collinear points along the line of the two primaries, and the two equilateral points that form an equilateral triangle with the two primaries. It is the collinear points that are of the most interest and in particular the L1 point between the two primaries and the L2 point on the far side of the smaller primary. Since Poincaré, there has been much work on finding periodic solutions to the three-body problem. Early work was confined to analytic studies that are restricted to approximations as there exists no closed form analytical solution to the three-body system equations of motion.

Introduction

In this chapter we consider the problem of sequencing a given number of jobs on a single machine and devise methodologies and develop closed-form expressions (wherever possible) to compute the expectation and variance of various performance measures. Numerical illustrations indicating the significance and applicability of our work are also presented through example problems.

Besides being of significance in their own right, single-machine problems also constitute a good starting point for analyzing more complex scheduling environments of flow shop and job shop. The different performance measures that we consider for the single-machine case can be classified into two categories:

1. Completion-time-based, which includes total completion time (total flow time), total weighted completion time, and total weighted discounted completion time

2. Due-date-based, which includes total tardiness, total weighted tardiness, total number of tardy jobs, total weighted number of tardy jobs, mean lateness, and maximum lateness.

The processing time of a job is assumed to be a random variable that follows an arbitrary probability distribution.

First, we present the notation that is used in this chapter. Some of this notation has been introduced already in earlier chapters. However, we include it here for the sake of completeness.

Introduction

In Chapter 4, different single-machine models were dealt with in detail, and now we extend our expectation-variance (EV) analysis to multimachine environments. In this chapter we focus on a flow shop with unlimited intermediate storage (buffer capacity) where n jobs are waiting to be processed. The flow shop consists of m machines. Our analysis for this environment is identical to that presented by Wilhelm and Ahmadi-Marandi (1982), who studied an assembly system. A flow shop is, in fact, a simpler version of an assembly line, and hence their methodology can be adapted to our case. The EV analysis of a flow shop would act as a stepping stone for undertaking the EV analysis for job-shop and parallel-machine environments. Numerical illustrations indicating the significance and applicability of our work are also presented through example problems. The objective function that we consider is to minimize the makespan. Makespan is an important objective in a flow shop because a lower makespan value implies higher utilization of the machines. Also, we consider permutation flow shops, in which the job sequence does not change across the machines, and the jobs on each machine are also processed according to the first come, first served principle.

Uncertainty

The realm of manufacturing is replete with instances of uncertainties in job processing times, machine statuses (up or down), demand fluctuations, due dates of jobs, and job priorities. These uncertainties stem from the inability to predict with sufficient accuracy information about product demand, job processing times, and occurrences such as unexpected machine breakdowns and arrivals/cancellations of orders. Although highly efficient forecasting methods are currently available, product demand errors invariably occur in the production system. Process variability is another significant factor that introduces variations and uncertainty into the manufacturing process.

Uncertainty is inarguably an undesirable factor in the manufacturing process because it does not give production managers complete control over the manufacturing process. Some of the ill effects of these uncertainties include system instability, excess inventory, customer dissatisfaction because due dates are not met, and, more important, loss of revenue. Recent advances in manufacturing management techniques, such as agile manufacturing, have made variability an important design criterion in order to ensure predictability and dependability of production systems. Agility is the ability of a system to thrive and prosper in an environment of constant and unpredictable change.

Uncertainty in Scheduling

As true as it would be with any other field within manufacturing, the uncertainty factor is of considerable importance in production scheduling. Scheduling is a decision-making process that plays an important role in most manufacturing as well as in most information-processing environments.

Introduction

Robust scheduling is one of the approaches adopted to deal with uncertainties in stochastic scheduling. Since these uncertainties, arising as they do from variability in the scheduling parameters, significantly affect the performance of a system, a viable approach has been to determine a robust schedule that is least susceptible to disturbances or variations in the input parameters and that has minimum variability in its output performance measure. For instance, when processing times are uncertain, a robust schedule would have the least variance of the output performance measure, although it might not necessarily have the least expected value. As also mentioned in Chapter 1, of the various parameters involved in scheduling, we intend to focus on the uncertainty factor associated with job processing times. The following sections detail different robust scheduling methodologies that are available to model certain scheduling environments and the underlying principles behind those various approaches. Our primary focus is to elicit and delve in detail on the modeling approaches and not to expostulate the solution methodologies. However, we do briefly discuss the various solution approaches that are used to solve these robust scheduling problems and also state relevant results (as propositions) that are used in developing these solution methodologies. We intend to capture the core techniques that have been used in modeling robustness in scheduling and would advise interested readers to refer to the appropriate literature for a detailed and complete exposition.

Scheduling is a decision-making process that is commonly encountered in practice – in both production and nonproduction-related environments. The effectiveness of a schedule depends on how well it performs in the environment for which it is designed. For an environment that involves a stochastic element, which is more often the case in practice, a typical approach presented in the literature has been to determine a schedule that optimizes the expected value of a performance measure. However, optimizing merely the expectation of a performance measure for a schedule is not enough for use in such an environment because variability of the measure plays an important role in influencing the performance of the schedule. It is, therefore, essential that a schedule be selected for implementation that has suitable values for both the expectation and variance of the performance measure in consideration. In this book, we present methodologies for determining such a schedule, and in this respect, this book is different from the other books on scheduling.

The book is organized as follows. In Chapter 1, we focus on the impact of uncertainty (variability) in scheduling, and the need for efficient modeling of stochastic scheduling problems and for devising effective scheduling strategies to counter the impact of variability. We specifically highlight the prevalence of variability in job processing times and elicit the issue of neglecting variance in schedule optimization and the significance of considering variance. Furthermore, we enunciate the need for a comprehensive analytical evaluation of the expectation and variance of different performance measures.