Periodicity.: January - March 2015
e-ISSN......: 2236-269X
Cover Image

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

Renata Melo e Silva de Oliveira, Maria S. F. O. de C. Ribeiro

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.

Keywords


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

Full Text:

PDF HTML

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: . 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.




DOI: http://dx.doi.org/10.14807/ijmp.v6i1.262

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Copyright (c)



LIBRARIES BY

Logo Gaudeamus

Logo INDIANA

Logo CHENG KUNG

Logo UTEP

Logo MOBIUS

Logo UNIVEM

Logo Kennedy

Logo Columbia

Logo UCS

Logo MSG/UFF

Logo OPT

Logo Biblioteca Professor Milton Cabral Moreira

Logo UFL

Logo ULRICHSWEB

Logo UNISA