IDEAS home Printed from https://ideas.repec.org/a/eee/proeco/v124y2010i2p453-462.html
   My bibliography  Save this article

Efficient overtime planning in packing shops with lines of identical manning

Author

Listed:
  • Lagodimos, A.G.
  • Mihiotis, A.N.

Abstract

We consider a capacity planning problem arising at the packaging stage in many process industries. Termed economic manpower shift planning with overtime (EMSP-O), it seeks the manpower and overtime to be planned at each workday shift so that production targets for all packing lines are met at minimum cost. The problem was previously modelled as an ILP and its solution explored. Here we present a new EMSP-O model that relaxes a restrictive assumption of the original model. We show that the relaxed EMSP-O is NP-hard and focus on the special case where all lines have identical manning. For this case, we establish properties of the optimal solution and show that, with no overtime constraints, an O(N log N) algorithm can find an optimal solution. With overtime constraints, the algorithm effectively constitutes a heuristic. Computations and comparisons with a commercial optimizer for two- and three-shift problems (as found in practice) were performed. Results demonstrate the algorithm efficiency which, except for very tight overtime constraints, reaches an optimum at high speed.

Suggested Citation

  • Lagodimos, A.G. & Mihiotis, A.N., 2010. "Efficient overtime planning in packing shops with lines of identical manning," International Journal of Production Economics, Elsevier, vol. 124(2), pages 453-462, April.
    • Handle: RePEc:eee:proeco:v:124:y:2010:i:2:p:453-462
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0925-5273(09)00455-1
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Corominas, Albert & Lusa, Amaia & Pastor, Rafael, 2007. "Using a MILP model to establish a framework for an annualised hours agreement," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1495-1506, March.
    2. Lodi, Andrea & Martello, Silvano & Monaci, Michele, 2002. "Two-dimensional packing problems: A survey," European Journal of Operational Research, Elsevier, vol. 141(2), pages 241-252, September.
    3. Lusa, Amaia & Pastor, Rafael & Corominas, Albert, 2008. "Determining the most appropriate set of weekly working hours for planning annualised working time," International Journal of Production Economics, Elsevier, vol. 111(2), pages 697-706, February.
    4. Easton, F. F. & Rossin, D. F., 1997. "Overtime schedules for full-time service workers," Omega, Elsevier, vol. 25(3), pages 285-299, June.
    5. de Kok, Ton G., 2000. "Capacity allocation and outsourcing in a process industry," International Journal of Production Economics, Elsevier, vol. 68(3), pages 229-239, December.
    6. A Corominas & A Lusa & R Pastor, 2002. "Using MILP to plan annualised working hours," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(10), pages 1101-1108, October.
    7. Venkataraman, R. & Brusco, M. J., 1996. "An integrated analysis of nurse staffing and scheduling policies," Omega, Elsevier, vol. 24(1), pages 57-71, February.
    8. Buxey, Geoff, 1995. "A managerial perspective on aggregate planning," International Journal of Production Economics, Elsevier, vol. 41(1-3), pages 127-133, October.
    9. Hertz, Alain & Lahrichi, Nadia & Widmer, Marino, 2010. "A flexible MILP model for multiple-shift workforce planning under annualized hours," European Journal of Operational Research, Elsevier, vol. 200(3), pages 860-873, February.
    10. Su, Ling-Huey & Lien, Chun-Yuan, 2009. "Scheduling parallel machines with resource-dependent processing times," International Journal of Production Economics, Elsevier, vol. 117(2), pages 256-266, February.
    11. Lagodimos, A.G. & Mihiotis, A.N., 2006. "Overtime vs. regular shift planning decisions in packing shops," International Journal of Production Economics, Elsevier, vol. 101(2), pages 246-258, June.
    12. Croci, F. & Perona, M. & Pozzetti, A., 2000. "Work-force management in automated assembly systems," International Journal of Production Economics, Elsevier, vol. 64(1-3), pages 243-255, March.
    13. Claassen, G. D. H. & van Beek, P., 1993. "Planning and scheduling packaging lines in food industry," European Journal of Operational Research, Elsevier, vol. 70(2), pages 150-158, October.
    14. Van Dam, Peter & Gaalman, Gerard J. C. & Sierksma, Gerard, 1998. "Designing scheduling systems for packaging in process industries: A tobacco company case," International Journal of Production Economics, Elsevier, vol. 56(1), pages 649-659, September.
    15. Lagodimos, A. G. & Leopoulos, V., 2000. "Greedy heuristic algorithms for manpower shift planning," International Journal of Production Economics, Elsevier, vol. 68(1), pages 95-106, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Lagodimos, A.G. & Mihiotis, A.N., 2006. "Overtime vs. regular shift planning decisions in packing shops," International Journal of Production Economics, Elsevier, vol. 101(2), pages 246-258, June.
    2. Corominas, Albert & Lusa, Amaia & Olivella, Jordi, 2012. "A detailed workforce planning model including non-linear dependence of capacity on the size of the staff and cash management," European Journal of Operational Research, Elsevier, vol. 216(2), pages 445-458.
    3. Lusa, Amaia & Pastor, Rafael & Corominas, Albert, 2008. "Determining the most appropriate set of weekly working hours for planning annualised working time," International Journal of Production Economics, Elsevier, vol. 111(2), pages 697-706, February.
    4. Min Wang & Guoshan Liu & Xinyu Lin, 2022. "Dynamic Optimization of the Multi-Skilled Resource-Constrained Project Scheduling Problem with Uncertainty in Resource Availability," Mathematics, MDPI, vol. 10(17), pages 1-20, August.
    5. Hertz, Alain & Lahrichi, Nadia & Widmer, Marino, 2010. "A flexible MILP model for multiple-shift workforce planning under annualized hours," European Journal of Operational Research, Elsevier, vol. 200(3), pages 860-873, February.
    6. Egbert Veen & Erwin Hans & Bart Veltman & Leo Berrevoets & Hubert Berden, 2015. "A case study of cost-efficient staffing under annualized hours," Health Care Management Science, Springer, vol. 18(3), pages 279-288, September.
    7. De Bruecker, Philippe & Van den Bergh, Jorne & Beliën, Jeroen & Demeulemeester, Erik, 2015. "Workforce planning incorporating skills: State of the art," European Journal of Operational Research, Elsevier, vol. 243(1), pages 1-16.
    8. Van den Bergh, Jorne & Beliën, Jeroen & De Bruecker, Philippe & Demeulemeester, Erik & De Boeck, Liesje, 2013. "Personnel scheduling: A literature review," European Journal of Operational Research, Elsevier, vol. 226(3), pages 367-385.
    9. Corominas, Albert & Pastor, Rafael & Rodriguez, Ericka, 2006. "Rotational allocation of tasks to multifunctional workers in a service industry," International Journal of Production Economics, Elsevier, vol. 103(1), pages 3-9, September.
    10. Francisco Trespalacios & Ignacio E. Grossmann, 2017. "Symmetry breaking for generalized disjunctive programming formulation of the strip packing problem," Annals of Operations Research, Springer, vol. 258(2), pages 747-759, November.
    11. Andrzej Kozik, 2017. "Handling precedence constraints in scheduling problems by the sequence pair representation," Journal of Combinatorial Optimization, Springer, vol. 33(2), pages 445-472, February.
    12. Anshu Ranjan & Pramod Khargonekar & Sartaj Sahni, 2017. "Offline first-fit decreasing height scheduling of power loads," Journal of Scheduling, Springer, vol. 20(5), pages 527-542, October.
    13. Russo, Mauro & Sforza, Antonio & Sterle, Claudio, 2013. "An improvement of the knapsack function based algorithm of Gilmore and Gomory for the unconstrained two-dimensional guillotine cutting problem," International Journal of Production Economics, Elsevier, vol. 145(2), pages 451-462.
    14. Jens Brunner & Jonathan Bard & Rainer Kolisch, 2009. "Flexible shift scheduling of physicians," Health Care Management Science, Springer, vol. 12(3), pages 285-305, September.
    15. Bayliss, Christopher & Currie, Christine S.M. & Bennell, Julia A. & Martinez-Sykora, Antonio, 2021. "Queue-constrained packing: A vehicle ferry case study," European Journal of Operational Research, Elsevier, vol. 289(2), pages 727-741.
    16. López-Camacho, Eunice & Terashima-Marín, Hugo & Ochoa, Gabriela & Conant-Pablos, Santiago Enrique, 2013. "Understanding the structure of bin packing problems through principal component analysis," International Journal of Production Economics, Elsevier, vol. 145(2), pages 488-499.
    17. W. D. D. Madhavee & N. Saldin & U. C. Vaidyarathna & C. J. Jayawardene, 2018. "A Practical Application of the Generalized Cutting Stock Algorithm," Academic Journal of Applied Mathematical Sciences, Academic Research Publishing Group, vol. 4(3), pages 15-21, 03-2018.
    18. Peters, Emmanuel & de Matta, Renato & Boe, Warren, 2007. "Short-term work scheduling with job assignment flexibility for a multi-fleet transport system," European Journal of Operational Research, Elsevier, vol. 180(1), pages 82-98, July.
    19. A Ghanmi & R H A D Shaw, 2008. "Modelling and analysis of Canadian Forces strategic lift and pre-positioning options," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(12), pages 1591-1602, December.
    20. Elina Rönnberg & Torbjörn Larsson, 2010. "Automating the self-scheduling process of nurses in Swedish healthcare: a pilot study," Health Care Management Science, Springer, vol. 13(1), pages 35-53, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:proeco:v:124:y:2010:i:2:p:453-462. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/ijpe .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.