<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

Publié en ligne: 16 févr. 2018

Pages: 37 - 40

Reçu: 15 sept. 2015

Accepté: 11 déc. 2017

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

Mots clés
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

Publié en ligne: 16 févr. 2018

Pages: 37 - 40

Reçu: 15 sept. 2015

Accepté: 11 déc. 2017

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

Mots clésscheduling, 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.

Mots clés
scheduling, lot-sizing, single machine, batching machine, polynomial time algorithm