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.
1 December 2019 in Expert Systems with Applications
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.
17 September 2021 in International Journal of Information Technology & Decision Making
Job-shop scheduling problems are complex and still well-studied manufacturing problems. Improvement heuristic algorithms have been proposed to solve the scheduling problems using makespan as their performance measure. All these heuristics iteratively perturb trial schedules by selecting a new schedule from a set of nearby schedules (neighbourhood); then, recalculate and compare the makespan until a sufficient schedule is determined. Unlike previous studies, we did not generate a new heuristic or a novel neighbourhood calculation. Instead, we proposed a theoretical framework, Algorithm to Visit Affected Node (AVAN), which can be incorporated in qualified heuristics while using their current neighbourhood structure to accelerate the recalculation of the makespan in each iteration. We modelled the system by Directed Acyclic Graph (DAG) where the length of the longest path equals the makespan. The scheduling perturbations are represented by adding and deleting edges. AVAN investigates the configuration of scheduling perturbations (added/deleted edges) to find an appropriate starting point to traverse the graph. AVAN is mathematically more efficient than previous longest path algorithms for perturbed DAG. Its time complexity is , where is the number of affected nodes and is the number of incoming and outgoing edges of the affected nodes.
1 July 2023 in Northeast Journal of Complex Systems (NEJCS)
Parler, a self-proclaimed free speech social media platform founded in 2018, attracted a large influx of new members in 2020 as the result of a highly visible platform migration campaign. Parler usage was linked to the planning of the Jan. 6, 2021 attack on the United States Capitol building, leading to a shutdown of the Parler platform. Parler, which is now back online, offers an important lens through which to examine the broader attempts at platform migration in response to changing content moderation and platform governance policies and their impact on political polarization. We begin by examining the network connections between US Congressional Representatives on both Twitter and Parler. We find that Parler has a homogenous population of users, consisting of a single isolated group, where polarization seems irrelevant, while Twitter demonstrates two clearly polarized groups. We compare how politicians and political pundits use Parler differently. Finally, we examine the evolution of Parler including comparing Parler’s own policies before and after the shutdown and reflecting on the future of platforms like Parler and similar platform migration experiments.