research-article

A semantics-based dispatching rule selection approach for job shop scheduling

Authors:

Utpal RoyAuthors Info & Claims

Volume 30, Issue 7

Pages 2759 - 2779

https://doi.org/10.1007/s10845-018-1421-z

Published: 01 October 2019 Publication History

Abstract

Dispatching rules are commonly used for job shop scheduling in industries because they are easy to implement, and they yield reasonable solutions within a very short computational time. Many dispatching rules have been developed but they can only perform well in specific scenarios. This is because a dispatching rule or a combination of dispatching rules always pursues a single or multiple fixed production objectives. A lot of approaches (e.g. simulation based or machine learning based approaches) have been published in the literatures attempted to solve the problem of selecting the proper dispatching rules for a given production objective. To select a combination of dispatching rules per randomly selected combination of objectives, this paper investigates a novel semantics-based dispatching rule selection system. Each of the dispatching rules and production objectives relates to a set of scheduling parameters like processing time, remaining work, total work, due date, release date, tardiness, etc. These parameters are semantically interrelated so that a dispatching rule and a production objective can also be semantically related through their semantic expressions. A semantic similarity value can be calculated by comparing their semantic expressions. Based on this idea, a semantics-based dispatching rule selection system for job shop scheduling is developed to generate a combination of dispatching rules given randomly selected combination of production objectives. A proof-of-concept verification process is provided at the end of the paper.

References

[1]

Ahmed, F., & Han, S. (2015). Interoperability of product and manufacturing information using ontology. Concurrent Engineering, 23(3), 265–278.

[2]

Azadeh, A., Hosseini, N., Abdolhossein Zadeh, S., & Jalalvand, F. (2015). A hybrid computer simulation-adaptive neuro-fuzzy inference system algorithm for optimization of dispatching rule selection in job shop scheduling problems under uncertainty. The International Journal of Advanced Manufacturing Technology, 79(1), 135–145.

[3]

Azadeh, A., Negahban, A., & Moghaddam, M. (2012). A hybrid computer simulation-artificial neural network algorithm for optimisation of dispatching rule selection in stochastic job shop scheduling problems. International Journal of Production Research, 50(2), 551–566.

[4]

Baykasoglu, A., Göçken, M., & Özbakir, L. (2010). Genetic programming based data mining approach to dispatching rule selection in a simulated job shop. Simulation, 86(12), 715–728.

Digital Library

[5]

Blackstone, J. H., Phillips, D. T., & Hogg, G. L. (1982). A state-of-the-art survey of dispatching rules for manufacturing job shop operations. International Journal of Production Research, 20(1), 27–45.

[6]

Borgo, S., & Leitão, P. (2004). The role of foundational ontologies in manufacturing domain applications. In R. Meersman & Z. Tari (Eds.), On the move to meaningful internet systems 2004: CoopIS, DOA, and ODBASE. OTM 2004. Lecture notes in computer science (Vol. 3290). Berlin: Springer.

[7]

Borsato, M. (2014). Bridging the gap between product lifecycle management and sustainability in manufacturing through ontology building. Computers in Industry, 65(2), 258–269.

Digital Library

[8]

Canbolat, Y. B., & Gundogar, E. (2004). Fuzzy priority rule for job shop scheduling. Journal of Intelligent Manufacturing, 15, 527–533.

[9]

Chang, X., Rai, R., & Terpenny, J. (2010). Development and utilization of ontologies in design for manufacturing. Journal of Mechanical Design, 132(2), 021009–021009.

[10]

Chen, X., Wen, L. H., & Murata, T. (2012). Composite dispatching rule design for dynamic scheduling with customer-oriented production priority control. IEEJ Transactions on Electrical and Electronic Engineering, 7(1), 53–61.

[11]

Chhim, P., Chinnam, R. B., & Sadawi, N. (2017). Product design and manufacturing process based ontology for manufacturing knowledge reuse. Journal of Intelligent Manufacturing. https://doi.org/10.1007/s10845-016-1290-2.

[12]

Chungoora, N., Canciglieri, O., & Young, R. I. M. (2010). Towards expressive ontology-based approaches to manufacturing knowledge representation and sharing. International Journal of Computer Integrated Manufacturing, 23(12), 1059–1070.

Digital Library

[13]

El Bouri, A., & Amin, G. R. (2015). A combined OWA-DEA method for dispatching rule selection. Computers & Industrial Engineering, 88, 470–478.

Digital Library

[14]

El-Bouri, A., & Shah, P. (2006). A neural network for dispatching rule selection in a job shop. The International Journal of Advanced Manufacturing Technology, 31(3), 342–349.

[15]

Fortineau, V., Paviot, T., & Lamouri, S. (2013). Improving the interoperability of industrial information systems with description logic-based models: The state of the art. Computers in Industry, 64(4), 363–375.

Digital Library

[16]

