Analytic evaluation of the expectation and variance of different performance measures of a schedule on a single machine under processing time variability. (English) Zbl 1165.90476
Summary: We present closed-form expressions, wherever possible, or devise algorithms otherwise, to determine the expectation and variance of a given schedule on a single machine. We consider a variety of completion time and due date-based objectives. The randomness in the scheduling process is due to variable processing times with known means and variances of jobs and, in some cases, a known underlying processing time distribution. The results that we present in this paper can enable evaluation of a schedule in terms of both the expectation and variance of a performance measure considered, and thereby, aid in obtaining a stable schedule. Additionally, the expressions and algorithms that are presented, can be incorporated in existing scheduling algorithms in order to determine expectation-variance efficient schedules.
MSC:
| 90B36 | Stochastic scheduling theory in operations research |
Keywords:
single machine scheduling; processing time variability; various performance measures; expectation-variance analysisReferences:
| [1] | Ayhan H, Olsen TL (2000) Scheduling of multi-class single server queves under nontraditional performance measures. Oper Res 48(3):482–489 · Zbl 1106.90319 · doi:10.1287/opre.48.3.482.12428 |
| [2] | Clark CE (1961) The greatest of a finite set of random variables. Oper Res 9:145–162 · Zbl 0201.51102 · doi:10.1287/opre.9.2.145 |
| [3] | Daniels RL, Carrillo JE (1997) {\(\beta\)}-robust scheduling for single-machine systems with uncertain processing times. IIE Trans 29:977–985 |
| [4] | Daniels RL, Kouvelis P (1995) Robust scheduling to hedge against processing time uncertainty in single-stage production. Manag Sci 41(2):363–376 · Zbl 0832.90050 · doi:10.1287/mnsc.41.2.363 |
| [5] | De P, Ghosh JB, Wells CE (1992) Expectation-variance analysis of job sequences under processing time uncertainty. Int J Prod Econ 28:289–297 · doi:10.1016/0925-5273(92)90017-2 |
| [6] | Dodin B (1996) Determining the optimal sequences and the distributional properties of the completion times in stochastic flow shops. Comput Oper Res 23:829–843 · Zbl 0868.90064 · doi:10.1016/0305-0548(95)00083-6 |
| [7] | Jung YS, Nagasawa H, Nishiyama N (1990) Bicriterion single-stage scheduling to minimize both the expected value and the variance of the total flow time. J Jpn Ind Man Assoc 39:76–82 (in Japanese) |
| [8] | Kouvelis P, Daniels RL, Vairaktarakis G (2000) Robust scheduling of a two-machine flow shop with uncertain processing times. IIE Trans 32:421–432 |
| [9] | Krokhmal P, Grundell D, Pardalos PM (2007) Asymptotic behavior of the optimal value of multidimensional assignment problems. Math Program 109(2–3):525–551 · Zbl 1147.90033 · doi:10.1007/s10107-006-0036-x |
| [10] | McKay KN, Safayeni FR, Buzacott JA (1988) Job-shop scheduling theory: What is relevant? Interfaces 18:84–90 · doi:10.1287/inte.18.4.84 |
| [11] | Morizawa K, Ono T, Nagasawa H, Nishiyama N (1993) An interactive approach for searching a preferred schedule. J Jpn Ind Man Assoc 39:76–82 |
| [12] | Murata T, Ishibuchi H, Tanaka H (1996) Multi-objective genetic algorithm and its applications to flowshop scheduling. Comput Ind Eng 30:957–968 · doi:10.1016/0360-8352(96)00045-9 |
| [13] | Nagasawa H, Shing C (1997) Interactive decision system in parallel-machine stochastic multi-objective scheduling. In: Proceedings of the 1st international conference on engineering design and automation, Bangkok, Thailand, pp 421–424 |
| [14] | Nagasawa H, Shing C (1998) Interactive decision system in stochastic multi-objective scheduling to minimize the expected value and variance of total flow time. J Oper Res Soc Jpn 41(2):261–278 |
| [15] | Portougal V, Trietsch D (1998) Makespan related criteria for comparing schedules in stochastic environments. J Oper Res Soc 49(11):1188–1195 · Zbl 1140.90417 |
| [16] | Rajendran C (1995) Heuristics for scheduling in flowshop with multiple objectives. Eur J Oper Res 82:540–555 · Zbl 0905.90107 · doi:10.1016/0377-2217(93)E0212-G |
| [17] | Shing C, Nagasawa H (1996) Interactive decision support system in stochastic multi-objective scheduling. Bull Osaka Prefect Univ Ser A 45(2):133–141 · Zbl 0908.90161 |
| [18] | Wilhelm WE (1986) The application of lognormal models of transient operations in the flexible manufacturing environment. J Manuf Syst 5(4):253–266 · doi:10.1016/0278-6125(86)90056-7 |
| [19] | Yang J, Gang Y (2002) On the robust single machine scheduling problem. J Comb Optim 6:17–33 · Zbl 1058.90029 · doi:10.1023/A:1013333232691 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
