Comparing Mixed & Integer Programming vs. Constraint Programming by solving Job-Shop Scheduling Problems

Authors

  • Renata Melo e Silva de Oliveira University of State of Para (Assistent Professor III) and University of Porto ( PhD Student at FEUP)
  • Maria S. F. O. de C. Ribeiro UNIVERSITY OF PORTO (UP)

DOI:

https://doi.org/10.14807/ijmp.v6i1.262

Keywords:

Constraint Programming, Mixed an Integer Programming, Job-shop Scheduling Problem, Makespan minimization

Abstract

Scheduling is a key factor for operations management as well as for business success. From industrial Job-shop Scheduling problems (JSSP), many optimization challenges have emerged since de 1960s when improvements have been continuously required such as bottlenecks allocation, lead-time reductions and reducing response time to requests.  With this in perspective, this work aims to discuss 3 different optimization models for minimizing Makespan. Those 3 models were applied on 17 classical problems of examples JSSP and produced different outputs.  The first model resorts on Mixed and Integer Programming (MIP) and it resulted on optimizing 60% of the studied problems. The other models were based on Constraint Programming (CP) and approached the problem in two different ways: a) model CP1 is a standard IBM algorithm whereof restrictions have an interval structure that fail to solve 53% of the proposed instances, b) Model CP-2 approaches the problem with disjunctive constraints and optimized 88% of the instances. In this work, each model is individually analyzed and then compared considering: i) Optimization success performance, ii) Computational processing time, iii) Greatest Resource Utilization and, iv) Minimum Work-in-process Inventory. Results demonstrated that CP-2 presented best results on criteria i and ii, but MIP was superior on criteria iii and iv and those findings are discussed at the final section of this work.

Author Biographies

Renata Melo e Silva de Oliveira, University of State of Para (Assistent Professor III) and University of Porto ( PhD Student at FEUP)

University of Porto

Faculty of Engineering of University of Porto

Student at Doctoral Program in Industrial Engineering and Management

Maria S. F. O. de C. Ribeiro, UNIVERSITY OF PORTO (UP)

Faculty of Engineering of University of Porto

Student at Master Program in Electrical and Computers Engineering

References

ACHTERBERG, T. et al. (2008) Constraint Integer Programming : A New Approach to Integrate CP and MIP. In: [s.l: s.n.]. p. 6–20.

ACHTERBERG, T. et al. (2008b) Constraint Integer Programming : A New Approach to Integrate CP and MIP. In: PERRON, M. A.; LAURENT, T. (Ed.) Integration of AI and OR Techniques inConstraint Programming for Combinatorial Optimization Problems- 5th CAIPOR. Anais...Paris: Springer, Disponível em: http://download.springer.com/static/pdf/854/bok:978-3-540-68155-7.pdf?auth66=1401445197_6c2a7a5412d043e9d7236f3536cf3058&ext=.pdf.

ALHARKAN, I. M. (2005) Algorithms for Sequencing and Scheduling. 1. ed. Riyadih: King Saud University, p. Alharkan, Ibrahim

APPLEGATE, D.; COOK, W. (1991) A computational study of the job-shop scheduling instance. ORSA Journal on Computing, v. 3, p. 149–156.

BARTÁK, R. (1999) Constraint Programming : In Pursuit of the Holy GrailProceedings of the Week of Doctoral Students (WDS99). Anais...Prague: MatFyzPress.

BEASLY, J. E. (2014) OR-Library. Disponível em: http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/jobshop1.txt. Acesso em: 10 fev.

BERTHOLD, T.; NATURWISSENSCHAFTEN, D. DER. (2008) Constraint Integer Programming. Paris: Zuse Institute Berlin.

BOUSHAALA, A. et al. (2012) Genetic Algorithm based on Some Heuristic Rules for Job Shop Scheduling Problem3rd International Conference on Industrial Engineering and Operations Management. Anais...Istanbul,: IEE, Disponível em: http://iieom.org/ieom2012/pdfs/75.pdf.

BRADLEY, S. P.; HAX, A. C.; MAGNANTI, T. L. (1977) Mathematical Programming: An OverviewBoston: Addison-Wesley Longman, Inc., Disponível em: http://web.mit.edu/15.053/www/.

BROWN, S.; BLACKMON, K.; COUSINS, H. M. (2011) Operations Management. 1. ed. Boston: Elsevier, p. 449

COLMERAUER, A. (1990) An Introduction to Prolog III. In: LLOYD, J. W. (Ed.) Computational Logic. Anais...Brussels: Springer, Disponível em: http://link.springer.com/book/10.1007/978-3-642-76274-1.

