Communications - Scientific Letters of the University of Zilina 2013, 15(1):39-43 | DOI: 10.26552/com.C.2013.1.39-43

Mathematical Programming vs. Constraint Programming for Scheduling Problems

Ludmila Janosikova1, Tomas Hreben1
1 Department of Transportation Networks, Faculty of Management Science and Informatics, University of Zilina, Slovakia

This paper focuses on a classical scheduling problem known as the job-shop scheduling problem which is one of the most difficult problems in combinatorial optimisation. The paper presents two solution techniques, namely mathematical programming and constraint programming and compares their computational efficiency on benchmark problems. In addition, the experience with scheduling trains in a passenger railway station is presented. The computational experiments proved that the mathematical programming approach outperforms constraint programming with respect to the quality of the solution.

Keywords: mathematical programming, constraint programming, scheduling, job-shop scheduling problem

Published: March 31, 2013  Show citation

ACS AIP APA ASA Harvard Chicago Chicago Notes IEEE ISO690 MLA NLM Turabian Vancouver
Janosikova, L., & Hreben, T. (2013). Mathematical Programming vs. Constraint Programming for Scheduling Problems. Communications - Scientific Letters of the University of Zilina, 15(1), 39-43. doi: 10.26552/com.C.2013.1.39-43
Share...
Download citation
  • BibTeX (.bib)
  • Bookends (.ris)
  • EasyBib (.ris)
  • EndNote (.enw)
  • EndNote 8 (.xml)
  • ISI WoS (.isi)
  • Medlars (.medlars)
  • Mendeley (.ris)
  • MODS (.xml)
  • Papers (.ris)
  • RefWorks (.txt)
  • RefManager (.ris)
  • RIS (.ris)
  • MS Word (.xml)
  • Zotero (.ris)
    • Open full article

    References

    1. ADAMS, J., BALAS, E., ZAWACK, D.: The Shifting Bottleneck Procedure for Job Shop Scheduling. Management Science 34 (1988), pp. 391-401. Go to original source...
    2. APPLEGATE, D., COOK, W.: A Computational Study of the Job-shop Scheduling Problem. ORSA J. of Computing 3(2), 1991, pp. 149-156. Go to original source...
    3. FISHER, H., THOMPSON, G. L.: Probabilistic Learning Vombinations of Local Job-shop Scheduling Rules. J. F. Muth, G. L. Thompson (eds.), Industrial Scheduling, Prentice Hall, Englewood Cliffs, New Jersey, 1963, pp. 225-251.
    4. LAWRENCE, S.: Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques (Supplement), Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, Pennsylvania, 1984.
    5. VAESSENS, R. J. M., AARTS, E. H. L., LENSTRA, J. K.: Job Shop Scheduling by Local Search. INFORMS J. on Computing 8, 1996, pp. 302-317. Go to original source...
    6. JAIN, A. S., MEERAN, S.: Deterministic Job-shop Scheduling: Past, Present and Future, European J. of Operational Research 113 (1999), pp. 390-434. Go to original source...
    7. Xpress-Kalis Reference Manual [online]. Available from: http://www.fico.com [Accessed 10 October 2011].
    8. OR-Library [online]. Available from: http://people.brunel.ac.uk/~mastjjb/jeb/orlib/jobshopinfo.html [Accessed 19 June 2012].
    9. Gurobi Optimizer 5.0 [online]. Available from: http://www.gurobi.com [Accessed 19 June 2012].
    10. JANOSIKOVA, L., KREMPL, M.: Routing and Scheduling Trains at a Passenger Railway Station. Proc. of the 16th Intern. Sci. Conference Quantitative Methods in Economics, Bratislava, 2012. Bratislava : Ekonom, 2012, pp. 108-114.

    This is an open access article distributed under the terms of the Creative Commons Attribution 4.0 International License (CC BY 4.0), which permits use, distribution, and reproduction in any medium, provided the original publication is properly cited. No use, distribution or reproduction is permitted which does not comply with these terms.


    Return to the content