China
Africa
Explore chapters and articles related to this topic
Harmony Search
Published in Nazmul Siddique, Hojjat Adeli, Nature-Inspired Computing, 2017
To speed up the local search procedure, the concept of common critical operations represented by a disjunctive graph is introduced; that is, a schedule is represented by a disjunctive graph. The effective neighborhoods are based on the critical path in the disjunctive graph. The local search is performed on the disjunctive graph, which introduces problem-specific knowledge for the local search. The optimization process is executed by providing cooperation between the global search-based HS and the local search. The effectiveness and performance of the proposed approach have been tested on a number of benchmark problems. Thirty independent runs are carried out for each data set. The chosen parameter settings are as follows: HMS = 5, HMCR = 0.95, PAR = 0.3, and δ = 1. The number of iterations was adjusted according to data sets. The computational results demonstrate the effectiveness and efficiency of the proposed algorithm for solving the FJSSP with the makespan criterion, and also results are competitive in terms of solution quality and time requirements.
A theoretical framework to accelerate scheduling improvement heuristics using a new longest path algorithm in perturbed DAGs
Published in International Journal of Production Research, 2023
Golshan Madraki, Seyedamirabbas Mousavian, Yasamin Salmani
Any graph representation of a manufacturing system must be acyclic since the existence of a cycle in a system means a deadlock situation under which the system fails to continue to operate forever (H. Wang et al. 2020). Therefore, one of the most appropriate, accurate, and adequate models for our choice-free job shop system and the classical scheduling problem is DAG. The DAG representation of a manufacturing system is also known as a task graph, disjunctive graph, or precedence graph (Dou et al. 2021; Mokhtari and Mozdgir 2015). The following basic concepts of DAG modelling approach have been utilised in the literature for several decades (Adams, Balas, and Zawack 1988): Nodes in the DAG denote the operations (processing of a job by a machine) and edges model the scheduling/sequencing of the operations. The weights of the nodes show the processing time of the operations.
A new neighbourhood structure for job shop scheduling problems
Published in International Journal of Production Research, 2023
Jin Xie, Xinyu Li, Liang Gao, Lin Gui
This section briefly introduces a disjunctive graph model for JSP proposed by Balas (1969) to clearly describe the N8 neighbourhood structure. The disjunctive graph G = (N, A, E) is used to represent any scheduling scheme, where N represents the operation set, N = {0, Oij, | i = 1, 2, … , n; j = 1, 2, … , m}, Oij denotes the jth operation of the ith job, 0 is the dummy start operation, and is the dummy finish operation. A denotes the set of conjunctive arcs that connect operations of the same job. E represents the set of disjunctive arcs that connect operations processed on the same machine. pij denotes the the processing time of Oij. The length of an arc is equal to pij. The length of an arc is equal to pij or pi’j’, which is depended on its orientation. Besides, the length of an arc is equal to 0, when its starting operation is 0 or ending operation is . The longest path from 0 to is the critical path, its length is equal to the makespan of the scheduling scheme. If there are multiple longest paths from 0 to in a disjunctive graph, we randomly choose any one of them as the critical path. The objective of obtaining the optimal scheduling scheme corresponds to finding the shortest critical path from the disjunctive graph.
Learning to schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning
Published in International Journal of Production Research, 2021
Junyoung Park, Jaehyeong Chun, Sang Hun Kim, Youngkook Kim, Jinkyoo Park
The disjunctive graph only contains static information of the JSSP such as processing times of operations, precedence sharing, and machine sharing constraints, failing to incorporate dynamically changing JSSP state information. We incorporate node features into the nodes in g so that g represent the current state of the JSSP during scheduling. The node feature assigned to node v is as follows: