This paper proposes a research program to develop unified recursive formulations for job shop and open shop scheduling problems, extending recent advances in recursive function representations for scheduling problems. The approach aims to handle routing flexibility in job shops and complete routing freedom in open shops, unifying these under a common recursive structure.
Key findings
Proposes a unified recursive formulation framework for job shop, open shop, and flow shop scheduling.
Develops dynamic programming algorithms with theoretical analysis of complexity and approximation ratios.
Integrates recursive formulations with deep reinforcement learning for adaptive scheduling.
Plans comprehensive experimental validation on benchmark instances and open source implementation.
Limitations & open questions
The research is in the proposal stage and has not yet been empirically validated.
The integration of recursive formulations with machine learning techniques is a new area and may face challenges.