A Review for Submodular Optimization on Machine Scheduling Problems

This paper provides a review of recent results on machine scheduling problems solved by methods of submodular optimization. We present some basic definitions of submodular functions and their connection to scheduling models. Based on the classification of problem features, we conclude different scheduling models, applications of these scheduling scenarios, approaches of submodular optimization, and the performance of corresponding algorithms. It is shown that the use of these submodular optimization methodologies yields fast and efficient algorithms for specific scheduling models such as controllable processing time, unreliable job processing, and common operation scheduling. By identifying the trends in this field, we discuss some potential directions for future research.