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

o название темы

o содержание темы

o основная литература

o дополнительная литература

Модуль 3, has 16 hours

1. Introduction to single machine scheduling theory and its applications. 4 hours.

This lecture and corresponding seminar focuses on both the theory and the applications of scheduling. The theoretical side deals with the detailed sequencing and scheduling of jobs. Given a collection of jobs requiring processing in a certain machine environment, the problem is to sequence these jobs, subject to given constraints, in such a way that one or more performance criteria are optimized. This lecture deals with deterministic scheduling models defined on a single machine. It is assumed that there are a finite number of jobs. Emphasis is placed on the analysis of relatively simple priority or dispatching rules. We discuss the notation and give an overview of the models that are considered in the subsequent lectures and seminars. A special attention will be given to didactical and methodological tools of our research activities including some general hints to how write a research paper in scheduling theory and how to make an impressive presentation of obtained results.

Literature. SCH[1-9, 17-24,29]

Additional Literature. SCH[30-34]

2. Overview of algorithmic complexity in single machine scheduling theory. 4 hours.

Complexity theory is based on a mathematical framework developed by logicians and computer scientists. This theory was developed to study the intrinsic

difficulty of algorithmic problems and has proven very useful for combinatorial

optimization problems. In complexity theory a distinction is made between optimization problems and decision problems. The question raised in a decision problem requires either a yes or a no answer. These decision problems are therefore often also referred to as yes-no problems. With every optimization problem one can associate a decision problem. For example, in the Problem 1 the total weighted completion time has to be minimized. In the associated decision problem the question is raised whether there exists a schedule with the total weighted completion time less than a given value z. It is clear that the optimization problem and the related decision problem are strongly connected. Actually, if there exists a polynomial time algorithm for the optimization problem, then there exists a polynomial time algorithm for the decision problem and vice versa. A fundamental concept in complexity theory is the concept of problem reduction. Very often it occurs that one combinatorial problem is a special case of another problem, or equivalent to another problem, or more general than another problem. Often, an algorithm that works well for one combinatorial problem works as well for another after only minor modifications.

In scheduling theory it is often of interest to determine the borderline between polynomial time problems and NP-hard problems. In order to determine the exact boundaries it is necessary to find the “hardest” or the “most general” problems that still can be solved in polynomial time. These problems are characterized by the fact that any generalization, e. g., the inclusion of precedence constraints, results in NP-hardness, either in the ordinary sense or strongly. In the same vein it is of interest to determine the “simplest” or “least general” problems that are NP-hard, either in the ordinary sense or strongly. Making such a strongly NP-hard problem easier in any respect, e. g., setting all equal to 1, results in a problem that is either solvable in polynomial time or NP-hard in the ordinary sense. In addition, it is also of interest to determine the most general problems that are NP-hard in the ordinary sense, but not strongly NP-hard. A significant amount of research has focused on these boundaries. However, the computational complexity of a number of scheduling problems has not yet been determined and the borderlines are therefore still somewhat fuzzy.

Literature. SCH[5, 10, 11, 14]

a. B. Goldengorin. Quantitative Logistics. 20 Lectures in Combinatorial Optimization. Syllabus. Operations Department, University of Groningen, The Netherlands, 2009, Lecture 20.

3. Fundamental properties of weighted versions for single machine scheduling problems. 4 hours.

Consider the following simple example for the Problem 1 with 2 jobs, release dates r1 = 0, r2 = 1 and equal processing times p = 2. Depending on the job weights either the schedule (1; 2; 2; 1) or (1; 1; 2; 2) is optimal. The feasible schedule (1; 2; 1; 2) can never be optimal since (1; 1; 2; 2) has a strictly better objective value irrespective of the weights. It appears that,

when it is profitable to interrupt job 1, job 2 is fully processed before job 1 is resumed. A generalization of this property is given in this lecture. It should be noted that this property is a direct consequence of Lemma 2.1 introduced by Tian et al. [34]. This lemma states that in a p-active schedule, job i is either fully processed before job j is started, or job I is interrupted by job j and not resumed before job j is completed. This implies that if job i is interrupted, it is interrupted for p = 2 or a multiple of p time units. Note that a preemptive schedule is p-active if no job's completion time can be advanced without postponing the completion time of some other job. It is not difficult to show that an optimal preemptive schedule is p-active when

the total weighted completion time is minimized.

Literature. SCH[34]

a. H. Bouma. All Minimal and Maximal Open Single Machine Scheduling Problems are Pseudo-Polynomially Solvable. MSc Thesis, University of Groningen, The Netherlands, 2009.

