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

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.

4. Методология исследований в этом научном семинаре

Taking into account the open computational complexity status of all three above mentioned problems our didactically motivated approach to resolve these problems will be as follows.

First we will try to show that all of these problems are pseudo-polynomially solvable and if we will be successful we are going to design decision technology based on general purpose solvers. Otherwise, we are not giving up and keep to design some branch and bound type algorithms for solving each of the above three problems.

The common part of our didactical and organizational tools for the p-median and single machine scheduling problems is the mixed integer linear programming approach.

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. A justification for this research is that there is evidence (Brusco and Kohn 2008) that the PMP can provide better cluster reconstruction than alternative clustering procedures (the complete and average linkage, minimum variance, and K-means).

In this seminar 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 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 decrease with increasing the number p of medians. Moreover, both these numbers are minimal within the class of mixed Boolean LP models. A computational experiment has shown 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.

To keep my description of this seminar short I am not going to repeat similar didactical and organizational steps and tools for scheduling and PMP problems in details since as I have explained above the approach to both of these problems will be based on mixed integer linear programming (MILP) applied by means of general purpose MILP solvers.

Our list of references will be cited either by their current number or by authors’ names and consists of two sets with the following literature.

Bibliography for single machine scheduling problems.

[1] Baker, K. R. (1974). Introduction to Sequencing and Scheduling. New York:

John Wiley & Sons.

[2] Baker, K. R., E. L. Lawler, J. K. Lenstra and A. H.G. Rinnooy Kan (1983,

Mar.-Apr.). Preemptive scheduling of a single machine to minimize maximum

cost subject to release dates and precedence constraints. Operations

Research 31(2), 381-386.

[3] Bang-Jensen, J. and G. Gutin (2001). Digraphs: Theory, Algorithms and

Applications. London: Springer.

[4] Baptiste, P. (2000). Scheduling equal-length jobs on identical parallel machines.

Discrete Applied Mathematics 103, 21-32.

[5] Baptiste, P., P. Brucker, S. Knust and V. G. Timkovsky (2004). Ten notes

on equal-processing time scheduling. At the frontiers of solvability in polynomial

time. Quarterly Journal of the Belgian, French and Italian Operations Research Societies 2, 111-127.

[6] Baptiste, P., M. Chrobak, C. Durr, W. Jawor and N. Vakhania (2004).

Preemptive scheduling of equal-length jobs to maximize weighted throughput.

Operations Research Letters 32, 258-264.

[7] Baptiste, P., M. Chrobak, C. Durr and J. Sgall. A dynamical program

for the special case when p > max ri. Unpublished manuscript.

http://www. lix. polytechnique. fr/~durr/OpenProblems/1 rj pmtn pjp sumWjCj/

[8] Baptiste, P., M. Chrobak, C. Durr and J. Sgall. A linear program for the first open problem. Unpublished manuscript.

http://www. lix. polytechnique. fr/~durr/OpenProblems/1 rj pmtn pjp sumWjCj/

[9] Brucker, P. (2004). Scheduling Algorithms (4th ed.). Berlin: Springer Verlag.

[10] Brucker, P and S. plexity results for scheduling problems.

http://www. mathematik. uni-osnabrueck. de/research/OR/class/

[11] Chen, B., C. N. Potts and G. J. Woeginger (1998). A review of machine

scheduling: complexity, algorithms and approximability. In: D.-Z. Du and

P. M. Pardalos (Eds.), Handbook of Combinatorial Optimization, Volume

3, pp. 21-170. Boston, Dordrecht: Kluwer Academic Publishers.

[12] Du. J. and J. Y.-T. Leung (1990, Aug.). Minimizing total tardiness on one

