Программа научного семинара «Mетоды анализа и выбора решений» (стр. 3 )

Now consider the airline company. It needs to assign airplanes to flights such that none of the flights is cancelled. The cost of assigning a certain type of aircraft to a particular flight is known in advance. Each flight is characterized by a departure and arrival time and by the expected number of passengers. Each airplane has a certain capacity. Obviously, it is desirable that an airplane has sufficient capacity to carry all passengers, since otherwise a certain amount of revenue is missed. On the other hand, when there is overcapacity the revenues may not be sufficient to cover the flight's costs. Given the departure and arrival time, the cost of a flight, the expected number of passengers per flight and the revenue per passenger, the airline is interested in assigning its airplanes to flights such that total profits are maximized.

These examples show that scheduling problems arise frequently in practice and often involve a company's core business. Therefore, considerable amounts of attention have been paid to scheduling techniques in the literature for over fifty years. Pinedo (2008) defines scheduling as the allocation of limited resources to activities that have to be done over time. This allocation needs to be such that a company optimizes its objectives and achieves its goals. In the examples stated above, the photocopiers in the copy shop and the fleet of the airline company are the resources. The activities are the orders and the flights. The objectives are to minimize the total amount of discount and to maximize profits respectively.

Scheduling techniques rely heavily on mathematical models, exact algorithms and heuristics. For many problems efficient algorithms have been found to solve the problems to optimality. However, there are still many problems that have not been solved yet. In this seminar new models for three of these unsolved scheduling problems will be presented and studied. In the first three seminars after an overview of single machine scheduling problems the students going to present some basic concepts of computational complexity and Integer Linear Programming. These basic concepts will be illustrated by means of the simplest case of Problem 1, defined for all jobs with processing times equal 2 (p=2). The notions of unimodular and totally unimodular matrices as well as total dual integrality for systems of linear inequalities will be presented by students. Moreover, three groups of students will be able to show that our new LAP based formulation for Problem 1 doesn’t satisfy to any of the above mentioned notions, i. e. its matrix is either not unimodular or even not totally unimodular. Moreover, the corresponding pair of primal and dual problems is not a total dual integral system. Having that no of the well known notions cannot be used to indicate the complexity status of Problem 1, we are going to use the Branch-and-Bound algorithms idea to prove that the Problem 1 is pseudo-polynomially solvable.

First of all we are going to ask our students to study a manual of any Linear Programming solver (in fact, here in Nizhny Novgorod branch, we have a general purpose LP solver incorporated into the well known software ILOG). By means of the chosen LP solver the students going to solve some benchmark (computationally difficult) instances of the Problem 1. During such experiments different groups of students will be able to “discover” the following property of our LAP based mathematical model: if an LP solver terminates with an integer solution then this solution is an optimal schedule to the Problem 1. If an LP solver returns a non-integer (fractional) optimal solution, then there are at least two other optimal schedules with the same value of objective function as the value of fractional optimal solution. Based on these observations the students will be challenged by the following research questions.

Question 1. Construct an algorithm with its computational complexity at most pseudo-polynomial which transforms a non-integer (fractional) solution into an integer (Boolean) one.

Question 2. Let us introduce a new type of polyhedrons for the Problem 1 which we call mixed integer polyhedrons with the following property: for each fractional corner point feasible (optimal) solution there are at least two integer corner point feasible (optimal) solutions. Show that your algorithm from question 1 returns an integer (Boolean) solution with the same value as the fractional LP based optimal solution.

Based on our study of the Problem 1 we are going to present a Mixed Integer Linear Programming model for generalized equal processing times with p>2 and repeat all steps of our study which we have done for the case with p=2.

Further we are going to use our reductions of two other single machine scheduling problems minimizing the total weighted tardiness. The second problem is preemptive and in case with p=2 will be denoted as the Problem 2, the third problem is a non-preemptive version of Problem 2 and denoted as the Problem 3.

Место курса в системе формируемых инновационных квалификаций

Our scientific seminar covering all three single machine scheduling problems with an open computational status will lead to an innovative result which show that all these three problems are pseudo-polynomially solvable. The place of these three problems not only in scheduling theory and practice is very important for various reasons (see Pinedo, 2008).

The single machine environment is very simple and a special case of all other environments. Single machine models often have properties that neither machines in parallel nor machines in series have. The results that can be obtained for single machine models not only provide insights into the single machine environment, they also provide a basis for heuristics that are applicable to more complicated machine environments. In practice, scheduling problems in more complicated machine environments give rise to a single machine model.

Our scientific seminar devoted to the mentioned above three single machine scheduling problems with an open computational status analyzing in fact various single machine scheduling models in detail. The total weighted completion time objective is considered first, followed by several due date related objectives, including the maximum lateness, the number of tardy jobs, the total tardiness and the total weighted tardiness. In most models considered in this seminar there is no advantage in having preemptions; for these models it can be shown that the optimal schedule in the class of preemptive schedules is non-preemptive. However, if jobs are released

