Algorithm Research For Scheduling Problems In Radar Transmission System

we mainly study the scheduling problem in randar transmission system.Two models for general and special cases are studied.The core of the research is the approximation algo-rithm and the design and analysis of the heuristic algorithm.This paper is divided into four chapters,details are as follows.In chapter 1,we introduces the basic concept of scheduling problem and the background of the scheduling problem in randar transmission system,Two scheduling problems that need to be studied in this paper are abstracted.In chapter 2,we mainly study the coupled-task scheduling problem with delay time in single-machine environment,where a_i=b_i.In this scheduling problem,job need to be com-pleted in single machine,all jobs have two stages,there is a delay time between the stages,as that when the delay time is completed,the second stage of the job must be started immedi-ately.The problem that we study requires that the processing time of the first stage is equal to the processing time of the second stage for all jobs,the objective function of the problem is makespan,its three field is 1|exactl_j|C_max.In this chapter,the approximation algorithm is designed in some special cases,the properties of the problem and the worst case analysis of the algorithm in different cases are given.In other special cases,we analyzed the problem by numerical simulation.In chapter 3,we mainly study the coupled-task scheduling model with delay time in single-machine environment.It's different from the previous chapter,we study the general case in this chapter,we don't have the conditions that a_i=b_i.its three field is 1|exactl_j|C_maxand the objective function of the problem is makespan.This chapter gives the integer program model and the relevant properties of the scheduling problem.The tabu search algorithm is designed and improved according to the properties of the problem.In the design of tabu search algorithm,we make full use of the optimal solution property of the problem to design the tabu table.Through designed coding and decoding rules,we guarantee the quality of the solution and accelerate the convergence speed of the algorithm.Through a large number of numerical simulation experiments and comparisons from multiple angles,We conclude that the algorithm designed in this paper has better performance.In chapter 4,we give the summary and outlook of this paper.