zbMATH — the first resource for mathematics

Scheduling two-point stochastic jobs to minimize the makespan on two parallel machines. (English) Zbl 1096.68555
Summary: Simple optimal policies are known for the problem of scheduling jobs to minimize expected makespan on two parallel machines when the job running-time distribution has a monotone hazard rate. But no such policy appears to be known in general. We investigate the general problem by adopting two-point running-time distributions, the ismplest discrete distributions not having monotone hazard rates. We derive a policy that gives an explicit, compact solution to this problem and prove its optimality. We also comment briefly on first-order extensions of the model, but each of these seems to be markedly more difficult to analyze.
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B35 Deterministic scheduling theory in operations research
Full Text: DOI
[1] Coffman, Probability in the Engineering and Informational Sciences 3 pp 89– (1989)
[2] DOI: 10.2307/1427379 · Zbl 0617.90044 · doi:10.2307/1427379
[3] Coffman, Computer and Job-Shop Scheduling Theory (1976)
[4] Bruno, Journal of the Association for Computing Machinery 28 pp 100– (1981) · Zbl 0454.68016 · doi:10.1145/322234.322242
[5] DOI: 10.2307/3212936 · Zbl 0427.90051 · doi:10.2307/3212936
[6] Glazebrook, Journal of Applied Probability 16 pp 658– (1979) · doi:10.1017/S0021900200107843
[7] DOI: 10.2307/3214023 · Zbl 0633.90026 · doi:10.2307/3214023
[8] DOI: 10.1287/mnsc.12.5.437 · doi:10.1287/mnsc.12.5.437
[9] DOI: 10.1016/0022-0000(85)90045-5 · Zbl 0583.68020 · doi:10.1016/0022-0000(85)90045-5
[10] DOI: 10.1287/mnsc.6.1.1 · Zbl 1047.90504 · doi:10.1287/mnsc.6.1.1
[11] DOI: 10.2307/3213926 · Zbl 0477.90030 · doi:10.2307/3213926
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.