at different points in time, then it may be advantageous to preempt. If jobs are released at different points in time in a non-preemptive environment, then it may be advantageous to allow for unforced idleness (i. e., an optimal schedule may not be non-delay).

Moreover, this seminar creates a clear link to some hot topics in integer and mixed integer Linear Programming, computational complexity, and shows that many other problems in decision making with an open computational status might be solved successfully even we have not found an answer to the main question in computational complexity theory whether the given specific problem is, for example, polynomially solvable, NP-hard or have some other computational complexity status. It means that for all problems with unknown computational complexity status we are able to create an implicit enumeration algorithm, like Branch-and-Bound or any of its essential variations, e. g. Dynamic Programming, Branch-and-Cut, Branch-and-Cut-and-Price, Branch-and-Win, Cut-and-Solve, Data Correcting, and many others.

To summarize, this seminar creates an innovative approach to analyze not only scheduling problems but many other problems in decision making research and industry, and related to the following skills preferred by many employers.

Many employers prefer applicants with a master's degree in operations research, management science, or a closely related field—such as computer science, engineering, business, applied mathematics, or information systems. Dual graduate degrees in operations research and computer science are especially attractive to employers. This research seminar creating a natural bridge for numerous degree programs in operations research and closely related fields in colleges and universities across the Russian Federation.

Continuing education is important for operations research analysts. Keeping up to date with technological advances, software tools, and improvements in analytical methods is vital for maintaining their problem-solving skills.

Since scheduling theory is a multi-disciplinary field, a background in technologies of political science, economics, statistics, engineering, accounting, and management can also be useful. The participants who has successfully completed this research seminar will be able to think logically, work well with people, and write and speak well in English.

II. Содержание научного семинара

1. Новизна научного семинара (научная, содержательная; сравнительный анализ с подобными курсами в России и за рубежом, курсами, читаемыми в НИУ ВШЭ)

Scheduling is a decision-making process that is used on a regular basis in many manufacturing and services industries. It deals with the allocation of resources to tasks over given time periods and its goal is to optimize one or more objectives.

The resources and tasks in an organization can take many different forms. The resources may be machines in a workshop, runways at an airport, crews at a construction site, processing units in a computing environment, and so on. The tasks may be operations in a production process, take-offs and landings at an airport, stages in a construction project, executions of computer programs, and so on. Each task may have a certain priority level, an earliest possible starting time and a due date. The objectives can also take many different forms. One objective may be the minimization of the completion time of the last task and

another may be the minimization of the number of tasks completed after their respective due dates.

Scheduling, as a decision-making process, plays an important role in most

manufacturing and production systems as well as in most information processing environments. It is also important in transportation and distribution settings and in other types of service industries like supply chain management and operational logistics systems.

The above mentioned three single machine scheduling problems are single machine scheduling problems with remaining open computational status. Professor Philippe Baptiste at his website http://www. lix. polytechnique. fr/alco/openPbs looking for any progress with a general case of the Problem 1 and discussing some special cases of this problem as follows.

Minimizing total waiting time in preemptive equal job length scheduling or 1|rj;pj=p;pmtn|Σ wjCj

This is an open problem. If you make some progress it would be nice to let us know: Ph. Baptiste, Marek Chrobak, C. Dürr, Jiri Sgall. The notes above are not ready papers, but rough research drafts.

We are given n jobs. Each job j has a release time rj before which it is not available, a priority weight wj and each job has the same processing time p. Without loss of generality we assume that jobs are indexed according to their release times, that is r1 <=...<=rn. A preemptive schedule is a mapping which associates to every job a sequence of time intervals of total length p. For technical reasons the intervals are closed at the beginning and open at the end. All intervals -- including those of different jobs -- have to be disjoint. To be feasible the smallest starting time of the intervals associated to job j must be not earlier than rj. The latest ending time of the intervals is called the completion time of job j and denoted Cj. We wish to find a feasible preemptive schedule on one machine, which minimizes the total weighted completion time, which is defined as Σ wj Cj.

r1=0 r2=1 r3=3 r4=4 p=3

|___________________________________ w1=3

|_________________________________ w2=100

|_____________________________ w3=3

|___________________________ w4=10

|1|2 2 2|4 4 4|1 1|3 3 3| optimal schedule of cost 521

Fig 1: an example of an optimal schedule

It is easy to model the problem as an integer linear program with 0-1 variables Xi, t, where Xi, t=1 indicates that job i completes at time t. This linear program has two kind of natural constraints, (1) saying that a job completes eventually at some point not earlier than ri+p, and (2) that for any time interval [s, t] the number of jobs that are fully executed (the sum of Xi, u over u in [s, t] and over i such that ri ≥= s ) is at most (t-s)/p.

