A Batching Machine Model for Lot Scheduling on a Single Machine

• Autorzy: Kovalyov M. Y.

Identyfikatory

DOI

10.1515/fcds-2018-0003

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

scheduling; lot-sizing; single machine; batching machine; polynomial time algorithm

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2018
• Tom: Vol. 43, No. 1
• Strony: 38--40
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Kovalyov M. Y.

• United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6, 220012, Minsk, Belarus

Bibliografia

• [1] Allahverdi A., Ng C.T., Cheng T.C.E., Kovalyov M.Y. A survey of scheduling problems with setup times or costs, European Journal of Operational Research, 187, 2008, 985-1032.
• [2] Baptiste P., Batching identical jobs, Mathematical Methods of Operations Research, 53, 2000, 355-367.
• [3] Brucker P., Scheduling algorithms, Fifth edition, Springer, 2007.
• [4] Brucker P., Gladky A., Hoogeveen H., Kovalyov M.Y., Potts C.N., Tautenhahn T., van de Velde S., Scheduling a batching machine, Journal of Scheduling, 1, 1998, 31-54.
• [5] Drexl A., Kimms A. Lot sizing and scheduling - survey and extensions, European Journal of Operational Research, 99, 1997, 221-235.
• [6] Gerstl E., Mosheiov G., A two-stage flow shop scheduling with a critical machine and batch availability, Foundations of Computing And Decision Sciences, 37, 1, 2012, 39-56.
• [7] Hou Y.-T., Yang D.-L., Kuo W.-H., Lot scheduling on a single machine, Information Processing Letters, 114, 2014, 718-722.
• [8] Karimi B., Fatemi Ghomi S.M.T., Wilson J.M. The capacitated lot sizing problem: a review of models and algorithms, Omega, 31, 2003, 365-378.
• [9] Potts C.N., Kovalyov M.Y., Scheduling with batching: a review, European Journal of Operational Research, 120, 2000, 228-249.
• [10] Potts C.N., Van Wassenhove L.N., Integrating scheduling with batching and lotsizing: A review of algorithms and complexity, Journal ofthe Operational Research Society, 43, 1992, 395-406.
• [11] Webster S.T., Baker K.R., Scheduling groups of jobs on a single machine, Operations Research, 43, 1995, 692-703.