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.
WangJ.B. and WangJ.J., Single-machine scheduling problems with precedence constraints and simple linear deterioration, Applied Mathematical Modelling39(3-4) (2015), 1172–1182.
2.
SkutellaM., A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective, Operations Research Letters44(5) (2016), 676–679.
3.
DavariM., DemeulemeesterE., LeusR. and NobibonF.T., Exact algorithms for single-machine scheduling with time windows and precedence constraints, Journal of Scheduling19(3) (2016), 309–334.
4.
GaoY. and YuanJ.J., Bi-criteria pareto-scheduling on a single machine with due indices and precedence constraints, Discrete Optimization25 (2017), 105–119.
5.
RustogiK. and StrusevichV.A., Single machine scheduling with a generalized job-dependent cumulative effect, Journal of Scheduling20(6) (2017), 583–592.
6.
FujitaT., HatanoK., KijimaS. and TakimotoE., Online Combinatorial Optimization with Multiple Projections and Its Application to Scheduling Problem, Ieice Transactions on Fundamentals of Electronics Communications and Computer SciencesE101A(9) (2018), 1334–1343.
7.
SittersR. and YangL.Y., A (2+epsilon)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective, Operations Research Letters46(4) (2018), 438–442.
8.
ProtD. and Bellenguez-MorineauO., A survey on how the structure of precedence constraints may change the complexity class of scheduling problems, Journal of Scheduling21(1) (2018), 3–16.
9.
LiJ.Q., XuD.H. and LiH.X., Single machine due window assignment scheduling problem with precedence constraints and fuzzy processing times, Journal of Intelligent and Fuzzy Systems34(6) (2018), 4301–4314.
10.
RostamiS., CreemersS. and LeusR., Precedence Theorems and Dynamic Programming for the Single-Machine Weighted Tardiness Problem, European Journal of Operational Research272(1) (2019), 43–49.
11.
IshiiH. and TadaM., Single machine scheduling problem with fuzzy precedence relation, European Journal of Operational Research87(2) (1995), 284–288.
12.
LevnerE. and VlachM., Single-machine scheduling with mixed precedence constraints, Journal of the Operations Research Society of Japan42(3) (1999), 330–341.
13.
XieY., XieJ.Y. and HuangQ.H., Single Machine Scheduling Problem with Fuzzy Due Dates and Fuzzy Precedence, Journal of Shanghai University9(5) (2005), 450–454.
14.
LiX.S., IshiiH. and ChenM.H., Batch scheduling problem with due-date and fuzzy precedence relation, KYBERNETIKA48(2) (2012), 346–356.
15.
LiX.S., IshiiH. and ChenM.H., Single machine parallel-batching scheduling problem with fuzzy due-date and fuzzy precedence relation, International Journal of Production Research53(9) (2015), 2707–2717.
16.
LiJ., XuD. and LiH., Single machine due date assignment scheduling problem with preceden3ce constraints and controllable processing times in fuzzy environment, Iranian Journal of Fuzzy Systems15(6) (2018), 121–143.
17.
BehnamianJ., Survey on fuzzy shop scheduling, Fuzzy Optimization and Decision Making15(3) (2016), 331–366.
18.
WikumE.D., LlewellynD.C. and NemhauserG.L., One-machine generalized precedence constrained scheduling problems, Operations Research Letters16(2) (1994), 87–99.
19.
FintaL. and LiuZ., Single machine scheduling subject to precedence delays, Discrete Applied Mathematics70(3) (1996), 247–266.
20.
MuthusamyK., ShaoC.S., VlachM. and IshiiH., Scheduling with fuzzy delays and fuzzy precedences, Fuzzy Sets & Systems134(3) (2003), 387–395.
21.
XieY., XieJ.Y. and DengX.L., A single machine scheduling problem with fuzzy time delays. The 16th IFAC World Congress, 2005, pp 37-42, Prague, Czech Republic.
22.
XieY. and OuL.L., Single Machine Fuzzy Delays Scheduling Problem with Fuzzy Precedences, The 6th International Conference on Fuzzy Systems and Knowledge Discovery (2009), pp. 375–379, Tianjin, China.
23.
XieY., XieJ. and LiuJ., Single Machine Scheduling Problem with Fuzzy Precedence Delays and Fuzzy Processing Times, Lecture Notes in Computer Science3614(5) (2009), 907–910.
24.
BruckerP., KnustS. and OğuzC., Scheduling chains with identical jobs and constant delays on a single machine, Mathematical Methods of Operations Research (ZOR)63(1) (2006), 63–75.
25.
PottsC.N. and WhiteheadJ.D., Heuristics for a coupled-operation scheduling problem, Journal of the Operational Research Society58(10) (2007), 1375–1388.
26.
CondottaA. and ShakhlevichN.V., Scheduling coupled-operation jobs with exact time-lags, Discrete Applied Mathematics160(16-17) (2012), 2370–2388.
27.
RebaineD., Flow shop vs. permutation shop with time delays, Computers & Industrial Engineering48(2) (2005), 357–362.
28.
MsakniM.K., KhallouliW., Al-SalemM. and LadhariT., Minimizing the total completion time in a two-machine flowshop problem with time delays, Engineering Optimization48(7) (2016), 1164–1181.
29.
MoukrimA., RebaineD. and SerairiM., A branch and bound algorithm for the two-machine flowshop problem with unit-time operations and time delays, RAIRO - Operations Research48(2) (2014), 235–254.
30.
DhouibE., TeghemJ. and LoukilT., Non-permutation flow-shop scheduling problem with minimal and maximal time lags: Theoretical study and heuristic. Annals of Operations Research. 2018.
31.
MaY.C., JiaX.R. and ZhangQ.L., Robust observer-based finite-time H∞ control for discrete-time singular Markovian jumping system with time delay and actuator saturation, Nonlinear Analysis: Hybrid Systems28 (2018), 1–22.
32.
GoriL., GuerriniL. and SodiniM., Disequilibrium dynamics in a Keynesian model with time delays, Commun Nonlinear Sci Numer Simulat58 (2018), 119–130.
33.
XiaoJ.Y. and ZhongS.M., Extended dissipative conditions for memristive neural networks with multiple time delays, Applied Mathematics and Computation323 (2018), 145–163.
34.
ZhangW., WangT.C. and TongS.C., Event-Triggered Control for Networked Switched Fuzzy Time-Delay Systems with Saturated Inputs, International Journal of Fuzzy Systems21(5) (2019), 1455–1466.
35.
DarbandiA., YoonS. and KimM.K., Schedule construction under precedence constraints in flexray in-vehicle networks, International Journal of Automotive Technology18(4) (2017), 671–683.
36.
LawlerE.L. and MooreJ.M., A functional equation and its application to resource allocation and sequencing problems, Management Science16(1) (1969), 77–84.
37.
GareyM.R. and JohnsonD.S., Computers and Intractability: AGuide to the Theory of NP-Completeness.W. H. Freeman and Company: San Fransisco. 1979.
38.
LawlerE.L., Optimal Sequencing of a Single Machine Subject to Precedence Constraints, Management Science19(5) (1973), 544–546.
39.
T’KindtV., BillautJ.C. and ScottH., Multicriteria Scheduling: Theory, Models and Algorithms, Springer: New York, 2006.
