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
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/31264 |
| Date | 27 February 2004 |
| Creators | Nagarajan, Balaji |
| Contributors | Industrial and Systems Engineering, Sarin, Subhash C., Jain, Sanjay, Chen, Fengshan Frank |
| Publisher | Virginia Tech |
| Source Sets | Virginia Tech Theses and Dissertation |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
| Relation | Thesis.pdf |
Page generated in 0.0025 seconds