Inverse scheduling: two-machine flow-shop problem

DC FieldValueLanguage
dc.contributor.authorBrucker, Peter
dc.contributor.authorShakhlevich, Natalia V.
dc.date.accessioned2021-12-23T16:07:06Z-
dc.date.available2021-12-23T16:07:06Z-
dc.date.issued2011
dc.identifier.issn10946136
dc.identifier.urihttps://osnascholar.ub.uni-osnabrueck.de/handle/unios/7712-
dc.description.abstractWe 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.
dc.description.sponsorshipEPSRCUK Research & Innovation (UKRI)Engineering & Physical Sciences Research Council (EPSRC) [EP/D059518]; Engineering and Physical Sciences Research CouncilUK Research & Innovation (UKRI)Engineering & Physical Sciences Research Council (EPSRC) [EP/D059518/1] Funding Source: researchfish; EPSRCUK Research & Innovation (UKRI)Engineering & Physical Sciences Research Council (EPSRC) [EP/D059518/1] Funding Source: UKRI; This research was supported by the EPSRC funded project EP/D059518 ``Inverse Optimization in Application to Scheduling''. We would like to thank anonymous referees for providing useful recommendations which helped in improving the presentation of the material.
dc.language.isoen
dc.publisherSPRINGER
dc.relation.ispartofJOURNAL OF SCHEDULING
dc.subjectALGORITHMS
dc.subjectEngineering
dc.subjectEngineering, Manufacturing
dc.subjectFlow shop scheduling
dc.subjectInverse scheduling
dc.subjectOperations Research & Management Science
dc.subjectOPTIMIZATION
dc.titleInverse scheduling: two-machine flow-shop problem
dc.typejournal article
dc.identifier.doi10.1007/s10951-010-0168-y
dc.identifier.isiISI:000290684700003
dc.description.volume14
dc.description.issue3, SI
dc.description.startpage239
dc.description.endpage256
dc.contributor.orcid0000-0002-5225-4008
dc.identifier.eissn10991425
dc.publisher.place233 SPRING ST, NEW YORK, NY 10013 USA
dcterms.isPartOf.abbreviationJ. Sched.
dcterms.oaStatusGreen Accepted
crisitem.author.deptUniversität Osnabrück-
crisitem.author.orcid0000-0002-5225-4008-
crisitem.author.netidShNa001-
Show simple item record

Page view(s)

5
Last Week
0
Last month
1
checked on Apr 23, 2024

Google ScholarTM

Check

Altmetric