文章基本信息

标题：The Optimality Box and Region for Single-Machine Scheduling of a Set of Jobs with Uncertain Durations
本地全文：下载
作者：Yuri N. Sotskov ; Natalja G. Egorova ; Frank Werner 等
期刊名称：IFAC PapersOnLine
印刷版ISSN：2405-8963
出版年度：2019
卷号：52
期号：13
页码：88-93
DOI：10.1016/j.ifacol.2019.11.141
语种：English
出版社：Elsevier
摘要：A set of jobs has to be processed on a single machine without preemptions of a job. The exact value of the job processing time (duration) is unknown until the completion of the job. Lower and upper bounds on the job duration are known before scheduling. The problem is to minimize total completion time of the given jobs. We apply a stability approach to this scheduling problem and introduce an optimality region for a job permutation as an optimality measure of the schedule. We investigate properties of the optimality region and deriveO(n)algorithms for calculating the relative perimeter of the optimality region (the sum of the relative optimality sets of thenjobs) for a fixed job permutation. We present computational results for a comparison of the relative perimeters of the optimality regions for the mid-point permutations, the lower-bound permutations, the upper-bound permutations and the permutations having the largest optimality box.
关键词：KeywordsSchedulingSingle machineTotal completion timeUncertain durations