Plenary Lecture 6 A Method for a Class of Scheduling Problems

摘要

Discrete (combinatorial) optimization problems are of a significant practical interest. A set of constraints specify feasible solutions, while a solution which minimizes (maximizes) the given objective function is an optimal one. Typically, we are looking for an optimal or near to the optimal feasible solution. The set of the feasible solutions is always finite, thus there is no major difficulty from the mathematical point of view: we just need to generate all the feasible solutions determining one with the minimal (maximal) value of the objective function. But this might be practically impossible when the number of feasible solutions grows exponentially with the length of the input. Scheduling problems, with which we deal in this talk, constitute a part of the combinatorial optimization problems. They deal with a finite set of requests (usually called tasks or jobs) which have to be performed on a finite set of resources (usually called machines or processors). A job in a factory or a program in a computer system or a lesson in a school are examples of requests. A machine in a factory or a processor in a computer system or a teacher in a school are examples of resources. Each request has its processing requirement, i.e., it needs a prescribed time on a resource, and usually a resource cannot handle more than one request at a time (for example, a teacher cannot give two lessons simultaneously). Besides, there are a limited number of resources and time is also limited, so that we need to arrange an order in which the requests are handled by the resources to make the total elapsed time as small as possible. We may have different time objective functions (usually non-decreasing), which we wish to minimize or maximize. We may also have some additional restrictions on the orderings which we admit (for example, some lessons should be given before the others). Although the number of all possible admissible orderings or the feasible solutions is finite, it might be extremely large.In this talk we will discuss a method that permits to construct efficient direct combinatorial polynomial-time algorithms for a class of scheduling problems in which the jobs are released (become available) at different time moments, whereas we wish to complete each job by a specified time moment, the so-called due-date. Our objective is to minimize a non-decreasing (time) objective function. Using this method, we were able to improve a number of existing algorithm and have solved some earlier open problems. The method classiffies jobs into exible and rigid ones. Intuitively, the exible jobs are free to be moved easily without becoming late, whereas the movement of the rigid jobs is quite restricted. We show that the exible jobs need to be distributed in between the rigid ones in a way that uses the space in-between different sequences of rigid jobs in some optimal manner. In this way versions of a better known bin backing problem arise. Our algorithms use different strategy for finding such an optimal job partition. Some of them construct it iteratively: a new schedule, associated with a node in a search tree, is generated at each iteration. These schedules are derived from the neighborhood which we define. In other algorithms, finding the above partition is considered as an independent auxiliary problem.