<abstract xmlns="http://www.w3.org/1999/xhtml"><p>A recently introduced lot scheduling problem is considered. It is to find a partition of jobs of <italic>n</italic> orders into lots and to sequence these lots on a single machine so that the total average completion time of the orders is minimized. A simple <italic>O</italic>(<italic>n</italic> log <italic>n</italic>) time algorithm is presented for this problem in the literature, with a relatively sophisticated proof of its optimality. We show that modeling this problem as a classic batching machine problem makes its optimal solution obvious.</p></abstract>

A recently introduced lot scheduling problem is considered. It is to find a partition of jobs of n orders into lots and to sequence these lots on a single machine so that the total average completion time of the orders is minimized. A simple O(n log n) time algorithm is presented for this problem in the literature, with a relatively sophisticated proof of its optimality. We show that modeling this problem as a classic batching machine problem makes its optimal solution obvious.

A Batching Machine Model for Lot Scheduling on a Single Machine

United Institute of Informatics Problems, National Academy of Sciences of Belarus

Foundations of Computing and Decision Sciences

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"A Batching Machine Model for Lot Scheduling on a Single Machine"}

A recently introduced lot scheduling problem is considered. It is to find a partition of jobs of n orders into lots and to sequence these lots on a single...

A Batching Machine Model for Lot Scheduling on a Single Machine

Publicado en línea: 16 feb 2018

Páginas: 37 - 40

Recibido: 15 sept 2015

Aceptado: 11 dic 2017

DOI: https://doi.org/10.1515/fcds-2018-0003

Palabras clave
scheduling, lot-sizing, single machine, batching machine, polynomial time algorithm

© 2018 Mikhail Y. Kovalyov, published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

A Batching Machine Model for Lot Scheduling on a Single Machine

Publicado en línea: 16 feb 2018

Páginas: 37 - 40

Recibido: 15 sept 2015

Aceptado: 11 dic 2017

DOI: https://doi.org/10.1515/fcds-2018-0003

Palabras clavescheduling, lot-sizing, single machine, batching machine, polynomial time algorithm

© 2018 Mikhail Y. Kovalyov, published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Palabras clave
scheduling, lot-sizing, single machine, batching machine, polynomial time algorithm