Gan, M., Dou, X., & Jiang, R. (2013). From ontology to semantic similarity: Calculation of ontology-based semantic similarity. The Scientific World Journal, 2013, Article ID 793091.

[17]

Geiger, C. D., Uzsoy, R., & Aytuğ, H. (2006). Rapid modeling and discovery of priority dispatching rules: An autonomous learning approach. Journal of Scheduling, 9(1), 7–34.

Digital Library

[18]

Guerra-Zubiaga, D. A., & Young, R. I. M. (2008a). Information and knowledge interrelationships within a manufacturing knowledge model. The International Journal of Advanced Manufacturing Technology, 39(1), 182–198.

[19]

Guerra-Zubiaga, D. A., & Young, R. I. M. (2008b). Design of a manufacturing knowledge model. International Journal of Computer Integrated Manufacturing, 21(5), 526–539.

Digital Library

[20]

Harispe, S., Ranwez, S., Janaqi, S., & Montmain, J. (2013). Semantic measures for the comparison of units of language, concepts or instances from text and knowledge representation analysis. arXiv:1310.1285.

[21]

Harispe, S., Ranwez, S., Janaqi, S., & Montmain, J. (2017). Semantic similarity from natural language and ontology analysis. arXiv:1704.05295.

[22]

Haupt, R. (1989). A survey of priority rule-based scheduling. Operations-Research-Spektrum, 11(1), 3–16.

[23]

Heger, J., Hildebrandt, T., & Scholz-Reiter, B. (2015). Dispatching rule selection with Gaussian processes. Central European Journal of Operations Research, 23(1), 235–249.

[24]

Joseph, O. A., & Sridharan, R. (2011). Effects of routing flexibility, sequencing flexibility and scheduling decision rules on the performance of a flexible manufacturing system. The International Journal of Advanced Manufacturing Technology, 56(1), 291–306.

[25]

Kashfi, M. A., & Javadi, M. (2015). A model for selecting suitable dispatching rule in FMS based on fuzzy multi attribute group decision making. Production Engineering, 9(2), 237–246.

[26]

Kızıl, M., Özbayrak, M., & Papadopoulou, T. C. (2006). Evaluation of dispatching rules for cellular manufacturing. The International Journal of Advanced Manufacturing Technology, 28(9), 985–992.

[27]

Lemaignan, S., Siadat, A., Dantan, J. Y., & Semenenko, A. (2006). MASON: A proposal for an ontology of manufacturing domain. Paper presented at IEEE Workshop on Distributed Intelligent Systems: Collective Intelligence and Its Applications (DIS’06), Prague, Czech Republic. https://doi.org/10.1109/DIS.2006.48.

[28]

Lin, H. K., & Harding, J. A. (2007). A manufacturing system engineering ontology model on the semantic web for inter-enterprise collaboration. Computers in Industry, 58(5), 428–437.

Digital Library

[29]

Lin, L. F., Zhang, W. Y., Lou, Y. C., Chu, C. Y., & Cai, M. (2011). Developing manufacturing ontologies for knowledge reuse in distributed manufacturing environment. International Journal of Production Research, 49(2), 343–359.

[30]

Lin, Y., Chiu, C., & Tsai, C. (2008). The study of applying ANP model to assess dispatching rules for wafer fabrication. Expert Systems with Applications, 34(3), 2148–2163.

Digital Library

[31]

Liu, H., & Dong, J. (1996). Dispatching rule selection using artificial neural networks for dynamic planning and scheduling. Journal of Intelligent Manufacturing, 7, 243–250.

[32]

Metaxiotis, K. S., Psarras, J. E., & Askounis, D. (2001). Building ontologies for production scheduling systems: Towards a unified methodology. Information Management & Computer Security, 9(1), 44–51.

[33]

Mouelhi-Chibani, W., & Pierreval, H. (2010). Training a neural network to select dispatching rules in real time. Computers & Industrial Engineering, 58(2), 249–256.

Digital Library

[34]

Panetto, H., Dassisti, M., & Tursi, A. (2012). ONTO-PDM: Product-driven ONTOlogy for product data management interoperability within manufacturing process environment. Advanced Engineering Informatics, 26(2), 334–348.

Digital Library

[35]

Panwalkar, S. S., & Iskander, W. (1977). A survey of scheduling rules. Operations Research, 25(1), 45–61.

Digital Library

[36]

Rahmani, K., & Thomson, V. (2012). Ontology based interface design and control methodology for collaborative product development. Computer-Aided Design, 44(5), 432–444.

Digital Library

[37]

Scholz-Reiter, B., Heger, J., & Hildebrandt, T. (2010). Gaussian processes for dispatching rule selection in production scheduling: Comparison of learning techniques. Paper presented at 2010 IEEE International Conference on Data Mining Workshops, Sydney, NSW, Australia. https://doi.org/10.1109/ICDMW.2010.19.

