search

zcaicaros / L2D

Official implementation of paper "Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning"
288 stars 94 forks source link

How to test bigger instance and irregular instance #18

Open edwardzcl opened 9 months ago

edwardzcl commented 9 months ago

Why your models trained on small instances can be tested on bigger instances, how to solve the difference of size. Why each operation of your instance need different machines, no repetition in a job. How to test on some irregular instances, i.e. some jobs have different amount of operations.

zcaicaros commented 9 months ago
  1. GNN is a type of NN that is size-agnostic and generalizable to different sizes of disjunctive graphs.
  2. You can change the adjacent matrix to accommodate the varied number of operations of jobs.
edwardzcl commented 9 months ago
  1. GNN is a type of NN that is size-agnostic and generalizable to different sizes of disjunctive graphs.
  2. You can change the adjacent matrix to accommodate the varied number of operations of jobs.

For the question2, I think we can change the adjacent matrix i.e. conjunctions arcs and the last candidate operation of each job. Besides, I think there may be another way: we can make up the jobs with fewer operations to the longest one and set the processing time of these extra operations to be 0. For another question: the required machines of a job with 15 operations may be [1, 2, 1, 3, 10, 12, 10, 8, 2, 3, 12, 15, 4, 6, 12], which means some operations occupy the same machines, so is there some effects on your algorithm?

zcaicaros commented 9 months ago

For question 2, you don't need fictitious nodes like the ones with 0 processing time. You can directly remove the operations by constructing a modified adjacent matrix (i.e., the new adjacent matrix does not contain those operations, it only encodes the connectivity of the existing operation nodes). Of course, you need to provide the node raw feature tensor accordingly.

For the new question, this is a job shop problem with re-entry cases, i.e., a job must be processed by a machine multiple times. For now, I didn't see any barriers preventing applying my method to this problem. But you need to be careful in examining the state transition mechanism, especially for next-state disjunctive graph construction.

edwardzcl commented 8 months ago

For question 2, you don't need fictitious nodes like the ones with 0 processing time. You can directly remove the operations by constructing a modified adjacent matrix (i.e., the new adjacent matrix does not contain those operations, it only encodes the connectivity of the existing operation nodes). Of course, you need to provide the node raw feature tensor accordingly.

For the new question, this is a job shop problem with re-entry cases, i.e., a job must be processed by a machine multiple times. For now, I didn't see any barriers preventing applying my method to this problem. But you need to be careful in examining the state transition mechanism, especially for next-state disjunctive graph construction.

For the disjunctive graph of job shop problem with re-entry cases, there may be another issue: how to describe two adjacent operations which belongs to the same job, while they must be processed by a machine. In this case, whether a conjunctions arc or a disjunctive arc or both of them are required, and how to define the adjacent matrix becase these two arcs overlap.

zcaicaros commented 8 months ago

For question 2, you don't need fictitious nodes like the ones with 0 processing time. You can directly remove the operations by constructing a modified adjacent matrix (i.e., the new adjacent matrix does not contain those operations, it only encodes the connectivity of the existing operation nodes). Of course, you need to provide the node raw feature tensor accordingly. For the new question, this is a job shop problem with re-entry cases, i.e., a job must be processed by a machine multiple times. For now, I didn't see any barriers preventing applying my method to this problem. But you need to be careful in examining the state transition mechanism, especially for next-state disjunctive graph construction.

For the disjunctive graph of job shop problem with re-entry cases, there may be another issue: how to describe two adjacent operations which belongs to the same job, while they must be processed by a machine. In this case, whether a conjunctions arc or a disjunctive arc or both of them are required, and how to define the adjacent matrix becase these two arcs overlap.

Agree, this is a problem. But if you use modern library like PyG, it can handle it properly:

https://github.com/pyg-team/pytorch_geometric/discussions/7427#discussion-5228953