Inverse scheduling: two-machine flow-shop problem
DC Element | Wert | Sprache |
---|---|---|
dc.contributor.author | Brucker, Peter | |
dc.contributor.author | Shakhlevich, Natalia V. | |
dc.date.accessioned | 2021-12-23T16:07:06Z | - |
dc.date.available | 2021-12-23T16:07:06Z | - |
dc.date.issued | 2011 | |
dc.identifier.issn | 10946136 | |
dc.identifier.uri | https://osnascholar.ub.uni-osnabrueck.de/handle/unios/7712 | - |
dc.description.abstract | 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. | |
dc.description.sponsorship | EPSRCUK 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.iso | en | |
dc.publisher | SPRINGER | |
dc.relation.ispartof | JOURNAL OF SCHEDULING | |
dc.subject | ALGORITHMS | |
dc.subject | Engineering | |
dc.subject | Engineering, Manufacturing | |
dc.subject | Flow shop scheduling | |
dc.subject | Inverse scheduling | |
dc.subject | Operations Research & Management Science | |
dc.subject | OPTIMIZATION | |
dc.title | Inverse scheduling: two-machine flow-shop problem | |
dc.type | journal article | |
dc.identifier.doi | 10.1007/s10951-010-0168-y | |
dc.identifier.isi | ISI:000290684700003 | |
dc.description.volume | 14 | |
dc.description.issue | 3, SI | |
dc.description.startpage | 239 | |
dc.description.endpage | 256 | |
dc.contributor.orcid | 0000-0002-5225-4008 | |
dc.identifier.eissn | 10991425 | |
dc.publisher.place | 233 SPRING ST, NEW YORK, NY 10013 USA | |
dcterms.isPartOf.abbreviation | J. Sched. | |
dcterms.oaStatus | Green Accepted | |
crisitem.author.dept | Universität Osnabrück | - |
crisitem.author.orcid | 0000-0002-5225-4008 | - |
crisitem.author.netid | ShNa001 | - |
Seitenaufrufe
5
Letzte Woche
0
0
Letzter Monat
0
0
geprüft am 02.06.2024