This page has only limited features, please log in for full access.
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.
Jacqueline Otala; Alden Minard; Golshan Madraki; Seyedamirabbas Mousavian. Graph-Based Modeling in Shop Scheduling Problems: Review and Extensions. Applied Sciences 2021, 11, 4741 .
AMA StyleJacqueline Otala, Alden Minard, Golshan Madraki, Seyedamirabbas Mousavian. Graph-Based Modeling in Shop Scheduling Problems: Review and Extensions. Applied Sciences. 2021; 11 (11):4741.
Chicago/Turabian StyleJacqueline Otala; Alden Minard; Golshan Madraki; Seyedamirabbas Mousavian. 2021. "Graph-Based Modeling in Shop Scheduling Problems: Review and Extensions." Applied Sciences 11, no. 11: 4741.
The goal of this research is to accelerate improvement heuristics which use a graph to model the system and calculates the makespan, i.e., longest path in the graph, during each iteration. These heuristics iteratively perturb the graph and recalculate the makespan in each iteration until a satisfactory schedule is determined. We propose Improved Structural Perturbation Algorithm (ISPA) to accelerate the calculation of the length of the longest path in the graph in each iteration. This will decrease the overall computation time of these scheduling improvement heuristics. Scheduling perturbations are represented by structural perturbations of the graph (edge additions and deletions). ISPA partitions nodes in the graph into two types of sets and applies two different processes to calculate the effects of the perturbations depending on the set the node was in. The major contribution of this study is that ISPA executes once to update the length of the longest path regardless of the number of added and deleted edges. This results in a more efficient algorithm in terms of time complexity than previous algorithms. To show this performance improvement, an experiment was performed applying ISPA to a Simulated Annealing (SA) heuristic and compare it with applying the commonly used Standard Longest Path Algorithm (SLPA) and two other existing methods to the SA heuristic. The experiment shows that ISPA outperforms existing methods in all cases. Moreover, for these SA problems, ISPA saved 9%-65% of the execution time compared to SLPA for the job-shop scheduling problems. The time savings increase with size (number of nodes) of the problem. ISPA is applicable to other iterative heuristics, such as Tabu-search, Genetic Algorithms, and Shifting Bottleneck.
Golshan Madraki; Robert.P. Judd. Accelerating the calculation of makespan used in scheduling improvement heuristics. Computers & Operations Research 2021, 130, 105233 .
AMA StyleGolshan Madraki, Robert.P. Judd. Accelerating the calculation of makespan used in scheduling improvement heuristics. Computers & Operations Research. 2021; 130 ():105233.
Chicago/Turabian StyleGolshan Madraki; Robert.P. Judd. 2021. "Accelerating the calculation of makespan used in scheduling improvement heuristics." Computers & Operations Research 130, no. : 105233.
This paper proposes an algorithm called the Maximum Length Recalculation Algorithm (MLRA) to update the length of the longest path to affected nodes in a perturbed Directed Acyclic Graphs (DAG) where multiple edges are simultaneously deleted and added. MLRA can find all these lengths through a single pass. It is mathematically proved that MLRA is correct. MLRA can be applied in different fields where problems can be described as a perturbed DAG. For instance, this paper applies MLRA on the scheduling problem.
Golshan Madraki; Robert P. Judd. Recalculating the Length of the Longest Path in Perturbed Directed Acyclic Graph. IFAC-PapersOnLine 2019, 52, 1560 -1565.
AMA StyleGolshan Madraki, Robert P. Judd. Recalculating the Length of the Longest Path in Perturbed Directed Acyclic Graph. IFAC-PapersOnLine. 2019; 52 (13):1560-1565.
Chicago/Turabian StyleGolshan Madraki; Robert P. Judd. 2019. "Recalculating the Length of the Longest Path in Perturbed Directed Acyclic Graph." IFAC-PapersOnLine 52, no. 13: 1560-1565.
Maedeh Mosayeb Motlagh; Parham Azimi; Maghsoud Amiri; Golshan Madraki. An efficient simulation optimization methodology to solve a multi-objective problem in unreliable unbalanced production lines. Expert Systems with Applications 2019, 138, 1 .
AMA StyleMaedeh Mosayeb Motlagh, Parham Azimi, Maghsoud Amiri, Golshan Madraki. An efficient simulation optimization methodology to solve a multi-objective problem in unreliable unbalanced production lines. Expert Systems with Applications. 2019; 138 ():1.
Chicago/Turabian StyleMaedeh Mosayeb Motlagh; Parham Azimi; Maghsoud Amiri; Golshan Madraki. 2019. "An efficient simulation optimization methodology to solve a multi-objective problem in unreliable unbalanced production lines." Expert Systems with Applications 138, no. : 1.
Manufacturing scheduling improvement heuristics iterate over trial schedules to determine a satisfactory schedule. During each iteration, a performance measure (e.g. makespan) is calculated. The paper presents an efficient algorithm, Structural Perturbation Algorithm (SPA), that accelerates the calculation of the makespan. This means all scheduling improvement heuristics using SPA to calculate makespan for each trial schedule will run faster. To achieve this goal, the manufacturing system is modelled by a Directed Acyclic Graph (DAG). Schedule trials can be described as a perturbed DAG where multiple edges are added and deleted. The major contribution of this research is that SPA can handle multiple edge deletions/additions with a single pass which makes it more efficient in terms of time complexity than current approaches. SPA accomplishes this by partitioning the nodes into three regions based on the locations of the added and deleted edges. Then, SPA updates the length of the affected nodes in each region. The application of SPA is not limited to the scheduling problem. The SPA can be applied in other fields as long as the problem can be described as a Perturbed DAG.
Golshan Madraki; Robert P. Judd. Efficient algorithm to find makespan in manufacturing systems under multiple scheduling perturbations. International Journal of Production Research 2017, 56, 5402 -5418.
AMA StyleGolshan Madraki, Robert P. Judd. Efficient algorithm to find makespan in manufacturing systems under multiple scheduling perturbations. International Journal of Production Research. 2017; 56 (16):5402-5418.
Chicago/Turabian StyleGolshan Madraki; Robert P. Judd. 2017. "Efficient algorithm to find makespan in manufacturing systems under multiple scheduling perturbations." International Journal of Production Research 56, no. 16: 5402-5418.