A novel approach based on Neo4j for multi-constrained flexible job shop scheduling problem

摘要

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.