[38]

Shafiq, S. I., Faheem, M., & Ali, M. (2010). Effect of scheduling and manufacturing flexibility on the performance of FMS. Global Journal of Flexible Systems Management, 11(3), 21–38.

[39]

Shiue, Y. (2009). Data-mining-based dynamic dispatching rule selection mechanism for shop floor control systems using a support vector machine approach. International Journal of Production Research, 47(13), 3669–3690.

[40]

Stanford Center for Biomedical Informatics Research (BMIR). (2018). Protégé: A free, open-source ontology editor and framework for building intelligent systems. http://protege.stanford.edu/. Accessed on 29 Jan 2018.

[41]

Talhi, A., Fortineau, V., Huet, J., & Lamouri, S. (2017). Ontology for cloud manufacturing based product lifecycle management. Journal of Intelligent Manufacturing. https://doi.org/10.1007/s10845-017-1376-5.

[42]

The Apache Software Foundation. (2018). Apache jena: A free and open source java framework for building semantic web and linked data application. https://jena.apache.org/. Accessed on 29 Jan 2018.

[43]

Usman, Z., Young, R. I. M., Chungoora, N., Palmer, C., Case, K., & Harding, J. A. (2013). Towards a formal manufacturing reference ontology. International Journal of Production Research, 51(22), 6553–6572.

[44]

W3C Working Group. (2012). OWL 2 web ontology language Manchester syntax (2$$^{\rm nd}$$ ed.). W3C Recommendation.

[45]

Wilbrecht, J. K., & Prescott, W. B. (1969). The influence of setup time on job shop performance. Management Science, 16(4), 274–280.

[46]

Wu, Z., & Palmer, M. (1994). Verb semantics and lexical selection. Paper presented at Proceeding ACL ’94 Proceedings of the 32nd Annual Meeting on Association for Computational Linguistics, Las Cruces, New Mexico, USA.

[47]

Zhang, H., Zhu, B., Li, Y., Yaman, O., & Roy, U. (2015). Development and utilization of a process-oriented information model for sustainable manufacturing. Journal of Manufacturing Systems, 37(2), 459–466.

[48]

Zhong, R. Y., Huang, G. Q., Dai, Q. Y., & Zhang, T. (2014). Mining SOTs and dispatching rules from RFID-enabled real-time shopfloor production data. Journal of Intelligent Manufacturing, 25, 825–843.

Digital Library

Cited By

Castro RGodinho-Filho MTavares-Neto R(2022)Dispatching method based on particle swarm optimization for make-to-availabilityJournal of Intelligent Manufacturing10.1007/s10845-020-01707-633:4(1021-1030)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1007/s10845-020-01707-6
Yin SBao JZhang JLi JWang JHuang X(2020)Real-time task processing for spinning cyber-physical production systems based on edge computingJournal of Intelligent Manufacturing10.1007/s10845-020-01553-631:8(2069-2087)Online publication date: 4-Mar-2020
https://dl.acm.org/doi/10.1007/s10845-020-01553-6

Recommendations

Constraint-Based Job Shop Scheduling with {\sc Ilog\ Scheduler}

We introduce constraint-based scheduling and discuss its main principles. An approximation algorithm based on tree search is developed for the job shop scheduling problem using {\sc Ilog\ Scheduler} . A new way of calculating lower bounds on the ...
Heuristic Optimization for Dual-resource Constrained Job Shop Scheduling
CAR '09: Proceedings of the 2009 International Asia Conference on Informatics in Control, Automation and Robotics

In the study of job shop scheduling problem in mass injection molding processing enterprises, the practical job shop scheduling environment cannot be mirrored in the traditional study only considering machine resources. A dual-resource (machines and ...
Automatically evolving preference-based dispatching rules for multi-objective job shop scheduling
Abstract
Dispatching rules represent a simple heuristic for finding good solutions for job shop scheduling problems. Due to their fast applicability and easy handling, they are often used in manufacturing companies to create appropriate production ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Intelligent Manufacturing

Journal of Intelligent Manufacturing Volume 30, Issue 7

Oct 2019

207 pages

ISSN:0956-5515

Issue’s Table of Contents

Copyright © 2019 Springer Science+Business Media, LLC, part of Springer Nature.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 October 2019

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Castro RGodinho-Filho MTavares-Neto R(2022)Dispatching method based on particle swarm optimization for make-to-availabilityJournal of Intelligent Manufacturing10.1007/s10845-020-01707-633:4(1021-1030)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1007/s10845-020-01707-6
Yin SBao JZhang JLi JWang JHuang X(2020)Real-time task processing for spinning cyber-physical production systems based on edge computingJournal of Intelligent Manufacturing10.1007/s10845-020-01553-631:8(2069-2087)Online publication date: 4-Mar-2020
https://dl.acm.org/doi/10.1007/s10845-020-01553-6

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents