Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper tries to solve traditional scheduling problems by using the deep reinforcement learning (RL) framework. To make the RL framework applicable to such problems, the authors model the problem states as an agent-task graph and encode the nodes in the graph utilizing a type-aware graph attention technique they proposed. The obtained node embeddings are next used to compute the final assignment probabilities. The authors use implementation tricks such as reward normalization and clip-loss to accelerate training or achieve better performance in the training process. The proposed method performs well in the traveling salesmen problem and the job-shop scheduling problem.
main_review: ----A post rebuttal edit: 
Thanks for providing the detailed clarifications, a revised manuscript, and new experimental results. I have read all these responses. I agree with the advantages of ScheduleNet over other RL-based methods; however, I’m just still not convinced about the novelty of the three modules themselves. Besides, the explanation about not using the value function is far-fetched, and there is already much research about assignments in the MARL community. In addition, when comparing with other RL-based methods, I suggest that the authors provide the number of network parameters to ensure that the advantages achieved by ScheduleNet do not depend on a larger network. However, I keep my positive impression on this work. 


**Strengths**:

1. The paper is well-organized, and the writing logic is very clear. The Introduction section does not give a flat description but introduces the features of the proposed method one by one; therefore, the readers can have a quick glance at the advantages of the ScheduleNet. The Method section is also clearly structured and easy to understand.
2. The reinforcement learning framework is suitable for solving sequential decision problems, so it is a reasonable and clever attempt to apply the framework to multi-agent scheduling problems. This paper's adjustments in modeling, representation, and training techniques are all good practices to involve the RL framework.

**Weaknesses**:

1. This submission has some mistakes and typos in writing, including grammar and expression problems, some of which may affect understanding. I only list some of them here. 

   (1) Verb mistakes. For example, in the last paragraph on page one, "a wrong choice at the early stage can results (result) in irreversible poor results at the end"; In the part about Job-shop scheduling problems on page three, "However, these methods utilizing (utilize) human-engineered dense reward"......

   (2) Third-person singular. For example, "learning-based improvement (improvements) have shown better performance" in the paragraph about vehicle routing problems on page two; "such randomness do (does) not alter" in the action paragraph on page three; 

   (3) Writing standard mistakes. For example, nearly all the "i.e." miss the comma (i.e.,); 

   (4) Compilation problems. For example, Figure 1 on page three is mentioned on page four for the first time; 

   (5) Many article usage mistakes. For example, you should remove the word "the" of "following novelties and the advantages" in the Novelties paragraph on the second page; In the paragraph about Job-shop scheduling problems on page three, "solving job-shop scheduling problem" should be revised as "solving the job-shop scheduling problem" or "solving job-shop scheduling problems"; Besides, the "an" in "requires an additional training" should be removed; There are two "the" in the transition paragraph on page three;

   (6) Sentence break mistakes. For example, "A solution to mTSP is considered to be complete when all the cities have been visited (, ) and all salesmen have returned to the depot" in the first paragraph of page four, a comma should be put before "and" because the subject of the sentence changes;

   (7) ......

   While some of these errors do not affect comprehension, they may influence the cogency of this paper. Besides, these basic errors may give the impression that the essay has not been adequately prepared. 

2. There are linguistic repetitions in the formulation section. The authors try to give examples to clearly explain some of the definitions but mostly just repeat the definitions—for example, the reward part in subsection 3.1. If the paper sets a subsection about examples, it is recommended to give a straightforward and real example rather than repetition.

3. Why does the essential difference between min-max and min-sum affect the solutions to scheduling problems? This point is understandable but not theoretically stated in the paper. Therefore, the reader cannot tell whether the proposed framework can also solve the min-sum problem. I believe that different scheduling problems may pursue various goals, and the problem with min-max as the goal that this paper tries to solve is only one class of scheduling problems. If the proposed method cannot solve problems with min-sum as the goal, then the proposed approach may have some limitations. I suggest that the authors analyze and explain these issues in their submission.

4. About Novelty. The approach proposed in this paper is an attempt to apply reinforcement learning to scheduling problems. The modeling technique, representation technique, and RL technique are minor improvements on traditional methods and can be summarized as implementation tricks to adapt to scheduling problems. I am therefore skeptical about this paper's novelty and contribution. In terms of the RL community, the contribution of this paper is low. 

   I have not previously delved into scheduling problems and have only a passing knowledge in this area, so I cannot accurately assess this method's academic and theoretical contributions in the scheduling area. However, by reading this submission, I believe that its theoretical contribution may be small and the experimental performance is not significantly improved compared to other methods. 

   However, if the authors can provide more convincing explanations during the discussion period, I will change my opinion on this problem.
summary_of_the_review: This paper is an attempt to combine the DRL framework with scheduling problems. It deserves credit for modeling the scheduling problems as MDPs to fit the RL framework and for providing new implementation insights for solving mSPs by utilizing reinforcement learning. However,  this paper has no major innovations or new theoretical insights at the methodological level but minor changes to existing techniques to make a REINFORCE variant applicable to the scheduling problem. Therefore, this paper's contribution to the community may be limited.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a generic approach called ScheduleNet to solve combinatorial multi-agent scheduling problems using neural network and reinforcement learning. An agent-task relationship graph is first constructed through edge and node embedding (using message passing framework among neighbours). Message values for each node is computed using type-aware edge embedding value and then a node embedding is performed using the message values. Using these embedding values, ScheduleNet computes assignment probability between idle agent and active tasks. ScheduleNet is trained using reinforcement learning and two methods are proposed to improve training performance: (a) reward normalization and (b) adding clip parameter in REINFORCE algorithm training. Extensive experimental results are demonstrated on mTSP and job-shop scheduling problems. Through benchmarking against state-of-the-art OR heuristics and RL methods, and using ablation studies, it is shown that the ScheduleNet performs efficiently and generalizes well to unknown or online scenarios.
main_review: The paper proposes a generic framework for solving multi-agent combinatorial scheduling problems. The type-aware embedding for agent-task relationship graph construction is novel and has a distributed framework which can be developed using message passing framework among neighbours. The reward normalization and usage of clip parameter in training REINFORCE algorithm are shown to be effective. I appreciate the extensive amount of empirical results on both mTSP and JSP domains, which demonstrate that the ScheduleNet not only performs efficiently during training process as compared to state-of-the-art methods, but also generalizes well to other real-world datasets. Ablation study also demonstrates the efficacy of embedding methods and two practical modifications made for REINFORCE algorithm. Having said that I have a few comments: (a) The runtime comparison between RL and OR methods is not completely fair as the RL method only consider inference time (training time is not included if I am not wrong). (b) The multi-agent aspect of the problem is somewhat not discussed in properly. I would appreciate adding a distributed RL training algorithm using the messages generated for each node in each time-step. One key issue in multi-agent RL training is non-stationarity; I am not sure how this problem is tackled. (c) Please explain how the different hard constraints for these combinatorial problems are satisfied during RL training? Is it generalizable enough to tackle additional constraints, e.g., time window constraints? (d) I am interested to understand the problem setting for the results of Table 2. The RL algorithm is trained using synthetic dataset (results of Table 1) and then executed in these public datasets? Have you done any incremental training on these public datasets? If not, do you have any insights on why it generalizes so well to these public datasets; does the parametric distribution matches between the synthetic and public dataset? Please clarify.
summary_of_the_review: The paper solves a combinatorial multi-agent scheduling problem using graph embedding and RL methods. Both type-aware message embedding and practical suggestions to improve REINFORCE algorithm are interesting and performs well. I also appreciate extensive empirical results on two general problem classes against both state-of-the-art OR and RL based techniques. Having said that, I am not confident on how the multi-agent aspect of the problem is tackled. No theoretical result is provided to demonstrate that the ScheduleNet can handle all the hard domain constraints of a problem and can tackle the multi-agent interactions in a principled way.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper considers solving two well-known combinatorial optimization problems (multiple traveling salesmen problem and job-shop scheduling problem) using neural networks trained with the help of Reinforcement Learning. The approach embeds the problem in an MDP framework with rewards corresponding to a normalized makespan metric and trains the policy using a PPO-like objective.
main_review: ==== A post rebuttal edit: I am satisfied with the author's extended answer, therefore I raise my score.

The paper is an interesting application of RL coupled with some tricks to the well-known optimization problems. Below are the detailed remarks.

​1. Description of MDP:

 * $p_\tau^i$ is defined as 'position' in Section 3.1. This is not clear. Section C.1. suggests that positions are 2D points.​
 * The generative process of MDP should be explained: how are $p_\tau^i$ generated, what is the distribution of distances between 'positions'? This could help to give context to the numbers in Tables 1-4.​
 * In the context of the above, the definition of makespan should be made more explicit.

2) Training:
* PPO uses an advantage normalization trick (among others). It bears some resemblance to the normalization trick in the paper (which is on the reward side, though). Is there some deeper similarity here?​
* Using advantage makes the method invariant to scalar shift in the rewards. This seems not to be the case for normalized rewards used in the paper. Is this issue a limitation for the method to use it for different optimization problems?  ​
* It is not clear how the formula (9) is computed, in particular using data gathered in Algorithm 2. This should be made explicit. Similarly, the meaning of the expected value in formula (9) should be described.​
* It would be interesting to know why the choice of "slowly varying" policy as baseline helps. In particular, it seems that this choice has to be related to the *inner updates* loop from Algorithm 2 (lines 9-12) and the choice of $K$. It also somewhat resembles the use of target networks in contemporary RL algorithms.
  ​
