Advanced Search
MyIDEAS: Login to save this paper or follow this series

Exponentially better than brute force: solving the jobshop scheduling problem optimally by dynamic programming

Contents:

Author Info

  • Gromicho, J.A.S.

    (Vrije Universiteit Amsterdam, Faculteit der Economische Wetenschappen en Econometrie (Free University Amsterdam, Faculty of Economics Sciences, Business Administration and Economitrics)

  • Hoorn, J.J. van
  • Timmer, G.T.
  • Saldanha-da-Gama, F.
Registered author(s):

    Abstract

    Scheduling problems received substantial attention during the last decennia. The job-shop problem is a very important scheduling problem, which is NP-hard in the strong sense and with well-known benchmark instances of relatively small size which attest the practical difficulty in solving it. The literature on job-shop scheduling problem includes several approximation and optimal algorithms. So far, no algorithm is known which solves the job-shop scheduling problem optimally with a lower complexity than the exhaustive enumeration of all feasible solutions. We propose such an algorithm, based on the well-known Bellman equation designed by Held and Karp to find optimal sequences and which offers the best complexity to solve the Traveling Salesman Problem known to this date. For the TSP this means O(n22n) which is exponentially better than O(n!) required to evaluate all feasible solutions. We reach similar results by first recovering the principle of optimality, which is not obtained for free in the case of the job-shop scheduling problem, and by performing a complexity analysis of the resulting algorithm. Our analysis is conservative but nevertheless exponentially better than brute force. We also show very promising results obtained from our implementation of this algorithm, which seem to indicate two things: firstly that there is room for improvement in the complexity analysis (we observe the generation of a number of solutions per state for the benchmark instances considered which is orders of magnitude lower than the bound we could devise) and secondly that the potential practical implications of this approach are at least as exciting as the theoretical ones, since we manage to solve some celebrated benchmark instances in processing times ranging from seconds to minutes.

    Download Info

    If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
    File URL: ftp://zappa.ubvu.vu.nl/20090056.pdf
    Our checks indicate that this address may not be valid because: 500 Failed to connect to FTP server zappa.ubvu.vu.nl: Net::FTP: Bad hostname 'zappa.ubvu.vu.nl'. If this is indeed the case, please notify (R. Dam)
    Download Restriction: no

    Bibliographic Info

    Paper provided by VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics in its series Serie Research Memoranda with number 0056.

    as in new window
    Length:
    Date of creation: 2009
    Date of revision:
    Handle: RePEc:dgr:vuarem:2009-56

    Contact details of provider:
    Web page: http://www.feweb.vu.nl

    Related research

    Keywords: Job-shop scheduling; dynamic programming; complexity analysis;

    This paper has been announced in the following NEP Reports:

    References

    References listed on IDEAS
    Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
    as in new window
    1. Baycan-Levent, Tuzin & Nijkamp, Peter & Sahin, Mediha, 2007. "New Orientations in Ethnic Entrepreneurship: Motivation, Goals and Strategies of New Generation Ethnic Entrepreneurs," Serie Research Memoranda 0012, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    2. Gulumser, Aliye Ahu & Baycan Levent, Tuzin & Nijkamp, Peter, 2007. "Changing trends in rural self-employment in Europe," Serie Research Memoranda 0017, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    3. Torrieri, F. & Nijkamp, P., 2009. "Scenario analysis in spatial impact assessment:a methodological approach," Serie Research Memoranda 0026, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    4. Jain, A. S. & Meeran, S., 1999. "Deterministic job-shop scheduling: Past, present and future," European Journal of Operational Research, Elsevier, vol. 113(2), pages 390-434, March.
    5. Lazrak, F. & Nijkamp, P. & Rietveld, P. & Rouwendal, J., 2009. "Cultural heritage: hedonic prices for non-market values," Serie Research Memoranda 0049, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    6. Lazrak, F. & Nijkamp, P. & Rietveld, P. & Rouwendal, J., 2009. "Cultural heritage and creative cities: an economic evaluation perspective," Serie Research Memoranda 0036, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    7. Baycan-Levent, Tuzin & Nijkamp, Peter, 2007. "Migrant Entrepreneurship In A Diverse Europe: In Search Of Sustainable Development," Serie Research Memoranda 0011, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    8. Borzacchiello, M.T. & Nijkamp, P. & Scholten, H.J., 2008. "A logistic regression model for explaining urban development on the basis of accessibility: a case study of Naples," Serie Research Memoranda 0020, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    9. Noronha Vaz, E. de & Noronha Vaz, T. de & Nijkamp, P., 2009. "Spatial analyses for policy evaluation of the rural world: portuguese agriculture in the last decade," Serie Research Memoranda 0007, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    10. Baycan-Levent, Tuzin & Nijkamp, Peter, 2007. "Characteristics Of Migrant Entrepreneurship In Europe," Serie Research Memoranda 0014, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    11. Noronha Vaz, E. de & Caetano, M. & Nijkamp, P., 2009. "Trapped between antiquity and urbanism - a multi-criteria assessment model of the greater cairo metropolitan area," Serie Research Memoranda 0006, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    12. Gülümser, A.A. & Baycan-Levent, T. & Nijkamp, P., 2009. "Turkey’s rurality: A comparative analysis at the EU level," Serie Research Memoranda 0031, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    13. Leeuwen, E. van & Nijkamp, P. & Noronha Vaz, T. de, 2009. "The multi-functional use of urban green space," Serie Research Memoranda 0051, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    14. Rodenburg, C.A. & Nijkamp, P. & Groot, H.L.F. de & Verhoef, E.T., 2009. "Valuation of multifunctional land use by commercial investors: a case study on the amsterdam zuidas mega-project," Serie Research Memoranda 0024, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    15. Sahin, M. & Nijkamp, P. & Rietdijk, M., 2009. "Cultural Diversity and Urban Innovativeness: Personal and Business Characteristics of Urban Migrant Entrepreneurs," Serie Research Memoranda 0033, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    16. Percoco, M. & Nijkamp, P., 2009. "Individual time preferences and social discounting in-environmental projects," Serie Research Memoranda 0028, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    17. Patuelli, R. & Reggiani, A. & Nijkamp, P. & Schanne, N., 2009. "Neural networks for cross-sectional employment forecasts: a comparison of model specifications for germany," Serie Research Memoranda 0014, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    18. Dijkgraaf, E. & Gradus, R.H.J.M., 2007. "How to get increasing competition in the Dutch refuse collection market?," Serie Research Memoranda 0019, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    19. Roberto Patuelli & Aura Reggiani & Peter Nijkamp & Norbert Schanne, 2009. "Neural Networks for Regional Employment Forecasts: Are the Parameters Relevant?," Working Paper Series 07_09, The Rimini Centre for Economic Analysis, revised Feb 2010.
    20. Leeuwen, E. van & Nijkamp, P., 2009. "A micro-simulation model for e-services in cultural heritage tourism," Serie Research Memoranda 0047, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    21. Cracolici, M. Francesca & Cuffaro, Miranda & Nijkamp, Peter, 2006. "Sustainable Tourist Development In Italian Holiday Destinations," Serie Research Memoranda 0014, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    22. Travisi, C.M. & Nijkamp, P., 2009. "Managing environmental risk in agriculture: a systematic perspective on the potential of quantitative policy-oriented risk valuation," Serie Research Memoranda 0043, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    23. Cuffaro , Miranda & Cracolici, Maria Francesca & Nijkamp, Peter, 2006. "Economic convergence vs. socio-economic convergence in space," Serie Research Memoranda 0020, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    24. Capello, R. & Nijkamp, P., 2009. "Urban Economics at a Cross-yard: Recent Theoretical and Methodological Directions and Future Challenges," Serie Research Memoranda 0039, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    25. Steinhofel, K. & Albrecht, A. & Wong, C. K., 1999. "Two simulated annealing-based heuristics for the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 118(3), pages 524-548, November.
    26. Bakker, P. & Koopmans, C. & Nijkamp, P., 2009. "Appraisal of integrated transport policies," Serie Research Memoranda 0052, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    27. Cracolici, M.F. & Cuffaro, M. & Nijkamp, P., 2009. "Tourism sustainability and economic efficiency - a statistical analysis of italian provinces," Serie Research Memoranda 0023, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    28. Annema, J.A. & Koopmans, C., 2009. "Een lastige praktijk: ervaringen met waarderen van omgevingskwaliteit in de kosten-batenanalyse," Serie Research Memoranda 0054, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    29. Rego, César & Duarte, Renato, 2009. "A filter-and-fan approach to the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 194(3), pages 650-662, May.
    30. Caragliu, A. & Del Bo, C. & Nijkamp, P., 2009. "Smart cities in Europe," Serie Research Memoranda 0048, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    31. Hemert, P. van & Nijkamp, P., 2008. "Thematic research prioritization in the EU and the Netherlands: an assessment on the basis of content analysis," Serie Research Memoranda 0023, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    32. Marinescu, M.M. & Nijkamp, P., 2009. "IT Companies in Rough Seas: Predictive Factors for Bankruptcy Risk in Romania," Serie Research Memoranda 0011, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    33. Flytzani, Stella & Nijkamp, Peter, 2007. "Locus of control and cross-cultural adjustment of expatriate managers," Serie Research Memoranda 0007, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    34. Ooms, M., 2008. "Trends in Applied Econometrics Software Development 1985-2008, an analysis of Journal of Applied Econometrics research articles, software reviews, data and code," Serie Research Memoranda 0021, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    35. Nijkamp, P. & Sahin, M., 2009. "Performance indicators of urban migrant entrepreneurship in the netherlands," Serie Research Memoranda 0034, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    36. Nijkamp, P. & Stough, R. & Sahin, M., 2009. "Impact of social and human capital on business performance of migrant entrepreneurs - a comparative dutch-us study," Serie Research Memoranda 0017, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    37. Masurel, E. & Nijkamp, P., 2009. "Bridging the gap between institutions of higher education and small and medium-size enterprises," Serie Research Memoranda 0037, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    38. Bruinsma, F. & Kourtit, K. & Nijkamp, P., 2009. "An agent-based decision support model for the development of e-services in the tourist sector," Serie Research Memoranda 0032, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    39. Joseph Adams & Egon Balas & Daniel Zawack, 1988. "The Shifting Bottleneck Procedure for Job Shop Scheduling," Management Science, INFORMS, vol. 34(3), pages 391-401, March.
    40. B. J. Lageweg & J. K. Lenstra & A. H. G. Rinnooy Kan, 1977. "Job-Shop Scheduling by Implicit Enumeration," Management Science, INFORMS, vol. 24(4), pages 441-450, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Lists

    This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

    Statistics

    Access and download statistics

    Corrections

    When requesting a correction, please mention this item's handle: RePEc:dgr:vuarem:2009-56. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (R. Dam).

    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 references are entirely missing, you can add them using this form.

    If the full references list an item that is present in RePEc, but the system did not link 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 profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.