DTIC ADA1041112: Minimizing Expected Makespan in Stochastic pdf

DTIC ADA1041112: Minimizing Expected Makespan in Stochastic

More Book Details

Description of the Book:

Suppose that two machines are available to process n tasks. Each task has to be processed on both machines, the order in which this happens is immaterial. Task j has to be processed on machine 1 (2) for random time X sub j (Y sub j) with distribution F sub j (G sub j). This kind of model is usually called an Open Shop. The time that it takes to process all tasks is normally called the makespan. Every time a machine finishes processing a task the decision-maker has to decide which task to process next. Assuming that X sub j and Y sub j have the same exponential distribution we show that the optimal policy instructs the decision-maker, whenever a machine is freed, to start processing the task with longest expected processing time among the tasks still to be processed on both machines. If all tasks have been processed at least once, it does not matter what the decision-maker does, as long as he keeps the machine busy.

We then consider the case of n identical tasks and two machines with different speeds. The time it takes machine 1 (2) to process a task has distribution F(G). Both distributions F and G are assumed to be New Better than Used (NBU) and we show that the decision-maker stochastically minimizes the makespan when he always gives priority to those tasks which have not yet received processing on either machine. (Author

• Creator/s: Defense Technical Information Center
• Date: 7/1/1981
• Year: 1981
• Book Topics/Themes: DTIC Archive, Pinedo, Michael L, CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER, *STOCHASTIC PROCESSES, *DECISION MAKING, *SCHEDULING, OPTIMIZATION, RANDOM VARIABLES, PARALLEL PROCESSING, MATHEMATICAL PREDICTION, EXPONENTIAL FUNCTIONS, DISTRIBUTION FUNCTIONS, NETWORK FLOWS, THEOREMS

An excerpt captured from the PDF book