Abstrakt. Schemaläggningsproblem är grundläggande för kombinatorisk optimering. Mycket arbete har gjorts på approximationsalgoritmer för NP-hårda fall, men relativt lite är känt om exakta lösningar när en del av indatan är en fast parameter. Under 2014 inledde Mnich och Wiese en systematisk studie i denna riktning. I det här dokumentet fortsätter vi denna studie och visar att flera ytterligare fall av grundläggande schemaläggningsproblem är fasta parameterdragbara för vissa naturliga parametrar. Vårt huvudsakliga verktyg är n-fold heltal programmering, en nyligen variabel dimension teknik som vi tror är mycket relevant för den parameteriserade komplexitet gemenskap. Detta papper tjänar till att visa upp och lyfta fram denna teknik. Specifikt visar vi följande fyra schemaläggning problem att vara fast-parameter dragbar, där pmax är den maximala bearbetningstiden för ett jobb och wmax är den maximala vikten av ett jobb: -Makespan minimization på likformigt besläktade maskiner (Q och Cmax) parameteriserad av pmax, -Makespan minimization på orelaterade maskiner (R och Cmax) parameteriserad av pmax och antalet typer av maskiner (definierad senare), -Samma problem, R och WjCj, parameteriserad av antalet distinkta jobbtider och antalet maskiner.
Det har varit nyligen applikationer av n-faldiga heltal programmering till schemaläggning problem i samband med parameteriserade algoritmer: Knop och Kouteck en REF visade, bland annat, att problemet med makespan minimization på orelaterade parallella maskiner, där bearbetningstiderna är beroende av både jobb och maskiner, är fast-parameter hanterbar med avseende på den maximala bearbetningstiden och antalet skilda maskintyper.
Scheduling meets n-fold Integer Programming
{'venue': 'Journal of Scheduling, 2018', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}