Single-machine scheduling problem with fuzzy time delays and mixed precedence constraints

摘要

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.