Research On Time-dependent Scheduling Methods And Application On Agile Satellites Mission Planning

Scheduling problems consist in the allocation of limited resources over time to a set of different tasks. A feasible schedule has to satisfy all the constraints concerning the tasks, resources and time in the problem. The aim of scheduling is to find, among all the feasible schedules, a feasible schedule that is with optimal the objective or with satisfying objective. The research on scheduling dated back to the middle 20 th century. New problems, theories and methods continued to come forth in the past tens of years. Time-dependent scheduling is a relatively new subject in scheduling society.In time-dependent scheduling, one or more elements of the problem are closely related to time. Actually, “time-dependent” was initially brought forward to describe problems of which the processing times of jobs were dependent on their starting time. The processing time is not fixed but instead varies as the starting time changes in such a problem which is most extensively studied among the time-dependent scheduling problems. Besides the time-dependent processing times, however, the revenue obtained(or penalty caused) by processing a job as well as the setup times between two consecutive jobs might depend on the starting time(or end time) as well. In this case, they are named time-dependent revenues and time-dependent setup times respectively, which not only exist extensively in the manufacturing and logistics industries, but also are significant characteristics in the agile earth-observing satellite mission planning problem. The time-dependent revenues and combination of selection and scheduling as well as time-dependent setup times in agile earth-observing satellite mission planning, which also exist extensively in other scheduling areas, are analyzed in the dissertation. Subsequently, studies are carried out on the following subjects, which are original contributions of the dissertation.(1) Algorithm for solving the earliness-tardiness scheduling problems is put forward.The earliness-tardiness scheduling is a typical scheduling problem with time-dependent revenues. The penalty caused by processing a job is not fixed but is dependent on the end time of processing. The mathematical formulations of the earliness-tardiness scheduling problem with distinct release date, due date, earliness penalty weight and tardiness penalty weight are put forward under single and parallel machine environments respectively. A memetic algorithm is proposed for the single machine problem. An improved optimal timing algorithm considering distinct release dates and setup times is put forward to fix the starting time and to calculate the objective under a given processing sequence. Experimental studies suggest the fine performance of proposed algorithm compared with classical genetic algorithm and OPL. The memetic algorithm proposed for the single machine environment is then modified for the parallel machine environment. An improved constructive heuristic for selecting machine and fixing the starting time is also proposed. The two algorithms are compared through experimental studies. Suggestions are given for the application of the two algorithms.(2) Algorithm for solving the order acceptance and scheduling is proposed.Order acceptance and scheduling problem combines selection and scheduling with time-dependent revenues. The decisions of selection and scheduling, which select a subset of orders and fix the starting time of them, have to be made integrally to maximize the revenues of scheduled orders. The revenue for processing an order depends on the end time for processing. The mathematical model is formulated and a diversity-controlling genetic algorithm is proposed. A diversity measurement is put forward for measuring the difference between individuals. A diverse population is maintained during the whole search procedure by the diversity controlling strategy. Iterated greedy heuristic based on destruction and construction is applied as the local search algorithm. Compared with five other algorithms, experimental results on large number of benchmark instances improved the efficacy of the proposed algorithm.(3) Algorithm for Multiple-Time-Dependent Scheduling problem is proposed.The problem that is characterized by a combination of time-dependent setup times, selection and scheduling and time-dependent revenues is studied. This problem is the order acceptance and scheduling problem combined with time-dependent setup times as well as earliness-tardiness penalties, which is rather complex and hard to solve. A real number between 0 and 1 is adopted as the encoding, which represents the ratio of the end time for processing to the length of the time window. Given a real number vector, the starting and end time of each job is pre-fixed by the real number in the vector. The setup time between different jobs can then be obtained by the starting and end time of each job. A directed acylic graph is constructed according to the starting and end time of each job as well as the setup times. The nodes in the longest path in the graph represent the scheduled jobs. The length of the path is the objective of the vector, i.e., the sum of revenues of all the scheduled jobs. A graph-based fitness evaluation hybrid differential evolutionary algorithm is proposed. The efficacy is improved by experimental studies compared with three other algorithms.(4) The application on agile earth observing satellite mission planning.Take an agile earth observing satellite under production for example to illustrate the application of the proposed time-dependent scheduling methods.The attitude maneuver time function of a practical agile earth observing satellite is adopted as the computational method for getting the time-dependent setup times. The experimental resutls show that the proposed time-dependent scheduling methods can greatly improve the revenue of image quality obtained by the agile earth observing satellite.