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

Article Sidebar

PDF HTML
Published: Mar 1, 2015
DOI: https://doi.org/10.14807/ijmp.v6i1.262
Keywords:
Constraint Programming Mixed an Integer Programming Job-shop Scheduling Problem Makespan minimization

Main Article Content

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)

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.

Downloads

Download data is not yet available.

Article Details

Issue
Vol. 6 No. 1 (2015): Independent Journal of Management & Production
Section
Articles

1. Proposal of Policy for Free Access Periodics

Authors whom publish in this magazine should agree to the following terms:

a. Authors should keep the copyrights and grant to the magazine the right of the first publication, with the work simultaneously permitted under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 that allows the sharing of the work with recognition of the authorship of the work and initial publication in this magazine.

b. Authors should have authorization for assuming additional contracts separately, for non-exclusive distribution of the version of the work published in this magazine (e.g.: to publish in an institutional repository or as book chapter), with recognition of authorship and initial publication in this magazine.

c. Authors should have permission and should be stimulated to publish and to distribute its work online (e.g.: in institutional repositories or its personal page) to any point before or during the publishing process, since this can generate productive alterations, as well as increasing the impact and the citation of the published work (See The Effect of Free Access).

 

Proposal of Policy for Periodic that offer Postponed Free Access

Authors whom publish in this magazine should agree to the following terms:

 

a. Authors should keep the copyrights and grant to the magazine the right of the first publication, with the work simultaneously permitted under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 [SPECIFY TIME HERE] after the publication, allowing the sharing of the work with recognition of the authorship of the work and initial publication in this magazine.

 

b. Authors should have authorization for assuming additional contracts separately, for non-exclusive distribution of the version of the work published in this magazine (e.g.: to publish in institutional repository or as book chapter), with recognition of authorship and initial publication in this magazine.

 

c. Authors should have permission and should be stimulated to publish and to distribute its work online (e.g.: in institutional repositories or its personal page) to any point before or during the publishing process, since this can generate productive alterations, as well as increasing the impact and the citation of the published work (See The Effect of Free Access).


d. They allow some kind of open dissemination. Authors can disseminate their articles in open access, but with specific conditions imposed by the editor that are related to:
     Version of the article that can be deposited in the repository:
           Pre-print: before being reviewed by pairs.
           Post-print: once reviewed by pairs, which can be:
                  The version of the author that has been accepted for publication.
                  The editor's version, that is, the article published in the magazine.
           At which point the article can be made accessible in an open manner: before it is published in the magazine, immediately afterwards or if a period of seizure is required, which can range from six months to several years.
      Where to leave open: on the author's personal web page, only departmental websites, the repository of the institution, the file of the research funding agency, among others.

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

Crossref
Scopus
Google Scholar
Europe PMC

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.