<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

Online veröffentlicht: 16. Feb. 2018

Seitenbereich: 37 - 40

Eingereicht: 15. Sept. 2015

Akzeptiert: 11. Dez. 2017

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

Schlüsselwörter
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

Online veröffentlicht: 16. Feb. 2018

Seitenbereich: 37 - 40

Eingereicht: 15. Sept. 2015

Akzeptiert: 11. Dez. 2017

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

Schlüsselwörterscheduling, 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.

Schlüsselwörter
scheduling, lot-sizing, single machine, batching machine, polynomial time algorithm