machine is NP-hard. Mathematics of Operations Research 15(3), 483{495.

[13] Durr, C. Minimizing total waiting time in preemptive equal job length

Scheduling.

http://www. lix. polytechnique. fr/~durr/OpenProblems/1 rj pmtn pjp sumWjCj/

[14] Garey, M. R. and D. S. Johnson (1979). Computers and Intractability. A

Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman

and Company.

[15] Gilbert, K. C. and R. B. Hofstra (1988). Multidimensional assignment

problems. Decision Sciences 19(2), 306-321.

[16] Goldengorin, B. When preemptive schedules of equal-length jobs to minimize

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

[17] Graham, R. L., E. L. Lawler, J. K. Lenstra and A. H.G. Rinnooy Kan (1979).

Preemptive scheduling of uniform machines subject to release dates. Annals of Operations Research 5, 287-326.

[18] Jackson, J. R. (1955). Scheduling a production line to minimize maximum

tardiness. Research Report 43, Management Science Research Project,

University of California, Los Angeles.

[19] Kuhn, H. W. (1955). The Hungarian method for the assignment problem.

Naval Research Logistics Quarterly 2(1-2), 83-97.

[20] Lawler, E. L. (1977). A "pseudopolynomial" algorithm for sequencing jobs

to minimize total tardiness. Annals of Discrete Mathematics 1, 331-342.

[21] Labetoulle, J., Lawler, E. L., Lenstra, J. K. and Rinnooy Kan, A. H.G.

(1984). Preemptive scheduling of uniform machines subject to release

dates. In: W. R. Pulleyblank (Ed.), Progress in Combinatorial Optimiza-

tion, New York: Academic Press, 245-261.

[22] Lenstra, J. K., A. H.G. Rinnooy Kan (1978). Complexity of scheduling under

precedence constraints. Operations Research 26(1), 22-35.

[23] Lenstra, J. K., A. H.G. Rinnooy Kan and P. Brucker (1977). Complexity

of machine scheduling problems. Annals of Discrete Mathematics 1, 343-

362.

[24] Leung, J. Y-T. (2004). Handbook of Scheduling. Algorithms, Models and

Performance Analysis Chapman & Hall/CRC Computer and Information

Science Series. Boca Raton, Florida [etc.]: Chapman & Hall/CRC.

[25] Lieshout, P. M.D. and A. Volgenant (2007). A branch-and-bound algorithm

for the singly constrained assignment problem. European Journal

of Operational Research 176, 151-164.

[26] Mazzola, J. B. and A. W. Neebe (1986, Jul.-Aug.). Resource-constrained

assignment scheduling. Operations Research 34(4), 560-572.

108

[27] Muller, F. M., M. M. Camozzato and O. C. Bassi de Araujo (2001, April).

Exact algorithms for the imbalanced time minimizing assignment problem.

Electronic Notes in Discrete Mathematics 7, 122-125.

[28] Pinedo, M. L. (2005). Planning and Scheduling in Manufacturing and Ser-

vices. Springer Series in Operations Research and Financial Engineering.

New York: Springer.

[29] Pinedo, M. L. (2008). Scheduling. Theory, Algorithms and Systems (3rd

ed.). New York: Springer.

[30] Schrijver, A. (1994). Theory of Linear and Integer Programming. Chichester

[etc.]: John Wiley & Sons.

[31] Sierksma, G. (2002). Linear and Integer Programming. Theory and Prac-

tice (2nd ed.). New York [etc.]: Marcel Dekker, Inc.

[32] Simons, B (1983). Multiprocessor scheduling of unit-time jobs with arbitrary

release times and deadlines. SIAM Journal on Computing 12, 294-299.

[33] Smith, W. E. (1956). Various optimizers for single-stage production. Naval

Research Logistics Quarterly 3, 59-66.

[34] Tian, Z. J., C. T. Ng and T. C.E. Cheng (2006). An O(n2) algorithm for

scheduling equal-length preemptive jobs on a single machine to minimize

total tardiness. Journal of Scheduling 9, 343-364.

Bibliography for the PMP

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

Journal of Combinatorial Optimization, DOI 10.1007/s25in press)

2. AlBdaiwi, B. F., Goldengorin, B., Sierksma, G.: Equivalent instances of the simple plant

