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.

Over the years, I have taught introductory as well as advanced courses in job scheduling. The problem is fascinating in its variety, which is truly astounding, and in the methodologies that have been offered by many researchers for its resolution. But I have always felt let down when it came to job scheduling under uncertainty: The absence of a comprehensive treatment of these real-life scenarios was a handicap that I felt acutely. After reading this book, I do not feel that way any more.

The fixation on “averages” is often meaningless, if not downright misleading. True, while the statement “on average, such and such phenomenon behaves in a certain way” or “has a particular value” is often a useful bit of information (one is usually interested in the average water temperature at the seaside before taking a jump into the ocean), it often carries insufficient information for intelligent decision making (knowing that one's heartbeat is good “on average” does not help to diagnose the ailment if sometimes it stops beating altogether!). Here is where the “range of variation,” as measured by the variance (or any other measure of dispersion), becomes invaluable.

Scheduling under stochastic conditions has received scant attention from authors in the field. Usually it appears, if at all, in the form of one or two (thin) chapters that introduce the problem and give a treatment based mostly on the assumption that the processing times of the jobs are exponentially distributed. The feeling always has persisted: Whoever heard of processing times that are exponentially distributed? And how to behave if they are not?

The primary motivation for the work presented in this book has been to address the inherent variability of various parameters (e.g., job processing times and due dates, among others) that are encountered in the scheduling of tasks in a production environment and their significant impact on system performance. Variability in scheduling has been modeled in the form of random variables, and most of the work undertaken in this field has considered optimizing the expected value of the performance measure of interest. In doing so, very little importance was attributed to variability of the system, and consequently, very little significance was attributed to the variance of a performance measure. It is often seen that a scheduler's preference is not only for a schedule that has a lower expected value but also for a schedule that provides minimum variability. Hence, schedule evaluation must be performed in terms of both the expectation and the variance of the performance measure. The inclusion of variance in schedule optimization leads to complexities that, apparently, have resulted in a dearth of reported work in the literature as far as evaluating the variance of a performance measure is concerned. Our aim has been to develop closed-form expressions (wherever possible) and devise methodologies to determine the expectation and variance for different performance measures and in diverse scheduling environments, in the face of processing time variability. This effort would lead the way in considering variance issues in schedule optimization and determining schedules that are both expectation- and variance-efficient.

Introduction

In Chapters 4 through 7 we have developed expressions of expectation and variance for various performance measures of a given schedule of jobs. We have considered schedules for different machine configurations. For some of the performance measures of these schedules, necessary assumptions are made on the type of processing time distribution used to enable development of analytical expressions. Table 8.1 gives an overview of the machine configurations and performance measures that we have considered, and it also depicts the assumptions made on the processing time distributions used for each of these cases. This table also presents information on the level of accuracy of the resulting expressions for the expectation and variance of a performance measure and whether the analysis relies on Clark's method (Clark, 1961).

Clark's method for approximating the expectation and variance of the maximum of a set of random variables is based on the assumption of normal distributions for all random variables. In this chapter we relax this assumption and consider the case of general processing time distributions. Our analysis relies on the use of finite-mixture models.

Finite-Mixture Models

The use of a finite mixture of distributions provides a flexible methodology to represent a variety of random phenomena.

Many important engineering problems can be cast in the form of a quadratically constrained quadratic program (QCQP) or a fractional QCQP. In general, these problems are nonconvex and NP-hard. This chapter introduces a semidefinite programming (SDP) relaxation procedure for this class of quadratic optimization problems which can generate a provably approximately optimal solution with a randomized polynomial time complexity. We illustrate the use of SDP relaxation in the context of downlink transmit beamforming, and show that the SDP relaxation approach can either generate the global optimum solution, or provide an approximately optimal solution with a guaranteed worst-case approximation performance. Moreover, we describe how the SDP relaxation approach can be used in magnitude filter design and in magnetic resonance imaging systems.

Introduction

In this chapter, we consider several classes of nonconvex quadratic constrained quadratic programs (QCQPs) and a class of nonconvex fractional QCQPs. The importance of these classes of problems lies in their wide-ranging applications in signal processing and communications which include:

• the Boolean least-squares (LS) problem in digital communications [1];

• the noncoherent maximum-likelihood detection problem in multiple-input multipleoutput (MIMO) communications [2, 3];

• the MAXCUT problem in network optimization [4];

• the large-margin parameter estimation problem in automatic speech recognition [5–8];

• the optimum coded waveform design for radar detection [9];

• the image segmentation problem in pattern recognition [10];

• the magnitude filter design problem in digital signal processing [11];

• the transmit B1 shim and specific absorption rate computation in magnetic resonance imaging (MRI) systems [12, 13];

• […]

Due to their computational efficiency and strong empirical performance, semidefinite relaxation (SDR)-based algorithms have gained much attention in multiple-input, multiple-output (MIMO) detection. However, the theoretical performance of those algorithms, especially when applied to constellations other than the binary phase-shift keying (BPSK) constellation, is still not very well-understood. In this chapter we describe a recently-developed approach for analyzing the approximation guarantees of various SDR-based algorithms in the low signal-to-noise ratio (SNR) region. Using such an approach, we show that in the case of M-ary phase-shift keying (MPSK) and quadrature amplitude modulation (QAM) constellations, various SDR-based algorithms will return solutions with near-optimal log-likelihood values with high probability. The results described in this chapter can be viewed as average-case analyses of certain SDP relaxations, where the input distribution is motivated by physical considerations. More importantly, they give some theoretical justification for using SDR-based algorithms for MIMO detection in the low SNR region.

Introduction

Semidefinite programming (SDP) has now become an important algorithm design tool for a wide variety of optimization problems. From a practical standpoint, SDP-based algorithms have proven to be effective in dealing with various fundamental engineering problems, such as control system design [1, 2], structural design [3], signal detection [4, 5], and network localization [6–8]. From a theoretical standpoint, SDP is playing an important role in advancing the theory of algorithms.

The past two decades have witnessed the onset of a surge of research in optimization. This includes theoretical aspects, algorithmic developments such as generalizations of interior-point methods to a rich class of convex-optimization problems, and many new engineering applications. The development of general-purpose software tools as well as the insight generated by the underlying theory have contributed to the emergence of convex optimization as a major signal-processing tool; this has made a significant impact on numerous problems previously considered intractable. Given this success of convex optimization, many new applications are continuously flourishing. This book aims at providing the reader with a series of tutorials on a wide variety of convex-optimization applications in signal processing and communications, written by worldwide leading experts, and contributing to the diffusion of these new developments within the signalprocessing community. The topics included are automatic code generation for real-time solvers, graphical models for autoregressive processes, gradient-based algorithms for signal-recovery applications, semidefinite programming (SDP) relaxation with worstcase approximation performance, radar waveform design via SDP, blind non-negative source separation for image processing, modern sampling theory, robust broadband beamforming techniques, distributed multiagent optimization for networked systems, cognitive radio systems via game theory, and the variational-inequality approach for Nash-equilibrium solutions.

This chapter presents distributed algorithms for cooperative optimization among multiple agents connected through a network. The goal is to optimize a global-objective function which is a combination of local-objective functions known by the agents only. We focus on two related approaches for the design of distributed algorithms for this problem. The first approach relies on using Lagrangian-decomposition and dual-subgradient methods. We show that this methodology leads to distributed algorithms for optimization problems with special structure. The second approach involves combining consensus algorithms with subgradient methods. In both approaches, our focus is on providing convergence-rate analysis for the generated solutions that highlight the dependence on problem parameters.

Introduction and motivation

There has been much recent interest in distributed control and coordination of networks consisting of multiple agents, where the goal is to collectively optimize a global objective. This is motivated mainly by the emergence of large-scale networks and new networking applications such as mobile ad hoc networks and wireless-sensor networks, characterized by the lack of centralized access to information and time-varying connectivity. Control and optimization algorithms deployed in such networks should be completely distributed, relying only on local observations and information, robust against unexpected changes in topology, such as link or node failures, and scalable in the size of the network.

This chapter studies the problem of distributed optimization and control of multiagent networked systems. More formally, we consider a multiagent network model, where m agents exchange information over a connected network.