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

Literature. PMP(23, 26).

a. Yunqiang Yin, Dehua Xu. Some single-machine scheduling problems with general effects of learning and deterioration. Computers and Mathematics with Applications–108.

14. Pseudo-Boolean approach to optimal MILP for the min-sum location-allocation problems

In these final lecture and seminar we discuss a general approach to solve the SPLP by means of the Generalized PMP (GPMP) as follows. As we have shown in our previous lectures and seminars a new Mixed Boolean pseudo-Boolean Linear Programming Model (MBpBLPM) can be designed for both problems, namely the SPLP and GPMP. The participants of this seminar will be able to check whether a MBpBLPM will be more efficient than other available in literature models for solving them to optimality by means of general purpose solvers, like EXPRESS, CPLEX, etc. One of the suggested approaches to solve the SPLP by means of the GPMP will be based on introduction a variational cardinality constraint on the number of opened plants into the SPLP with the purpose to truncate the corresponding pseudo-Boolean polynomial of the SPLP and, hence, to reduce the size of the corresponding linearized pseudo-Boolean polynomial.

Literature. PMP(5, 8, 16, 33).

Additional literature. PMP(35, 37, 38).

Оценочные средства для текущего контроля и аттестации студента

1. Перечень примерных контрольных вопросов и заданий для самостоятельной работы

1. Time and space complexities of an algorithm. P and NP classes of complexity. Basic NP-complete and NP-hard problems in single machine scheduling theory, weak and strong NP-complete problems, pseudo-polynomail algorithm.

2. Denitions: graph, arc, edge, digraph, simple path, cycle, connectness, tree, forest, spanning tree, 1-tree, component, equivalence relation, simple graph, bipartite graph, matching, disjoint paths, disjoint cycles, hamiltonian path, hamiltonian cycle, Euler tour, Euler graph, complete matching, network, capacity of an arc, capacity of a vertex, cut, capacity of a cut, saturated arc, upper (lower) tolerance, bottleneck tolerances w. r.t. different relaxations, lower (upper) bounds, relaxation of a problem, reduced and truncated pseudo-Boolean polynomial and its input matrix..

3. Linear, Integer and Mixed Integer Linear Programming: primal and dual Linear Programming problems, unimodular and totally unimodular matrices, total dual integrality, branch-and-bound (BnB) algorithm

4. Algorithms: Prim’s and Kruskal’s algorithms for Minimum Spanning Tree Problem, Dijkstra’s algortihm for Shortest Path Problem, Ford-Fulkerson's augmenting path algorithm for Max Flow Problem with and without lower bounds, Hungarian algorithm for Assignment Problem (AP), tolerance based algorithm for AP, Branch-and-Bound (BnB) algorithm for the Asymmetric Traveling Salesman Problem (ATSP) based on the AP, BnB algorithms for the Symmetric TSP (STSP) based on the 1-tree, Tolerance Based BnB algorithms for AP, ATSP and STSP, computing tolerances for MSTP, SPP, MCP, 1-tree, AP, ATSP, STSP, pre-processing for SPLP and PMP.

5. Heuristics: folklore (double MST), greedy (nearest neighbor), tolerance based greedy (max-regret), nearest insertion, 2, 3-opt, Christofides’ for the STSP; max-regret for the AP and ATSP.

Basic notions in our scheduling problems

Processing time pij. The pij. represents the processing time of job j onmachine i. The subscript i is omitted if the processing time of job j does not depend on the machine or if job j is only to be processed on one given machine.

Release date rj. The release date rj of job j may also be referred to as the ready date. It is the time the job arrives at the system, i. e., the earliest time at which job j can start its processing.

Due date dj. The due date dj of job j represents the committed shipping or completion date (i. e., the date the job is promised to the customer). Completion of a job after its due date is allowed, but then a penalty is incurred. When a due date must be met it is referred to as a deadline and denoted by .

Weight wj. The weight wj of job j is basically a priority factor, denoting the importance of job j relative to the other jobs in the system. For example, this weight may represent the actual cost of keeping the job in the system. This cost could be a holding or inventory cost; it also could represent the amount of value already added to the job.

A scheduling problem is described by a triplet α | β | γ. The α field describes the machine environment and contains just one entry. The β field provides details of processing characteristics and constraints and may contain no entry at all, a single entry, or multiple entries. The γ field describes the objective to be minimized and often contains a single entry.

The possible machine environments specified in the α field are: Single machine (1) The case of a single machine is the simplest of all possible machine environments and is a special case of all other more complicated machine environments. In this seminar we are dealing with a single machine.

Release and due dates. If this symbol appears in the β field, then job j cannot start its processing before its release date rj. If rj does not appear in the β field, the processing of job j may start at any time. In contrast to release dates, due dates are not specified in this field. The type of objective function gives sufficient indication whether or not there are due dates.

Any other entry that may appear in the β field is self explanatory. For example, pj = p implies that all processing times are equal and dj = d implies that all due dates are equal. As stated before, due dates, in contrast to release dates, are usually not explicitly specified in this field; the type of objective function gives sufficient indication whether or not the jobs have due dates.

