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 gather accurate information about the various parameters (e.g., processing times, product demand) or to gain complete control over the different manufacturing processes that are involved. Hence, it becomes imperative on the part of a production manager to take into account the impact of uncertainty on the performance of the system on hand. This uncertainty, or variability, is of considerable importance in the scheduling of production tasks. A scheduling problem is primarily to allocate the jobs and determine their start times for processing on a single or multiple machines (resources) for the objective of optimizing a performance measure of interest. If the problem parameters of interest e.g., processing times, due dates, release dates are deterministic, the scheduling problem is relatively easier to solve than for the case when the information is uncertain about these parameters. From a practical point of view, the knowledge of these parameters is, most often than not, uncertain and it becomes necessary to develop a stochastic model of the scheduling system in order to analyze its performance. Investigation of the stochastic scheduling literature reveals that the preponderance of the work reported has dealt with optimizing the expected value of the performance measure. By focusing only on the expected value and ignoring the variance of the measure used, the scheduling problem becomes purely deterministic and the significant ramifications of schedule variability are essentially neglected. In many a practical cases, a scheduler would prefer to have a stable schedule with minimum variance than a schedule that has lower expected value and unknown (and possibly high) variance. Hence, it becomes apparent to define schedule efficiencies in terms of both the expectation and variance of the performance measure used. It could be easily perceived that the primary reasons for neglecting variance are the complications arising out of variance considerations and the difficulty of solving the underlying optimization problem. Moreover, research work to develop closed-form expressions or methodologies to determine the variance of the performance measures is very limited in the literature. However, conceivably, such an evaluation or analysis can only help a scheduler in making appropriate decisions in the face of uncertain environment. Additionally, these expressions and methodologies can be incorporated in various scheduling algorithms to determine efficient schedules in terms of both the expectation and variance. In our research work, we develop such analytic expressions and methodologies to determine the expectation and variance of different performance measures of a schedule. The performance measures considered are both completion time and tardiness based measures. The scheduling environments considered in our analysis involve a single machine, parallel machines, flow shops and job shops. The processing times of the jobs are modeled as independent random variables with known probability density functions. With the schedule given a priori, we develop closed-form expressions or devise methodologies to determine the expectation and variance of the performance measures of interest. We also describe in detail the approaches that we used for the various scheduling environments mentioned earlier. The developed expressions and methodologies were programmed in MATLAB R12 and illustrated with a few sample problems. It is our understanding that knowing the variance of the performance measure in addition to its expected value would aid in determining the appropriate schedule to use in practice. A scheduler would be in a better position to base his/her decisions having known the variability of the schedules and, consequently, can strike a balance between the expected value and variance. / Master of Science

In this dissertation, we develop novel approaches to independently address two issues that are commonly encountered in machine scheduling problems: uncertainty of problem parameters (in particular, due to job processing times), and batching of jobs for processing on capacitated machines. Our approach to address the uncertainty issue regards the indeterminate parameters as random variables, and explicitly considers the resulting variability of a performance measure. To incorporate variability into the schedule selection process, we develop a method to evaluate both the expectation and variance of various performance measures for a given schedule. Our method is based on the use of mixture models to approximate a variety of distribution types. The Expectation-Maximization algorithm of Dempster et al. (1977) is applied to derive mixture models of processing time distributions. Our method, then, utilizes these mixture models to calculate the distributions of other random variables in order to derive the expectation and variance of various scheduling performance measures, assuming that the job sequencing decisions are known a priori. To make our method more computationally efficient, we adapt a mixture reduction method to control the number of mixture components used in the intermediate steps. We apply our method to two different scheduling problems: the job shop makespan scheduling problem and the single machine total weighted tardiness scheduling problem, and compare its performance with that of Monte-Carlo method. The results show the efficacy of our mixture approximation method. It generates fairly accurate results while requiring significantly less CPU times. The proposed method offers a good compromise between the Monte Carlo method, which requires extensive effort, and use of simple normal approximation, which produces lower-quality results. Next, we introduce and demonstrate for the first time in the literature the use of conditional-value-at-risk (CVaR) as a criterion for stochastic scheduling problems in order to obtain risk-averse solutions. This criterion has the tendency of minimizing both the expectation and variance of a performance measure simultaneously, which is an attractive feature in the scheduling area as most of the literature in this area considers the expectation and variance of a performance measure separately. Also, the CVaR has an added advantage of maintaining a linear objective function. We develop a scenario-based mixed integer programming formulation to minimize CVaR for the general scheduling problem involving various performance measures, and employ a decomposition-based approach for its solution. Furthermore, a set of valid inequalities are incorporated to strengthen the relaxed master problem of this decomposition scheme. The proposed approach is demonstrated on the single machine total weighted tardiness scheduling problem. Our computational investigation reveals the efficacy of the proposed decomposition approach and the effectiveness of using the CVaR as an optimization criterion for scheduling problems. Besides providing an exact approach to solve our stochastic scheduling problem, we also develop an efficient heuristic method to enable the use of CVaR for large-sized problems. To that end, we modify the Dynasearch method of Grosso et al. (2004) to minimize CVaR for a stochastic scheduling problem. Furthermore, we extend the application of CVaR to a parallel-machine total weighted tardiness problem. The use of CVaR appears to be quite promising for simultaneously controlling both the expected value and variability of a performance measure in a stochastic scheduling environment. Scenario-based formulations have frequently been used for stochastic scheduling problems. However, the determination of a lower bound can be a time-consuming task for this approach. Next, we develop a new method for scenario generation that is computationally competitive and that assures attainment of an exact lower bound. Our approach is based on discretization of random parameter distributions of job processing times. We use the idea of Recursive Stratified Sampling to partition the probability space, so that the conditional expectations in each region yield scenario-wise parameter values. These scenarios are, then, used to formulate a two-stage stochastic program, which yields a lower bound for the original stochastic problem. We provide theoretical basis of our bounding approach for both the expectation and CVaR objectives. Our discrete bounding method generates exact lower bounds, as against the probabilistic bounds generated by Sample Average Approximation. We also present results of our numerical experimentation to compare the performances of these two approaches in terms of the bound value obtained and the CPU time required. The problem pertaining to integrated batching and scheduling of jobs on capacitated parallel machines that we consider arises in the primary manufacturing sector of a pharmaceutical supply chain. We, first, develop a comprehensive mathematical programming model that can accommodate various realistic features of this problem. These features include batch production, sequence-dependent setup time/cost, and inter-period carryover of setup status. We further derive several valid inequalities that are based on the embedded subproblem structure. We also consider an alternative formulation (termed the Plant Location model) based on the lot-sizing perspective of the problem. Noting the resemblance of the campaign sequencing subproblem to the high multiplicity asymmetric traveling salesman problem (HMATSP), we adapt various ideas from the HMATSP to enforce the connectivity of the sequencing graph. Due to the complexity of this problem, we also explore the possibility of applying column generation technique for its solution. Various schemes of problem decomposition are considered, along with the use of dual stabilization technique to improve the convergence of the column generation procedure. We also develop heuristic methods to generate initial feasible solutions that further enhance the performance of the column generation method. A computational experimentation has been conducted on a data set that mimics real-life problem instances. It illustrates the effectiveness of using the proposed column generation method. / Ph. D.