location puters and Mathematics with Applications, 57, 812{

3. Avella, P., Sforza, A.: Logical reduction tests for the p-median problem. Annals of Operations Research, 86, 105{

4. Avella, P., Sassano, A., Vasil'ev, I.: Computational study of large-scale p-median problems.

Mathematical Programming, Ser. A, 109, 89{

5. Belenky, A. S. (Editor): Mathematical modeling of voting systems and elections: Theory

and Applications. Mathematical and Computer Modeling, 48(9-10), 1295{1

6. Beresnev, V. L.: On a problem of mathematical standardization theory. Upravliajemyje

Sistemy, 11, 43{54 (1973) (in Russian)

7. Beltran, C., Tadonki, C., Vial, J.-PH.: Solving the p-median problem with a semi-

Lagrangian putational Optimization and Applications, 35, 239-260

(2006)

8. Boros, E., Hammer, P. L.: Pseudo-Boolean optimization. Discrete Applied Mathematics,

123, 155{

9. Briant, O., Naddef, D.: The optimal diversity management problem. Operations Research,

52, 515{

10. Brusco, M. J., Kohn, H.-F. Optimal partitioning of a data set based on the p-median

problem. Psychometrika, 73(1), 89-

11. Christofides, N.: Graph Theory: An Algorithmic Approach. Academic Press Inc. Ltd.,

London (1975)

12. Church, R. L.: COBRA: a new formulation of the classic p-median location problem.

Annals of Operations Research, 122, 103-

13. Church, R. L.: BEAMR: An exact and approximate model for the p-median problem.

Computers & Operations Research, 35, 417-

14. Cornuejols, G., Nemhauser, G., Wolsey, L. A.: A canonical representation of simple plant

location problems and its applications. SIAM Journal on Matrix Analysis and Applications

(SIMAX), 1(3), 261-

15. Cornuejols, G., Nemhauser, G. L., and Wolsey, L. A.: The uncapacitated facility location

problem. In: Mirchandani, P. B., Francis, R. L. (eds) Discrete Location Theory. Wiley-

Interscience, New York (1990)

16. Dearing, P., Hammer, P. L., and B. Simeone. Boolean and Graph Theoretic Formulations

of the Simple Plant Location Problem. Transportation Science,26, No. 2, 138{

17. Elloumi, S.: A tighter formulation of the p-median problem. Journal of Combinatorial

Optimization, 19, 69{83 (2010)

18. Garey, M. R., Johnson, D. S.: Computers and Intractability. Freeman (1979)

19. Goldengorin, B., Tijssen, G. A., Ghosh, D., Sierksma, G.: Solving the simple plant location problems using a data correcting approach. Journal of Global Optimization, 25, 377{

20. Hakimi, S. L.: Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research, 12, 450-

21. Hakimi, S. L.: Optimum distribution of switching centers in a communication network

and some related graph theoretic problems. Operations Research, 13, 462-

22. Hammer, P. L.: Plant location { a pseudo-Boolean approach. Israel Journal of Technology,

6, 330{

23. Koskosidis, Y. A., Powell, W. B.: Clustering algorithms for consolidation of customer orders into vehicle shipments. Transportation Research 26B, 365-

24. Mirkin, B.: Clustering For Data Mining: A Data Recovery Approach (Chapman &

Hall/Crc Computer Science), Chapman & Hall/CRC, London, (2005)

25. Mladenovic, N., Brimberg, J., Hansen, P., Moreno-Perez, J. A.: The p-median problem:

A survey of metaheuristic approaches. European Journal of Operational Research, 179,

927-

26. Mulvey, J. M., Beck, M. P.: Solving capacitated clustering problems. European Journal of

Operational Research 18, 339-

27. OR-Library. Available at the web address

http://people. brunel. ac. uk/mastjjb/jeb/orlib/pmedinfo. html

28. Pentico, D. W.: The assortment problem: A survey. European Journal of Operational

Research 190, 295-

29. Pirkul, H.: Efficient algorithms for the capacitated concentrator location puters and Operations Research 14(3), 197-

30. Reese, J.: Solution Methods for the p-Median Problem: An Annotated Bibliography.

Networks 48, 125{

31. ReVelle, C. S., Swain, R.: Central facilities location. Geographical Analysis 2, 30{42 (1970)

32. ReVelle, C. S., Eiselt, H. A., Daskin, M. S.: A bibliography for some fundamental problem

categories in discrete location science. European Journal of Operational Research 184,

817{

33. Rosing, K. E., ReVelle, C. S., and Rosing-Vogelaar, H.: The p-Median and its Linear Programming Relaxation: An Approach to Large Problems. Journal of the Operational Research Society 30, 815-

34. Senne, E. L.F., Lorena, L. A.N., Pereira, M. A.: A branch-and-price approach to p-median

location puters & Operations Research 32, 1655-1

35. Schrijver, binatorial Optimization. Polyhedra and Efficiency. Springer (2003)

36. TSP{library. Available at the web address

http://www. iwr. uni-heidelberg. de/groups/comopt/software/TSPLIB95/.

37. Wolsey, L.: Mixed integer programming. Wiley Encyclopedia of Computer Science and

Engineering, edited by Benjamin Wah. John Wiley & Sons, Inc. (2008)

38. Won, Y., Lee, K. C.: Modified p-median approach for efficient GT cell puters & Industrial Engineering 46, 495-

Note that citing of these references will be done in square brackets for scheduling problems and just in brackets for location-allocation problems, for example SCH[1, 3-5] and PMP (1, 3-5), respectively.

2. Задачи научного семинара

(i) to formulate the following three open problems in single machine scheduling theory with equal-length jobs and different release dates. The objective of the first problem, in which preemption is allowed, is to minimize the total weighted completion time. The objective of the other two problems is to minimize the total weighted tardiness. The second problem is preemptive, the third is not. To this date, the complexity status of these problems has remained open, which was noticed by Labetoulle et al. in 1984;

(ii) to study some advanced methods for formulation and complexity analysis of scheduling problems based on patterns in the Linear Assignment Problem (LAP) and its variations.

(iii) to show that all these three single machine scheduling problems might be modeled in a unified form and have the same computational complexity status;

(iv) to concentrate our study on different LAP based models for the single machine scheduling of equal-length jobs with processing time 2, preemptions, different release dates and weights minimizing the total weighted completion time (further Problem 1).

(v) to show that the Problem 1 is pseudo-polynomially solvable, and hence its general case as well as both problems minimizing the total weighted tardiness are pseudo-polynomially solvable.

(v) to make familiar all participants of this seminar how to write a research report (paper) and present scientific results.

3. Методическая новизна научного семинара (новые методики, формы работы, авторские приемы в проведении исследований)

The seminar will be organized as follows. First of all we are going to motivate these research by means of some examples. Next we are going to present an interpretation of the Problem 1 in terms of a complete enumeration of all possible completion times for each released job. Based on all possible completion times for all jobs we are going to present different formulations of the Problem 1 as the LAP with additional constraints reflecting preemption of jobs. An intermediate question here whether we are able to find such a pricing of dummy parts of each job such that no dummy part will be “completed” after completion moment for each released job. Anyway our starting point for this seminar will be to present some simple motivation examples as follows.

In many manufacturing and service industries planning and scheduling belong to the day-to-day activities. Whether it is about a copy shop holder who needs to determine which order to print first, or the type of aircraft that should be assigned to a particular flight, the decisions made can seriously affect the efficiency or profitability of a company.

Consider for example a copy shop holder, who serves several business clients. Some orders are urgent, while others are not. A report that is just finished and should be presented the following morning has higher priority for a firm than the quarterly staff magazine. The urgency of an order is given by the difference between the deadline of an order and the point in time the order actually comes in at the copy shop. This is the so-called time window. Furthermore, each order has a different processing time, depending on its size, the quality etc. Last but not least, each order has a certain weight. When the copy shop holder does not meet a deadline, the client receives a discount based on the amount of delay and the weight of the order. Naturally, urgent and large orders have higher weights than low priority and small jobs. Given all orders, the copy shop holder would like to determine the printing schedule such that the total amount of discount is as small as possible.