3) Experiments:

* The description of training in Section 6.1 is slightly confusing. Is the ScheduleNet trained on $30x3$ setup for both Table 1 and Table 2? What is the choice of the *update steps* (lines 2 in Algorithm 2)?​
* It seems from Appendix C.1. that only one seed is used for training (1234). If so, then this could be worrying, as RL training is known to have high variance.​
* Values from tables 1-4 are not clear: 
    - what are the entries (makespan? normalized? discounted?)?
    - can we interpret these numbers (see the questions in point 1)?
    - what are the confidence intervals for these results?
    - how does this result compares to the "size of the graph", e.g. its
      diameter?
    - lack of the above make is if difficult to assess the difference between
      ScheduleNet and the baselines.​
* "Gap" (last column in Tables 1, 2, 4) is not defined. Make sure that the entries in this column reflect the values computed according to the definition and the values in the table.​
* The Authors mention real-life applications; however do not specify their scale.
  In particular, are the problems in the experiments section close to real
  applications?
  ​
* What are the computational limits of the method? How much larger problems can
  be tackled larger computational resources?
summary_of_the_review: The paper is an interesting application of RL coupled with some tricks to the
well-known optimization problems.
In its current form, it is below the acceptance threshold, but I am willing
to increase my score if the authors address the issues raised above.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a multi-agent reinforcement learning approach to solve scheduling problems (including mTSP and job-shop scheduling (JSP)), with the objective of makespan minimization. In the mTSP, the agent represents salesman, and in JSP, the agent represents machine. The core idea is to employ the type-aware graph attention mechanism to learn the assignment probability of agents to tasks. Experiments on mTSP and JSP simulations validate the strength of the proposed approach ScheduleNet. 
main_review: Strengths: The proposed ScheduleNet can make a tradeoff between computation time and solution efficiency (i.e., makespan).
Weaknesses: 
1)	From the experimental results, I find the proposed ScheduleNet less attractive. Specially, in the large-scale instance (200, 20), the LKH3 can also return the optimal solution. Although the running time of LKH3 is nearly 1,000 seconds, the ScheduleNet also takes hundreds of seconds. Considering the solution gap between LKH3 and ScheduleNet is 1.04, it is worth of waiting LKH3, especially in the offline settings, where the agents and jobs are known. 
2)	The JSP task seems easier than the mTSP task, since the machine in JSP is homogeneous while the salesman in mTSP is heterogeneous with different positions. Thus, my question is that why unify the training frame for these two different scenarios? I am convinced that the ScheduleNet is suitable for mTSP, but more smart mechanism is necessary for JSP. This can also explain that the ScheduleNet performs worse in JSP (Table 4) than that in mTSP. A potential re-organization is to first propose a more simple mechanism for the JSP with homogenous agents, and then to propose a complex mechanism (e.g., ScheduleNet) for the mTSP.
3)	In section 4.1, agent-task graph, the edge e_{ij} between nodes should be defined more clearly. Especially when there should be an edge between two nodes?
4)	This paper claims to propose a coordinated multi-agent approach, ScheduleNet seems like a centralized training and execution framework. Although the authors state “Note that ScheduleNet allows an agent to process its local state information,….appear dynamically.”, it is not clear how these agents coordinate their behavior, for example, when two agents are assigned to the same job, which agent really executes it?    
5)	Typos: Section 3: “An event is defined as the the case”->“An event is defined as the case”.

summary_of_the_review: This paper proposes a multiagent reinforcement learning approach to solve scheduling problems (including mTSP and job-shop scheduling (JSP)). However, the techniques are not clearly described and the experimental results are not fascinating.
review_title: null

Meta-review: This paper proposes a deep RL framework for the traditional schedule problem. The proposed algorithm is shown to be effective and has zero-shot generalization abilities. Reviewers are mostly satisfied with the response and the overall evaluation is slightly positive. However, there are some drawbacks of the current paper preventing it from getting a higher evaluation: (1) The reviewers believe that the contribution might be small -- at least for the RL area; the experimental performance for the scheduling problem is also not significantly improved compared to other methods (e.g. the search-based ones). Hence the reviewers believe the contribution of the paper is limited. (2) There is a number of typos and language issues in its present version. The paper may need several rounds of polishment before publication. (3) There is a lack of theoretical justification for the proposed method.  In sum, the AC recommends a borderline rejection.
Decision: Reject