caa a22 4500 445838620 CHVBK 20180317145337.0 cr unu---uuuuu 170323e20110601xx s 000 0 eng 10.1007/s10951-010-0168-y doi (NATIONALLICENCE)springer-10.1007/s10951-010-0168-y Inverse scheduling: two-machine flow-shop problem [Elektronische Daten] [Peter Brucker, Natalia Shakhlevich] We study an inverse counterpart of the two-machine flow-shop scheduling problem that arises in the context of inverse optimization. While in the forward scheduling problem all parameters are given and the objective is to find job sequence(s) for which the value of the makespan is minimum, in the inverse scheduling the exact values of processing times are unknown and they should be selected within given boundaries so that pre-specified job sequence(s) become optimal. We derive necessary and sufficient conditions of optimality of a given solution for the general case of the flow-shop problem when the job sequences on the machines can be different. Based on these conditions we prove that the inverse flow-shop problem is NP-hard even in the case of the same job sequence on both machines and produce a linear programming formulation for a special case which can be solved efficiently. Springer Science+Business Media, LLC, 2010 Inverse scheduling nationallicence Flow shop scheduling nationallicence Brucker Peter Fachbereich Mathematik/Informatik, Universität Osnabrück, 49069, Osnabrück, Germany aut Shakhlevich Natalia School of Computing, University of Leeds, LS2 9JT, Leeds, UK aut Journal of Scheduling Springer US; http://www.springer-ny.com 14/3(2011-06-01), 239-256 1094-6136 14:3<239 2011 14 10951 https://doi.org/10.1007/s10951-010-0168-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10951-010-0168-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Brucker Peter Fachbereich Mathematik/Informatik, Universität Osnabrück, 49069, Osnabrück, Germany aut NATIONALLICENCE 700 1- Shakhlevich Natalia School of Computing, University of Leeds, LS2 9JT, Leeds, UK aut NATIONALLICENCE 773 0- Journal of Scheduling Springer US; http://www.springer-ny.com 14/3(2011-06-01), 239-256 1094-6136 14:3<239 2011 14 10951 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer