Profile
International Journal of Computer & Software Engineering Volume 3 (2018), Article ID 3:IJCSE-128, 11 pages
https://doi.org/10.15344/2456-4451/2018/128
Research Article
Manufacturing Production Line Modelling and Classification of Associated NP-Hard Problems

Joseph Bonello*, John Abela and Ernest Cachia

University of Malta, Faculty of ICT, Msida, Malta
Joseph Bonello, University of Malta, Faculty of ICT , Msida, Malta; E-mail: joseph.bonello@um.edu.mt
27 November 2017; 17 February 2018; 19 February 2018
Bonello J, Abela J, Cachia E (2018) Manufacturing Production Line Modelling and Classification of Associated NP-Hard Problems. Int J Comput Softw Eng 3: 128. doi: https://doi.org/10.15344/2456-4451/2018/128

Abstract

Optimisation of production lines is known to be NP-Hard in the general case so many near-optimal approximation algorithms have been researched to overcome the challenge [1]. In this paper we describe an approach to modelling production lines using a graph theoretic model. In particular, we focus on single machine and job shop problems. We show that the model can be extended to open shop problems. We also discuss how the model can be used to classify scheduling problems from the generated models.