Affiliations: [a] School of Mechatronic Engineering and Automation, Shanghai University, Shanghai, China
| [b] Science and Information College, Qingdao Agricultural University, Qingdao, Shandong Province, China
Correspondence:
[*]
Corresponding author. Bing Wang, School of Mechatronic Engineering and Automation, Shanghai University, Shanghai 200072, China. E-mail: susanbwang@shu.edu.cn.
Abstract: In this paper, we study the single-machine scheduling problem and obtain some new results on the special time-delay structure and mixed precedence constraints. We first demonstrate the complexity of the ordinary problem under different circumstances and obtain two cases, namely a polynomial solvable case and an NP-complete case. Then, we present a fuzzy extension of the ordinary problem, based on which a representation of the non-dominated solutions is given for the fuzzy scheduling problem. Finally, we demonstrate the complexity of fuzzy extension problems under different time delays by proposing corresponding algorithms.