4. Complete enumeration of possible completion (tardiness) times. 4 hours.

In this lecture we assume that all jobs might be scheduled without idle time intervals. In case of the Problem 1 and n jobs the total number of time intervals is equal to T=2n. Since all jobs have the same processing time p = 2 the total number of job parts number of job parts is equal to T. It means that for each starting job part we are able to assign a “dummy” weighted processing time depending on the starting time interval which will be not taken into account in the total weighted processing time, but for each completed job part we will assign a weighted completion time depending on the completing time interval which will be taken into account in the total weighted processing time. We call such an assignment of contributions to the objective function a complete enumeration of all job parts depending on the corresponding time intervals. Similar considerations will be discussed for the total weighted tardiness of each job part with respect to the due dates. We complete this lecture by some examples of scheduling rules and introduce a new scheduling rule based on the notion of the dynamic (time dependent) weighted remaining processing time.

Literature.

a. B. Goldengorin. . When preemptive schedules of equal-length jobs to minimize

the weighted completion time should be (not) interrupted. Unpublished manuscript. 2010.

Additional Literature. SCH[1, 4, 5, 33]

Модуль 4, has 40 hours

5. The Assignment Problem in single machine scheduling models and algorithms. 2 hours.

Taking into account that each time interval must be assigned to exactly one job part and each job part must be assigned to exactly one time interval we will discuss how to formulate the Problem 1 in terms of the Assignment Problem with additional constraints keeping the right order of starting job part and completed job part for the jab j. We discuss the relationships between the Problem 1 and a polynomial solvable case of the axial three-dimensional assignment model from Gilbert and Hofstra [15]. Moreover, we formulate an open problem how to reschedule an optimal assignment problem schedule for all jobs with violated order of starting and completing parts.

Literature. SCH[6, 15, 19]

a. B. Goldengorin. Quantitative Logistics. 20 Lectures in Combinatorial Optimization. Syllabus. Operations Department, University of Groningen, The Netherlands, 2009, Lecture 4.

b. R. Burkard, M. Dell’Amico, S. Martello. Assignment Problems. SIAM Monographs on Discrete Mathematics and Applications, SIAM, Philadelphia, 2009.

Additional Literature SCH[25-28]

c. B. Goldengorin,  G. Jager. The Computational Efficiency of Ji-Lee-Li Algorithm for the Assignment Problem.  Algorithmic Operational Research, 3(1), 79--81, 2008.

d. M. Dell’Amico and P. Toth. Algorithms and codes for dense assignment problems:

The state of the art. Discr. Appl. Math., 100:17–48, 2000.

6. Patterns for the Problem 1 in terms of the Assignment Problem. 2 hours.

Any collection of AP entries is called a pattern. In terms of a permutation of rows or columns by means of patterns we reduce many combinatorial optimization problems to the AP. In this seminar we try to define such patterns that each starting job part will be scheduled before completing job part and the total weight of assigning all kob parts to all time intervals is minimized.

Literature.

a. B. Goldengorin. Schedules with Careful Checking: a Generalization of the Assignment Problem. Unpublished Manuscript, 2010.

7. Time indexed MILP formulations of the Problem 1. 2 hours.

In this lecture we combine the restrictions of classical assignment problem with the following property of feasible but non-optimal schedules for the Problem 1. In an optimal schedule of the Problem 1 there are either zero or an even number of time intervals between the intervals to which the _firrst (starting) and second (completing) part of a particular job are assigned.

It means that there is an optimal solution to the Problem in which preemption occurs at unit points in time only. This fact implies the so called time indexed formulation of the Problem 1 as follows.

The first collection of assignment type constraints ensure that each first respectively second part of a job is processed for the duration of at least one time interval. The second collection of constraints take care of the fact that each time interval is assigned to exactly one job part. Since the number of job parts is equal to the number of time intervals, it immediately follows from the first and second collections of constraints that each job part is assigned to exactly one time interval. The above indicated property is incorporated by means of the third collection of constraints which together assure that one cannot start processing the second part of a job before the _first part is processed. Furthermore, they assure that the number of time intervals that lies between the processing of the_first and second part of a job is either zero or even.

Literature. SCH[7, 8, 13]

a. B. Goldengorin. Quantitative Logistics. 20 Lectures in Combinatorial Optimization. Syllabus. Operations Department, University of Groningen, The Netherlands, 2009, Lecture 5.

