Abstract: he task scheduling for multiearth observation satellites(EOS) is a typical combinatorial optimization problem. Two scheduling algorithms are proposed which can deal with timewindow crash efficiently, and solve this problem according to the ways of dealing of crashing tasks: first finish first schedule with discard task moving back(FFFSDTMB) and accommodate discard task predicting coexistence with discard task moving back(ADTPCDTMB). The pseudocodes of these two algorithms are also given. A complete EOS scheduling process includes constraints checking, priority checking and task scheduling. This article focuses on task scheduling algorithm which have an exclusion relation and the same priority. The goals of these two proposed algorithms are both maximizing the number of tasks that can be scheduled. The same rationale in these two algorithms is that a discarded task can be scheduled instead of a previously selected one by moving it back to its next timewindow or later in the same timewindow. The evaluation results show that the proposed algorithms will enhance considerably the number of tasks that can be scheduled.

Key words: earth observation satellites, time window, scheduling algorithms, combinatorial optimization, conflict task