Preemptions (prmp). Preemptions imply that it is not necessary to keep a job on a machine, once started, until its completion. The scheduler is allowed to interrupt the processing of a job (preempt) at any point in time and put a different job on the machine instead. The amount of processing a preempted job already has received is not lost. When a preempted job is afterwards put back on the machine (or on another machine in the case of parallel machines), it only needs the machine for its remaining processing time. When preemptions are allowed prmp is included in the β field; when prmp is not included, preemptions are not allowed.

The objective function to be minimized is always a function of the completion times of the jobs, which, of course, depend on the schedule. The completion time of the operation of job j on machine i is denoted by Cij. The objective may also be a function of the due dates. In our seminar the completion time of job j is denoted by Cj.

The lateness of job j is defined as

Lj = Cj − dj,

which is positive when job j is completed late and negative when it is completed early.

The tardiness of job j is defined as

Tj = max(Cj − dj, 0) = max(Lj, 0).

The difference between the tardiness and the lateness lies in the fact that the tardiness never is negative.

The unit penalty of job j is defined as

Uj = 1 if Cj > dj and Uj = 0, otherwise.

The lateness, the tardiness and the unit penalty are the three basic due date related penalty functions considered in this seminar.

The total completion time ∑Cj. This objective sums the completion time of all jobs. Minimizing the total completion time can be used as a surrogate for minimizing the total Work-In-Process, since it tends to finish each job as quickly as possible.

The total weighted completion time ∑wjCj. The sum of the weighted completion times of the n jobs gives an indication of the total holding or inventory costs incurred by the schedule. The sum of the completion times is in the literature often referred to as the flow time. The total weighted completion time is then referred to as the weighted flow time.

The total weighted tardiness ∑wjTj .This is also a more general cost function than the total weighted completion time.

The weighted number of tardy jobs ∑wjUj. The weighted number of tardy jobs is not only a measure of academic interest, it is often an objective in practice as it is a measure that can be recorded very easily.

2. Примерная тематика рефератов и докладов студентов на семинаре

a. Algorithms (the Earliest Due Date (EDD) rule and the Weighted Shortest Processing Time (WSPT) rule,) for Jackson’s (1||Lmax ) and Smith’s (1||∑wjTj) problems.

b. The weighted remaining processing time for solving the Problem 1 and Smith’s problem.

c. Patterns in single machine scheduling putational study of Boolean Linear Programming Model for the Problem 1 and its generalization.

d. Pseudo-polynomial approximation algorithms for the Problem 1: theory and computational experiments.

e. Data correcting approach in combinatorial optimization.

f. Algorithm for minimization of clients in PMP based on Dilworth decomposition theorem for partial orders.

g. Equivalence classes of upper and lower tolerances defined by their equal values.

h. Boolean pseudo-Boolean Mixed Linear Programming Model for the Generalized PMP.

i. Computational study of reductions within Boolean pseudo-Boolean Mixed Linear Programming Models based on different heuristics.

j. Are Elloumi’s reductions in PMP embedded in the reductions based on pseudo-Boolean formulation of PMP.

k. Topics suggested by students (to be announced).

3. Примерный перечень вопросов для оценки качества освоения дисциплины (смотрите Перечень примерных контрольных вопросов и заданий для самостоятельной работы).

IV. Формы контроля

Формы текущего, промежуточного и итогового контроля

During the seminars I am going to formulate different research topics related either to scheduling or to min-sum location-allocation problems. Every student must prepare her (his) own research report on the chosen topic. Based on this research report a research talk must be done for at least 30 min.

Requirements for Reports

The assessments of the student’s reports are based on the quality of how the formulation of the problems is worked out, and the originality of the solution approach. The reports should include the following parts:

title page with name course, names of students, and date;

the report on each problem solution should contain:

a short problem description reflecting your understanding of the problem, plus the way the problem is solved;

the technical/mathematical solution;

the conclusion in terms of the way the problem is stated, possibly completed with suggestions for improving the problem formulation;

Literature.

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

G. Sierksma and D. works in Action. Text and Computer Exercises in Network Optimization. International Series in Operations Research & Management Science, Springer, 2010.

Примерный объем письменных работ

Each research report should contain at least 10 pages of written text in format A4.

Время выполнения работ (для аудиторных работ)

Итоговая оценка (методика выставления)

The evaluation of this scientific seminar includes two parts: 50% of this seminar is covered by a written research and 50% will be shared as follows: 25% for a research presentation on a seminar (research talk) and 25% by student’s answers to the questions as well as formulations of their own questions during this talk. The research report and research talk are obligatory and the research talk (presentation) should be graded at least 5.0. For example, your research report and your talk grades are 8.0, 6.0 and 7.3, respectively. Hence, your final grade is 8.00.25+6.00.25+7.30.5=2+1.5+3.65= 7.15, and will be rounded to the nearest integer 7.0.

NB: students questions during each presentation are very welcome and will be appreciated in the final grade of this seminar.

Автор программы