b. H. Bouma, B. Goldengorin. A Polytime Algorithm Based on Primal LP Model for the Scheduling Problem 1| pmtn; pj=2; rj | ∑wjCj. RECENT ADVANCES in APPLIED MATHEMATICS: Proceedings of the AMERICAN CONFERENCE in APPLIED MATHEMATICS (AMERICAN-MATH’10, Harvard University, Cambridge, USA, January 27-29, 2010. Published by WSEAS Press, pp.415--420.

Additional Literature SCH[30, 31]

8. Generalization of the Problem 1 for an arbitrary processing time. 2 hours.

First we generalize the main property of Problem 1 to the problem with a general processing time p as follows.

In an optimal schedule of the Problem 1 with general processing time p there are either zero, or a multiple of p time intervals between the intervals to which two subsequent parts of a job are assigned.

Note that all constraints are similar to constraints of the Problem 1 and assure that each job part is assigned to at least one time interval. Further constraints state that exactly one job part must be assigned to each time interval. These constraints correspond to the first collection of constraints used in the time indexed MILP formulation of the Problem 1. Similarly, there is a set of constraints that states that the job parts have to be processed in the right order and that the number of time intervals between two subsequent job parts is either zero or a multiple of .

Literature. SCH[17, 24. 29]

a. H. Bouma. All Minimal and Maximal Open Single Machine Scheduling Problems are Pseudo-Polynomially Solvable. MSc Thesis, University of Groningen, The Netherlands, 2009.

b. H. Bouma, B. Goldengorin. A Polytime Algorithm Based on Primal LP Model for the Scheduling Problem 1| pmtn; pj=2; rj | ∑wjCj. RECENT ADVANCES in APPLIED MATHEMATICS: Proceedings of the AMERICAN CONFERENCE in APPLIED MATHEMATICS (AMERICAN-MATH’10, Harvard University, Cambridge, USA, January 27-29, 2010. Published by WSEAS Press, pp..

9. The total weighted tardiness criterion with preemptions

In two previous lectures and corresponding seminars it was already mentioned that there is a strong similarity between the problems of minimizing the total weighted completion time and minimizing the total weighted tardiness. The only difference is that the costs of assigning _final job parts to time intervals are not only determined by the time interval under consideration, but also by the due date of the job. The structure of both problems is the same. This is reflected by a variation of the main property that holds true when the total weighted tardiness is minimized as follows.

There always exists an optimal schedule for the problem minimizing the total weighted tardiness, in which there are either zero or a multiple of time intervals between the intervals to which two subsequent parts of a job are assigned. In this lecture and corresponding seminar we adjust the objective function values depending on the current time interval and due date which imply our formulation of time indexed MILP model for minimizing the total weighted tardiness with preemptions.

Literature. SCH[34]

H. Bouma. All Minimal and Maximal Open Single Machine Scheduling Problems are Pseudo-Polynomially Solvable. MSc Thesis, University of Groningen, The Netherlands, 2009.

J. M. van den Akker, G. Diepen, J. A. Hoogeveen. Minimizing total weighted tardiness on a single machine with release dates and equal-length jobs. J Sched (2010) 13: 561–576. DOI 10.1007/s181-1

10. The total weighted tardiness criterion without preemptions

The difference between the preemptive problem minimizing the total weighted tardiness and its non-preemptive counterpart, is that all job parts need to be scheduled successively, once the first job part is assigned to a time interval. This means that some of assignment constraints can be simplified in the non-preemptive case. It should be mentioned that an optimal schedule of the problem with preemptions might contain idle time intervals. As a consequence, the number of time intervals that needs to be considered is larger than T. The maximum number of idle time intervals in an optimal schedule is (n-1)(T-1). Therefore, all job parts have to be scheduled to one time interval t = 1,…, T, where T = (n-1)(T-1)+ np. Note that the (in)equalities in the first set of constraints are different in comparison with similar constraints in its preemptive counterpart. This is caused by the fact that in the

non-preemptive case the number of job parts is smaller than the number of time intervals. Further the first set of constraints assure that each job part is assigned to exactly onetime interval and the second set of constraints states that each time interval must be assigned to at most one job part. Finally, the third set of constraints states that the job parts have to be processed in the right order and successively.

Literature. SCH[29]

a. H. Bouma. All Minimal and Maximal Open Single Machine Scheduling Problems are Pseudo-Polynomially Solvable. MSc Thesis, University of Groningen, The Netherlands, 2009.

b. J. M. van den Akker, G. Diepen, J. A. Hoogeveen. Minimizing total weighted tardiness on a single machine with release dates and equal-length jobs. J Sched (2010) 13: 561–576. DOI 10.1007/s181-1,

c. Ph. Baptiste and V. Timkovsky. Shortest path to non-preemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time. Mathematical Methods of Operations Research Volume 60, Number 1, 145-153, 2004.

11. The min-sum location-allocation problems

In this lecture and corresponding seminar we introduce a general class min-sum location-allocation problems among which we select only two problems, namely the Simple Plant Location Problem (SPLP) and p-Median Problem (PMP). As sometimes happened, some of the designed formulations and algorithms were separately done for the PMP without taking into account the ongoing progress with model formulations for another common model within minisum location-allocation problems,

namely the SPLP, often referred to as the Uncapacitated Facility Location Problem (UFLP) (see Cornuejols et al. [15]) or the warehouse location problem (see e. g. ReVelle et al. [32]). The SPLP is similar to the PMP, and the methods used to solve one are often adapted to solve the other. The objective function of the SPLP is one of determining the cheapest method of meeting the demands of a set of clients J = {1,…, n} from plants that can be located at some candidate sites I ={1,…, m}. The costs involved in meeting the client demands include the fixed cost of setting up a plant at a given site, and the per unit transportation cost of supplying a given client from a plant located at a given site. The PMP and SPLP differ in the following details. First, SPLP involves a fixed cost for locating a facility at a given vertex, while the PMP does not. Second, unlike the PMP, SPLP does not have a constraint on the number of opened facilities. Typical SPLP formulations separate the set of potential facilities (sites location, cluster centers) from the set of demand points (clients). In the PMP these sets are identical, i. e. I = J. Such problems are well known in cluster analysis (see e. g., Brusco and Kohn [10] and references within). Both problems form underlying models in several combinatorial problems, like set covering, set partitioning, information retrieval, simplification of logical Boolean expressions, airline crew scheduling, vehicle dispatching (see Christofides [11]), assortment (see e. g., Goldengorin et al. [19], Pentico [28], ) and are subproblems of various location analysis problems (see ReVelle et al. [32]).

Literature. PMP(10, 11, 15, 19, 28, 32)

a. B. F. AlBdaiwi, D. Ghosh, B. Goldengorin. Data Aggregation for p-Median Problems. Journal of Combinatorial Optimization 2010 (open access, in press) DOI: 10.1007/s251-8.

b. B. Goldengorin, D. plexity evaluation of benchmark instances for the p-median puters and Mathematics with Applications. 2011 (in press)

12. The p-median problem and its applications

The objective of the p-Median problem (PMP) is to locate p facilities (medians) such that the sum of the distances from each demand point to its nearest facility is minimized. It has been widely studied in literature and applied in cluster analysis, quantitative psychology, marketing, telecommunications industry, sales force territories design, political districting and references within, optimal diversity management, cell formation in group technology, vehicle routing, and topological design of computer communication networks. We formulate the PMP as a minimization problem of a pseudo-Boolean polynomial (pBp) and linearize all non-linear terms in pBp by means of new non-negative variables and linear constraints reflecting the relationships between all embedded terms in pBp. The number of new variables is equal to the number of linear constraints and both of them decrease with increasing the number p of means of computational experiments we show that our model is able to solve to optimality some of PMP benchmark instances which were intractable by general-purpose MILP software and even by the state-of-the-art algorithms. Also, CPU times with our model

outperform CPU times for the best available PMP models. Finally, we formulate some open problems including research projects for the PMP.

Literature. PMP(1-7, 10).

a. AlBdaiwi, B. F., Ghosh, D., Goldengorin, B.: Data aggregation for p-median problems.

Journal of Combinatorial Optimization, DOI 10.1007/s25open access).

b. B. Goldengorin, D. Krushinsky. Towards an optimal mixed Boolean LP model of the p-Median problem. Unpublished manuscript, 2011.

13. The generalized p-median problem and its applications

In this lecture and seminar, we study the Simple Plant Location Problem (SPLP). A detailed introduction to this problem appears in Cornuejols et al. (1990). The goal of the problem is one of determining a cheapest method of meeting the demands of a set of clients from plants that can be located at some candidate sites. The costs involved in meeting the client demands, include the fixed cost of setting up a plant at a given site, and the per unit transportation cost of supplying a given client from a plant located at a given site. This problem forms the underlying model in several combinatorial problems, like set covering, set partitioning, information retrieval, simplification of logical Boolean expressions, airline crew scheduling, vehicle dispatching and is a subproblem for various location analysis problems (see AlBdaiwi et al., 2010). We will assume that the capacity at each plant is sufficient to meet the demand of all clients. We will further assume that each client has a demand of one unit, which must be met by one of the opened plants. If a client's demand is different from one unit, we can scale the demand to unity by scaling the transportation costs accordingly. We discuss well known BnB type algorithms for solving the SPLP and more advanced algorithms based on pseudo-Boolean approach.