Graph-Based Modeling in Shop Scheduling Problems: Review and Extensions
| Autor: | Golshan Madraki, Jacqueline M. Otala, Seyedamirabbas Mousavian, Alden Minard |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Technology
Theoretical computer science QH301-705.5 Job shop Computer science graph theory QC1-999 Cellular manufacturing a systematic review and categorization methodology 0211 other engineering and technologies Complex system Scheduling (production processes) 02 engineering and technology Field (computer science) shop scheduling problem 0202 electrical engineering electronic engineering information engineering manufacturing systems General Materials Science Biology (General) QD1-999 Instrumentation Fluid Flow and Transfer Processes 021103 operations research Physics Process Chemistry and Technology General Engineering modeling Graph theory Directed graph Engineering (General). Civil engineering (General) Computer Science Applications Chemistry Hybrid system 020201 artificial intelligence & image processing TA1-2040 |
| Zdroj: | Applied Sciences, Vol 11, Iss 4741, p 4741 (2021) |
| ISSN: | 2076-3417 |
| DOI: | 10.3390/app11114741 |
| Popis: | Graphs are powerful tools to model manufacturing systems and scheduling problems. The complexity of these systems and their scheduling problems has been substantially increased by the ongoing technological development. Thus, it is essential to generate sustainable graph-based modeling approaches to deal with these excessive complexities. Graphs employ nodes and edges to represent the relationships between jobs, machines, operations, etc. Despite the significant volume of publications applying graphs to shop scheduling problems, the literature lacks a comprehensive survey study. We proposed the first comprehensive review paper which (1) systematically studies the overview and the perspective of this field, (2) highlights the gaps and potential hotspots of the literature, and (3) suggests future research directions towards sustainable graphs modeling the new intelligent/complex systems. We carefully examined 143 peer-reviewed journal papers published from 2015 to 2020. About 70% of our dataset were published in top-ranked journals which confirms the validity of our data and can imply the importance of this field. After discussing our generic data collection methodology, we proposed categorizations over the properties of the scheduling problems and their solutions. Then, we discussed our novel categorization over the variety of graphs modeling scheduling problems. Finally, as the most important contribution, we generated a creative graph-based model from scratch to represent the gaps and hotspots of the literature accompanied with statistical analysis on our dataset. Our analysis showed a significant attention towards job shop systems (56%) and Un/Directed Graphs (52%) where edges can be either directed, or undirected, or both, Whereas 14% of our dataset applied only Undirected Graphs and 11% targeted hybrid systems, e.g., mixed shop, flexible, and cellular manufacturing systems, which shows potential future research directions. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|