The Optimality Region for a Single-Machine Scheduling Problem with Bounded Durations of the Jobs and the Total Completion Time Objective

Yuri N. Sotskov and Natalja G. Egorova
Additional contact information
Yuri N. Sotskov: United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova Street 6, 220012 Minsk, Belarus
Natalja G. Egorova: United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova Street 6, 220012 Minsk, Belarus

Mathematics, 2019, vol. 7, issue 5, 1-21

Abstract: We study a single-machine scheduling problem to minimize the total completion time of the given set of jobs, which have to be processed without job preemptions. The lower and upper bounds on the job duration is the only information that is available before scheduling. Exact values of the job durations remain unknown until the completion of the jobs. We use the optimality region for the job permutation as an optimality measure of the optimal schedule. We investigate properties of the optimality region and derive O ( n ) -algorithm for calculating a quasi-perimeter of the optimality set (i.e., the sum of lengths of the optimality segments for n given jobs). We develop a fast algorithm for finding a job permutation having the largest quasi-perimeter of the optimality set. The computational results in constructing such permutations show that they are close to the optimal ones, which can be constructed for the factual durations of all given jobs.

Keywords: single-machine scheduling; uncertain job durations; total completion time objective; optimality region (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/5/382/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/5/382/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:7:y:2019:i:5:p:382-:d:226287

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().