DANTZIG, G. B. (1996) Linear ProgrammingWaPrinceton University Press. Disponível em: http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Dantzig1963-1.pdf.

DANTZIG, G. B. (2002) Linear Programming. Operations Research, v. 50, n. 1, p. 42–47, fev.

DAVE, U.; DANTZIG, G. B.; THAPA, M. N. (1998) Linear Programming-1: Introduction. 1. ed. New York: Springer-Verlag, v. 49, p. 1226

DERHY, M.-F. (2010) Integer Programming : The Branch and Bound Method. In: Linear Programming, Sensitivity Analysis & Related Topics. 1. ed. New York: Pearson Education, p. 464.

DUMITRESCU, D.; STOEAN, C.; STOEAN, R. (2007) Genetic Chromo-Dynamics for The JobShop Scheduling ProblemInternational Conference Knowledge Engineering Principles and Techniques. Anais...Romania: KEPT, Disponível em: http://www.cs.ubbcluj.ro/~studia-i/2007-kept/307-DumitrescuStoean.pdf.

FISHER, H.; THOMPSON, G. L. (1973) Probabilistic learning combinations of local job-shop scheduling rules. In: MUTH, J. F.; THOMPSON, G. L. (Ed.). Industrial Scheduling. 1. ed. New Jersey: Prentice Hall PTR, p. 128–139.

FOKKINGA, M. M. (2004) An exercise in Transformational Programming : Science of Computer Programming, v. 16, p. 19–48.

FRENCH, S. (1982) Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop. [s.l.] Ellis Horwood.

GUROBI OPTIMIZATION, I. (2014) Gurobi Optimization. Disponível em: <http://www.gurobi.com/resources/getting-started/mip-basics>. Acesso em: 31 maio.

IBM. (2014) IBM ILOG CPLEX Optimization Studio. Disponível em: http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r6/index.jsp?topic=/ilog.odms.ide.help/OPL_Studio/opllangref/topics/opl_langref_scheduling_sequence.html. Acesso em: 5 out.

JAFFART, J.; LASSEZ, J. (1987) Constraint Logic Programming POPL ’87 Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages. Anais...New York: Spriger, Disponível em: http://dl.acm.org/citation.cfm?id=41635.

KAUFMANN, A. (1977) Integer and Mixed Programming: Theory and Applications -. 1. ed. Pari: Academic Press Limited, p. 390

LITTLE, J.; TSANG, E. (1995) Foundations of Constraint Satisfaction. 2. ed. San Diegoeg: Academic Press Limited, v. 46, p. 666

MASTROLILLI, M. ; G. L. M. (2000) Effective Neighborhood Functions for the Flexible Job Shop Problem: Appendix (2000). Journal of Scheduling, v. 3, n. 1, p. 3–20.

MATOUSEK, J.; GARTNER, B. (2007) Understanding and Using Linear Programming. 1. ed. Berlim: Springer-Verlag, p. 229

OPL, I. B. M. I. (2009) Optimization modeling with IBM ILOG OPLIBM, Disponível em: https://www.google.pt/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0CC8QFjAA&url=http://lak.informatik.uni-freiburg.de/lak_teaching/ws11_12/combopt/cplex/Workbook.pdf&ei=aE6KU4jCL6Kg0QXq8oCoDA&usg=AFQjCNFOVRPUBVjWh5wDN140Sx-ApTHVdg&sig2=ypBxl3aZGj0QnuLIH5Al0w&bvm=bv.67720277,d.d2k

SALVAGNI, D. (2008) And Programming Heuristic Methods for Constraint for Mixed Integer Linear Programs Mixed. [s.l.] UNIVERSIT `A DEGLI STUDI DI PADOVA.

SLACK, N.; CHAMBERS, S.; JOHNSTON, R. (2010) Operations Management with MyOMLab. 6. ed. New Jersey: Prentice Hall PTR, p. 728

SLACK, N.; LEWIS, M. (2009) Operations Strategy. 2. ed. Harlow: Prentice Hall PTR, p. 528

TAHA, H. A. (2007) Operations Research: An Introduction. 8th. ed. London: Pearson Education.

VANDERBEI, R. J. (1998) Linear Programming: Foundations and Extensions. New York: Springer, v. 49, p. 93–98

VANDERBEI, R. J. (2008) INTEGER PROGRAMMING foundations and extension. 3rd. ed. new: Springer, p. 469

WALLACE, M. (1996) Practical applications of constraint programming. Constraints, v. 1, n. 1-2, p. 139–168, set.

ZHOU, J. (1996) A constraint program for solving the job-shop problem. Principles and Practice of Constraint Programming — CP96 Lecture Notes in Computer Science, v. 1118, p. 1–15.

Downloads

Published

2015-03-01