On batch scheduling of jobs with stochastic service times and cost structures on a single server

摘要

Jobs are modeled as decision trees of tasks in this paper. With each task is associateda joint probability distribution governing the deferral cost of the task, the execution time of the task, and a pointer to the descendant task next to be executed in the job. For a collection of jobs, an efficient algorithm is found and analyzed for sequencing jobs so as to minimize the total expected cost.