IDEAS home Printed from https://ideas.repec.org/a/spr/comgts/v14y2017i1d10.1007_s10287-016-0262-5.html
   My bibliography  Save this article

Flow-based formulations for operational fixed interval scheduling problems with random delays

Author

Listed:
  • Martin Branda

    (Charles University in Prague)

  • Štěpán Hájek

    (Charles University in Prague)

Abstract

We deal with operational fixed interval scheduling problem with random delays in job processing times. We formulate two stochastic programming problems. In the first problem with a probabilistic objective, all jobs are processed on available machines and the goal is to obtain a schedule with the highest attainable reliability. The second problem is to select a subset of jobs with the highest reward under a chance constraint ensuring feasibility of the schedule with a prescribed probability. We assume that the multivariate distribution of delays follows an Archimedean copula, whereas there are no restrictions on marginal distributions. We introduce new deterministic integer linear reformulations based on flow problems. We compare the formulations with the extended robust coloring problem, which was shown to be a deterministic equivalent to the stochastic programming problem with probabilistic objective by Branda et al. (Comput Ind Eng 93:45–54, 2016). In the numerical study, we report average computational times necessary to solve a large number of simulated instances. It turns out that the new flow-based formulation helps to solve the FIS problems considerably faster than the other one.

Suggested Citation

  • Martin Branda & Štěpán Hájek, 2017. "Flow-based formulations for operational fixed interval scheduling problems with random delays," Computational Management Science, Springer, vol. 14(1), pages 161-177, January.
    • Handle: RePEc:spr:comgts:v:14:y:2017:i:1:d:10.1007_s10287-016-0262-5
    DOI: 10.1007/s10287-016-0262-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10287-016-0262-5
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10287-016-0262-5?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    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. Peter Kall & János Mayer, 2011. "Stochastic Linear Programming," International Series in Operations Research and Management Science, Springer, edition 2, number 978-1-4419-7729-8, September.
    2. Parisio, Alessandra & Neil Jones, Colin, 2015. "A two-stage stochastic programming approach to employee scheduling in retail outlets with uncertain demand," Omega, Elsevier, vol. 53(C), pages 97-103.
    3. Leo G. Kroon & Marc Salomon & Luk N. Van Wassenhove, 1997. "Exact and Approximation Algorithms for the Tactical Fixed Interval Scheduling Problem," Operations Research, INFORMS, vol. 45(4), pages 624-638, August.
    4. Brucker, Peter & Qu, Rong & Burke, Edmund, 2011. "Personnel scheduling: Models and complexity," European Journal of Operational Research, Elsevier, vol. 210(3), pages 467-473, May.
    5. Kroon, Leo G. & Salomon, Marc & Van Wassenhove, Luk N., 1995. "Exact and approximation algorithms for the operational fixed interval scheduling problem," European Journal of Operational Research, Elsevier, vol. 82(1), pages 190-205, April.
    6. Darinka Dentcheva & Gabriela Martinez, 2012. "Augmented Lagrangian method for probabilistic optimization," Annals of Operations Research, Springer, vol. 200(1), pages 109-130, November.
    7. Chi To Ng & Tai Chiu Edwin Cheng & Andrei M Bandalouski & Mikhail Y Kovalyov & Sze Sing Lam, 2014. "A graph-theoretic approach to interval scheduling on dedicated unrelated parallel machines," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 65(10), pages 1571-1579, October.
    8. I. Bremer & R. Henrion & A. Möller, 2015. "Probabilistic constraints via SQP solver: application to a renewable energy management problem," Computational Management Science, Springer, vol. 12(3), pages 435-459, July.
    9. Feng Shan & Liwei Zhang & Xiantao Xiao, 2014. "A Smoothing Function Approach to Joint Chance-Constrained Programs," Journal of Optimization Theory and Applications, Springer, vol. 163(1), pages 181-199, October.
    10. Kovalyov, Mikhail Y. & Ng, C.T. & Cheng, T.C. Edwin, 2007. "Fixed interval scheduling: Models, applications, computational complexity and algorithms," European Journal of Operational Research, Elsevier, vol. 178(2), pages 331-342, April.
    11. J. Arturo Castillo-Salazar & Dario Landa-Silva & Rong Qu, 2016. "Workforce scheduling and routing problems: literature survey and computational study," Annals of Operations Research, Springer, vol. 239(1), pages 39-67, April.
    12. René Henrion & Cyrille Strugarek, 2011. "Convexity of Chance Constraints with Dependent Random Variables: The Use of Copulae," International Series in Operations Research & Management Science, in: Marida Bertocchi & Giorgio Consigli & Michael A. H. Dempster (ed.), Stochastic Optimization Methods in Finance and Energy, edition 1, chapter 0, pages 427-439, Springer.
    13. Patrizia Beraldi & Maria Bruni, 2010. "An exact approach for solving integer problems under probabilistic constraints with random technology matrix," Annals of Operations Research, Springer, vol. 177(1), pages 127-137, June.
    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. Slotnick, Susan A., 2011. "Order acceptance and scheduling: A taxonomy and review," European Journal of Operational Research, Elsevier, vol. 212(1), pages 1-11, July.
    2. Lukáš Adam & Martin Branda, 2016. "Nonlinear Chance Constrained Problems: Optimality Conditions, Regularization and Solvers," Journal of Optimization Theory and Applications, Springer, vol. 170(2), pages 419-436, August.
    3. Yim, Seho & Hong, Sung-Pil & Park, Myoung-Ju & Chung, Yerim, 2022. "Inverse interval scheduling via reduction on a single machine," European Journal of Operational Research, Elsevier, vol. 303(2), pages 541-549.
    4. Lukáš Adam & Martin Branda & Holger Heitsch & René Henrion, 2020. "Solving joint chance constrained problems using regularization and Benders’ decomposition," Annals of Operations Research, Springer, vol. 292(2), pages 683-709, September.
    5. Bekki, Özgün BarIs & Azizoglu, Meral, 2008. "Operational fixed interval scheduling problem on uniform parallel machines," International Journal of Production Economics, Elsevier, vol. 112(2), pages 756-768, April.
    6. Lee, Soonhui & Turner, Jonathan & Daskin, Mark S. & Homem-de-Mello, Tito & Smilowitz, Karen, 2012. "Improving fleet utilization for carriers by interval scheduling," European Journal of Operational Research, Elsevier, vol. 218(1), pages 261-269.
    7. Wim Ackooij, 2017. "A comparison of four approaches from stochastic programming for large-scale unit-commitment," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 5(1), pages 119-147, March.
    8. Xiaodi Bai & Jie Sun & Xiaojin Zheng, 2021. "An Augmented Lagrangian Decomposition Method for Chance-Constrained Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1056-1069, July.
    9. Türsel Eliiyi, Deniz & Azizoglu, Meral, 2011. "Heuristics for operational fixed job scheduling problems with working and spread time constraints," International Journal of Production Economics, Elsevier, vol. 132(1), pages 107-121, July.
    10. Antoon W.J. Kolen & Jan Karel Lenstra & Christos H. Papadimitriou & Frits C.R. Spieksma, 2007. "Interval scheduling: A survey," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(5), pages 530-543, August.
    11. Michel Minoux & Riadh Zorgati, 2019. "Sharp upper and lower bounds for maximum likelihood solutions to random Gaussian bilateral inequality systems," Journal of Global Optimization, Springer, vol. 75(3), pages 735-766, November.
    12. Maria Fleischer Fauske & Erlend Øby Hoff, 2016. "From F-16 to F-35: Optimizing the Training of Pilots in the Royal Norwegian Air Force," Interfaces, INFORMS, vol. 46(4), pages 326-333, August.
    13. Janiak, Adam & Janiak, Władysław A. & Krysiak, Tomasz & Kwiatkowski, Tomasz, 2015. "A survey on scheduling problems with due windows," European Journal of Operational Research, Elsevier, vol. 242(2), pages 347-357.
    14. Zhang, Xiandong & (Yale) Gong, Yeming & Zhou, Shuyu & de Koster, René & van de Velde, Steef, 2016. "Increasing the revenue of self-storage warehouses by optimizing order scheduling," European Journal of Operational Research, Elsevier, vol. 252(1), pages 69-78.
    15. Miguel A. Lejeune & François Margot, 2016. "Solving Chance-Constrained Optimization Problems with Stochastic Quadratic Inequalities," Operations Research, INFORMS, vol. 64(4), pages 939-957, August.
    16. Caselli, Giulia & Delorme, Maxence & Iori, Manuel, 2022. "Integer linear programming for the Tutor Allocation Problem : A practical case in a British University," Other publications TiSEM 983593a6-c17d-4b87-8ee1-a, Tilburg University, School of Economics and Management.
    17. Borgonjon, Tessa & Maenhout, Broos, 2022. "An exact approach for the personnel task rescheduling problem with task retiming," European Journal of Operational Research, Elsevier, vol. 296(2), pages 465-484.
    18. Young-Chae Hong & Amy Cohn & Stephen Gorga & Edmond O’Brien & William Pozehl & Jennifer Zank, 2019. "Using Optimization Techniques and Multidisciplinary Collaboration to Solve a Challenging Real-World Residency Scheduling Problem," Interfaces, INFORMS, vol. 49(3), pages 201-212, May.
    19. Beltran-Royo, C., 2017. "Two-stage stochastic mixed-integer linear programming: The conditional scenario approach," Omega, Elsevier, vol. 70(C), pages 31-42.
    20. Smirnov, Dmitry & Huchzermeier, Arnd, 2020. "Analytics for labor planning in systems with load-dependent service times," European Journal of Operational Research, Elsevier, vol. 287(2), pages 668-681.

    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:spr:comgts:v:14:y:2017:i:1:d:10.1007_s10287-016-0262-5. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.