@inproceedings{Phirsof2000,
  author    = {Phirsof, Alexander},
  title     = {Research of special models describing technological processes},
  doi       = {10.25643/bauhaus-universitaet.607},
  url       = {http://nbn-resolving.de/urn:nbn:de:gbv:wim2-20111215-6072},
  year      = {2000},
  abstract  = {The technological processes, schedules, parallel algorithms, etc., having some technological limitations and exacting increases of efficiency of their execution can be described through digraphs, on which the appropriate optimization problem (construction of optimal scheduling of tops of digraph) can be solved. The problems, researched in the given operation, have a generally following statement: The problem 1: Under the given graph G and option value h to construct parallel scheduling of tops of digraph of minimum length. Let's designate the problem S(G, h, l). The problem 2: Under the given graph G and option value l to construct parallel scheduling of tops of digraph of minimum width. Let's designate the problem S(G, l, h). The problem 3: Under the given graph G, option value h and periods of execution of operations di, i=1, …, n to construct parallel scheduling of tops of digraph of minimum length. Let's designate the problem S(G, h, di, l). The problems 1,2,3 in a case when h-arbitrary have exponential complexity. In operation the method of solution of the problem S(T, h, di, l) is offered on the basis of choice of tops having greatest weight. The approach to solution of the problem S(G, 3, l) is offered, where G the graph satisfying property : S[i] =S [i], i=1, …, l. For obtaining a rating of width of scheduling on an available estimator of length, we offer to use iterative algorithm of polynomial complexity, on which each step the current value of width of scheduling is set, which is used for specification of length of scheduling.},
  subject      = {Ablaufplanung},
  language  = {en}
}
@inproceedings{Sotskov2003,
  author    = {Sotskov, Yuri N.},
  title     = {Stability of an optimal schedule for a flow-shop problem with two jobs},
  doi       = {10.25643/bauhaus-universitaet.369},
  url       = {http://nbn-resolving.de/urn:nbn:de:gbv:wim2-20111215-3690},
  year      = {2003},
  abstract  = {The problem F|n=2|F is to minimize the given objective function F(C1,m, C2,m) of completion times Ci,m of two jobs i {\^I} J={1, 2} processed on m machines M={1, 2, …, m}. Both jobs have the same technological route through m machines. Processing time ti,k of job i{\^I} J on machine k{\^I} M is known. Operation preemptions are not allowed. Let R2m be space of non-negative 2m-dimensional real vectors t=(t1,1,…, t1,m, t2,1,…, t2,m) with Chebyshev's distance d(t, t*). To solve problem F|n=2|F, we can use the geometric algorithm, which includes the following steps: 1) construct digraph (V, A) for problem F|n=2|F and find so-called border vertices in (V, A); 2) construct the set of trajectories corresponding to the shortest paths Rt in digraph (V, A) from the origin vertex to each of the border vertices; 3) find an optimal path in the set Rt that represents a schedule with minimal value of the objective function F. Let path tu {\^I} Rt be optimal for the problem F|n=2|F with operation processing times defined by vector t. If for any small positive real number e > 0 there exists vector t*{\^I} R2m such that d(t, t*) = e and path tu is not optimal for the problem F|n=2|F with operation processing times defined by vector t*, then optimality of path tu is not stable. The main result of the paper is the proof of necessary and sufficient conditions for optimality stability of path tu. If objective function F is continuous non-decreasing (e.g., makespan, total completion time, maximal lateness or total tardiness), then to test whether optimality of the path tu {\^I} Rt is stable takes O(m log m) time.},
  subject      = {Ablaufplanung},
  language  = {en}
}