A novel approach based on Neo4j for multi-constrained flexible job shop scheduling problem. (April 2019)

• Record Type: Journal Article
• Authors: Zhu, Zhenwei; Zhou, Xionghui; Shao, Kang
• Is Part Of: Computers & industrial engineering. Volume 130(2019)
• Page Start: 671
• Page End: 686
• Publication Date: 2019-04
• Subjects: Flexible job shop scheduling -- Neo4j -- Semantic graph -- Precedence constraint -- Stock constraint -- Ant colony optimization; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2019.03.022
• Languages: English
• ISSNs: 0360-8352

Abstract

Graphical abstract: Highlights: First study to consider job precedence, stock and time constraints together. A novel semantic graph model integrating Neo4j and ontology is introduced. A Neo4j-based scheduling application framework is presented. Superior schedules are acquired by the simulation-based ant colony algorithm. Abstract: To accommodate the need for scheduling complex fabricated products manufacturing, this paper studies the flexible job shop scheduling problem with additional job precedence constraints, time constraints, and stock constraints. As a powerful graph database which deals with connected data and embraces relationships in flexible graphs, Neo4j is creatively introduced to tackle this problem. This paper proposes a semantic graph model which can not only represent the scheduling problem with extended constraints but also integrate the entire lifecycle data. In the semantic graph model, diverse specific data linked with semantic relationships are stored in Neo4j while the semantics of conceptual data model are recorded in the ontology. Based on Neo4j, a scheduling application framework incorporating graph database, semantic web and knowledge capture is also developed. By means of parsing the table header's semantics, an automatic conversion mechanism is achieved between tabular data in Excel spreadsheets and graph data in Neo4j. Inspired by the similarity between ants finding food sources along paths scattered with pheromone trails and assigning operations on resources one by one in line with the time under the guidance of accumulated knowledge, a simulation-based ant colony algorithm is carried out to acquire a feasible and nearly optimal schedule solution.