Journal of Systems Engineering and Electronics ›› 2020, Vol. 31 ›› Issue (2): 350-358.doi: 10.23919/JSEE.2020.000012

• Systems Engineering • Previous Articles     Next Articles

Robust single machine scheduling problem with uncertain job due dates for industrial mass production

Fan YUE1,2(), Shiji SONG2,*(), Peng JIA3(), Guangping WU1(), Han ZHAO2,4()   

  1. 1 Department of Automation, Tsinghua University, Beijing 100084, China
    2 Research Institute of Systems Engineering, Beijing 100072, China
    3 Jiuquan Satellite Launch Centre, Jiuquan 735000, China
    4 Department of Basic Science, Army Logistics Academy, Chongqing 401311, China
  • Received:2018-09-03 Online:2020-04-01 Published:2020-04-30
  • Contact: Shiji SONG;;;;
  • About author:YUE Fan was born in 1981. She received her Ph.D. degree in control science and engineering with the Department of Automation, Institute of System Integration in Tsinghua University, Beijing, China, in 2019. Her research interests include robust optimization, optimization algorithm, and system optimization. E-mail:|SONG Shiji was born in 1965. He is currently aprofessor with the Department of Automation, Tsinghua University, Beijing, China. His research interests include system modeling, optimization andcontrol, computational intelligence, and pattern recognition.E-mail:|JIA Peng was born in 1980. He received his B.S degree in opto-electronic engineering from Space Engineering University in 2003. He is currently a senior engineer at Jiuquan Satellite Launch Centre. His research interest inclucles application of unmanned aerial vehicle. E-mail:|WU Guangping was born in 1986. He received his M.S. degree from the Academy of Armored Forces Engineering (AAFE) in 2011. He is currently an engineer at Institute of Systems Engineering. His research interests include signal processing, mechatronics engineering, and equipment demonstration. E-mail:|ZHAO Han was born in 1982. He received his Ph.D. degree in control science and engineering with the Department of Automation, Institute of System Integration in Tsinghua University. His research interests include supply chain management and optimization approach. E-mail:
  • Supported by:
    the National Natural Science Foundation of China(61503211);the National Natural Science Foundation of China(U1660202);This work is supported by the National Natural Science Foundation of China (61503211; U1660202)


The single machine scheduling problem which involves uncertain job due dates is one of the most important issues in the real make-to-order environment. To deal with the uncertainty, this paper establishes a robust optimization model by minimizing the maximum tardiness in the worst case scenario over all jobs. Unlike the traditional stochastic programming model which requires exact distributions, our model only needs the information of due date intervals. The worst case scenario for a given sequence that belongs to a set containing only $n$ scenarios is proved, where $n$ is the number of jobs. Then, the model is simplified and reformulated as an equivalent mixed 0-1 integer linear programming (MILP) problem. To solve the MILP problems efficiently, a heuristic approach is proposed based on a robust dominance rule. The experimental results show that the proposed method has the advantages of robustness and high calculating efficiency, and it is feasible for large-scale problems.

Key words: robust optimization, single machine scheduling, maximum tardiness, uncertain due date