ABSTRACT: Denna schemaläggningsmodell är ett resultat av det verkliga problemet med schemaläggning i en textilindustri. Jobb kan vara självständigt uppdelade över flera angivna maskiner och preemption är tillåtet. Tidsfrister anges för varje jobb och arbetstillfällen antas vara tillgängliga. Det visas att minimera maximal viktad senfärdighet kan göras i polynom tid. Fallet av enhetliga maskiner (som i den berörda applikationen) kan modelleras som ett nätverk flöde och minimering av maximal senfärdighet kan göras i starkt polynom tid. Fallet av orelaterade maskiner kan lösas antingen genom generaliserade flödestekniker eller genom linjär programmering. Uppmärksamheten är också fokuserad på problemet med att hitta så kallade Obeordrade Lexico Optima, för att schemalägga icke-bindande jobb så tidigt som möjligt. Detta dokument behandlar ett schemaläggningsproblem som uppstår vid tillverkning av olika typer av tyger i en textilindustri. Problemet kännetecknas av förekomsten av flera maskiner (vävstolarna) på vilka flera arbeten måste bearbetas (de artiklar som ska vävas). Varje jobb är associerat till en bestämd delmängd av kompatibla maskiner på vilka det kan bearbetas. Ett märkligt drag i problemet är att varje jobb kan delas godtyckligt och bearbetas självständigt på dessa maskiner. Företräde är också tillåtet. Varje jobb har en tidsfrist och målet är att minimera den maximala förseningen eller den maximala viktade förseningen om jobben har tilldelats olika vikter. Det visar sig att detta problem kan lösas i polynom tid. I det allmänna fallet med icke-närstående maskiner, dvs. maskiner med olika hastigheter för olika jobb, problemet kan lösas genom linjär programmering eller genom generaliserade nätverksflöde tekniker. När det gäller enhetliga maskiner, som har praktisk relevans i den nämnda applikationen, kan en nätverksflödesmodell utvecklas med algoritmer baserade på maxflödesberäkningar. I allmänhet är de föreslagna algoritmerna svagt polynomiska. Men fallet med enhetliga maskiner och lika vikter kan lösas även i starkt polynom tid. Att minimera den maximala fördröjningen kan ge optimala lösningar med icke-bindande jobb som planeras senare än nödvändigt. För att planera alla jobb så tidigt som möjligt kommer vi också att ta itu med problemet med att hitta så kallade Unordered Lexico optimala lösningar.
Intressant är att Serafini, som motiveras av schemaläggning vävstolar i textilindustrin, ger en polynom-tidsalgoritm REF för schemaläggning oberoende jobb på icke-närstående maskiner, med tanke på att jobb kan delas godtyckligt och köras självständigt på olika maskiner.
Scheduling Jobs on Several Machines with the Job Splitting Property
{'venue': 'Oper. Res.', 'journal': 'Oper. Res.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}