Vi studerar problemen med schemaläggning jobb, med olika utgivningsdatum och lika behandlingstider, på två typer av batching maskiner. Alla jobb med samma batchstart och slutförs samtidigt. På en seriell batch maskin, längden på en batch motsvarar summan av bearbetningstiderna för sina jobb och, när en ny batch börjar, en konstant installationstid s inträffar. På en parallell batch maskin, det finns som mest b jobb per batch och längden på en batch är den största bearbetningstiden för sina jobb. Vi visar att i båda miljöer, för en stor klass av så kallade "ordnade" objektiva funktioner, är problemen polynomiskt lösliga genom dynamisk programmering. Detta gör att vi kan härleda att problemen där målet är att minimera det viktade antalet sena jobb, eller den viktade flödestiden, eller den totala senfärdigheten, eller den maximala senfärdigheten är polynom. Med andra ord visar vi att 1-p-batch, b < n, r i, p i = p-f och 1-s-batch, r i, p i = p-f, är polynomial för F  på { w i U i, w i C i, T i, T max }. Dessa problems komplexitet var okänd tidigare.
Baptiste REF studerade problemen med schemaläggning jobb med olika frisättningstider och lika behandlingstider på en sats bearbetningsmaskin och visade att minimering av det viktade antalet tardy jobb, den totala viktade avslutningstiden, den totala senfärdigheten och den maximala tardighet är polynomiskt solvable.
Batching Identical Jobs
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}