BulDML at Institute of Mathematics and Informatics >
International Journal ITA >
2007 >
Volume 14 Number 2 >

Please use this identifier to cite or link to this item:

Title: Realization of an Optimal Schedule for the Two-machine Flow-Shop with Interval Job Processing Times
Authors: Leshchenko, Natalja
Sotskov, Yuri
Keywords: Scheduling
Issue Date: 2007
Publisher: Institute of Information Theories and Applications FOI ITHEA
Abstract: Non-preemptive two-machine flow-shop scheduling problem with uncertain processing times of n jobs is studied. In an uncertain version of a scheduling problem, there may not exist a unique schedule that remains optimal for all possible realizations of the job processing times. We find necessary and sufficient conditions (Theorem 1) when there exists a dominant permutation that is optimal for all possible realizations of the job processing times. Our computational studies show the percentage of the problems solvable under these conditions for the cases of randomly generated instances with n ≤ 100 . We also show how to use additional information about the processing times of the completed jobs during optimal realization of a schedule (Theorems 2 – 4). Computational studies for randomly generated instances with n ≤ 50 show the percentage of the two- machine flow-shop scheduling problems solvable under the sufficient conditions given in Theorems 2 – 4.
ISSN: 1313-0463
Appears in Collections:Volume 14 Number 2

Files in This Item:

File Description SizeFormat
ijita14-2-p12.pdf142.21 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0!   Creative Commons License