The conjecture is that the relaxed linear program (where you removed the integrality constraint) has always an integer solution. The linear program is not totally unimodular, that is the simplex described by it might have some fractional vertices, but there is still hope that in the direction of the objective function, there is always an integer vertex. This property of a linear program may sound strange to you, but it happens sometimes, see [Durr, Hurand'06:Finding total...].

In fact we were able to show this conjecture for the special case when rj=j-1 and p=n. This proof lead us to the dynamic program below.

The linear program and the proof of integrality of the solution for the mentioned special case The linear program in GNU Mathprog

If you try to find a polynomial algorithm for this problem, the simplest special case to start with could be to assume rj=j and p=2 and arbitrary weights of course. Based on the -classification scheme of Graham et al. (1979) Peter Brucker has updated the computational complexity status of all studied and well known scheduling problems at the website http://www. informatik. uni-osnabrueck. de/knust/class/ as follows. maximal polynomially solvable: the hardest problems which are polynomially solvable, i. e. problems which are known to be polynomially solvable, but any harder cases are not known to be polynomially solvable, maximal pseudopolynomially solvable: the hardest problems which are known to be pseudopolynomially (but not polynomially) solvable, minimal NP-hard: the easiest problems which are NP-hard, i. e. problems which are known to be NP-hard, but any easier cases are not known to be NP-hard, minimal open: problems for which the complexity status is not known, but all easier cases are known to be polynomially solvable, maximal open: problems for which the complexity status is not known, but all harder cases are known to be NP-hard. As indicated at Professor Brucker’s website http://www. informatik. uni-osnabrueck. de/knust/class/dateien/classes/ein_ma/ein_ma. pdf our first problem of minimizing the total weighted completion time, in which preemption is allowed, is minimal open. The preemptive version of the problem of minimizing the total weighted tardiness is maximal open and its non-preemptive version is both: minimal and maximal open.

Tian et al. (2006) have indicated a quadratic algorithm for unweighted (with equal weights) version of the preemptive problem minimizing the total tardiness. We are going to study this paper in detail with the purpose to understand whether we vare able to reduce a general weighted case to an equal-weights case even by increasing the computational complexity status of this problem from polynomially solvable to pseudo-polynomially solvable. Recently van den Akker et al (2010) have formulated the minimization of total weighted tardiness problem as a time-indexed ILP after which they solve the LP relaxation. For certain special cases (namely when either all due dates, all weights, or all release dates are equal, or when all due dates and release dates are equally ordered), the solution for the LP-relaxation is either integral or can be adjusted in polynomial time into an integral one. For the general case they present a branching rule that performs well. We are going to split our study to each of the presented cases with the purpose to find out how much any of the above mentioned sufficient conditions are essential for the corresponding special problem cases to be polynomially solvable and might be either relaxed or kept unchanged.

References:

P. Brucker (1998): Scheduling algorithms, 2nd edition, Springer, Heidelberg.

R. L. Graham, E. L. Lawler, J. K. Lenstra, A. H.G. Rinnooy Kan (1979): Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math. 4, 287-326.

B. J. Lageweg, E. L. Lawler, J. K. Lenstra, A. H.G. Rinnooy Kan (1981): Computer aided complexity classification of deterministic scheduling problems, Report BM 138, Centre for Mathematics and Computer Science.

Zhongjun Tian, C. T. Ng, T. C. Edwin Cheng: An O(n2) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness. J. Scheduling 9(4): 343-

J. M. van den Akker, Guido Diepen, J. A. Hoogeveen: Minimizing total weighted tardiness on a single machine with release dates and equal-length jobs. J. Scheduling 13(6): 561-

Тематический план учебной дисциплины (отражает содержание дисциплины (перечень тем), структурированное по видам учебных занятий с указанием их объемов)

Тематический план учебной дисциплины

№ п/п	Наименование тем и разделов	ВСЕГО (часов)	Аудиторные занятия (час)	Самостоятельная работа
в том числе
Семинар 1	Семинар 2
1	Introduction to single machine scheduling theory and its applications	7	2	2	3
2	Overview of algorithmic complexity in single machine scheduling theory	7	2	2	3
3	Fundamental properties of weighted versions for single machine scheduling problems	7	2	2	3
4	Complete enumeration of possible completion (tardiness) times	7	2	2	3
5	The Assignment Problem in single machine scheduling models and algorithms	7	2	2	3
6	Patterns for the Problem 1 in terms of the Assignment Problem	7	2	2	3
7	Time indexed MILP formulations of the Problem 1	7	2	2	3
8	Generalization of the Problem 1 for an arbitrary processing time	7	2	2	3
9	The total weighted tardiness criterion with preemptions	7	2	2	3
10	The total weighted tardiness criterion without preemptions	7	2	2	3
11	The min-sum location-allocation problems	7	2	2	3
12	The p-median problem and its applications	7	2	2	3
13	The generalized p-median problem and its applications	7	2	2	3
14	Pseudo-Boolean approach to optimal MILP for the min-sum location-allocation problems	7	2	2	3
	ИТОГО:	108	28	28	52

  III. Содержание программы - строится по разделам и темам; содержание темы может разделяться на вопросы для лекционных и практических занятий. Каждая тема содержит следующие элементы: