Schedule Execution for Two-Machine Job-Shop to Minimize Makespan with Uncertain Processing Times

Yuri N. Sotskov, Natalja M. Matsveichuk and Vadzim D. Hatsura
Additional contact information
Yuri N. Sotskov: United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova Street 6, 220012 Minsk, Belarus
Natalja M. Matsveichuk: Belorussian State Agrarian Technical University, Nezavisimosti Avenue 99, 220023 Minsk, Belarus
Vadzim D. Hatsura: Belorussian State University of Informatics and Radioelectronics, P. Brovki Street 6, 220013 Minsk, Belarus

Mathematics, 2020, vol. 8, issue 8, 1-51

Abstract: This study addresses a two-machine job-shop scheduling problem with fixed lower and upper bounds on the job processing times. An exact value of the job duration remains unknown until completing the job. The objective is to minimize a schedule length (makespan). It is investigated how to best execute a schedule, if the job processing time may be equal to any real number from the given (closed) interval. Scheduling decisions consist of the off-line phase and the on-line phase of scheduling. Using the fixed lower and upper bounds on the job processing times available at the off-line phase, a scheduler may determine a minimal dominant set of schedules (minimal DS), which is based on the proven sufficient conditions for a schedule dominance. The DS optimally covers all possible realizations of the uncertain (interval) processing times, i.e., for each feasible scenario, there exists at least one optimal schedule in the minimal DS. The DS enables a scheduler to make the on-line scheduling decision, if a local information on completing some jobs becomes known. The stability approach enables a scheduler to choose optimal schedules for most feasible scenarios. The on-line scheduling algorithms have been developed with the asymptotic complexity O ( n 2 ) for n given jobs. The computational experiment shows the effectiveness of these algorithms.

Keywords: scheduling; job-shop; makespan criterion; uncertain processing times (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/8/1314/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/8/1314/ (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:8:y:2020:i:8:p:1314-:d:395994

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 ().