### ?

## Finding the Pareto Set for a Bi-criteria Scheduling Problem on a Single Machine with Equal Processing Times

Otto-von-Guericke University Magdeburg, Germany.
--.
Institut fur Mathematische Optimierung
,
2015.
No. 11.

The following special case of the classical NP-hard scheduling problem 1jrj jLmax is considered. There is a set of jobs N = f1; 2; : : : ; ng with identical processing times pj = p for all jobs j 2 N. All jobs have to be processed on a single machine. The optimization criterion is the minimization of maximum lateness Lmax. We analyze algorithms for the makespan problem 1jrj jCmax, presented by Garey et al. (1981) and Simons (1978) and give two polynomial algorithms to solve the problem under consideration and to construct the Pareto set with respect to the criteria Lmax and Cmax. The complexity of the presented algorithms is O(Q _ n log n) and O(n2 log n), respectively, where 10Q is the accuracy of the input-output parameters.

Publication based on the results of:

Optimization Letters 2016 P. 1-13

The following special case of the classical NP-hard scheduling problem (Formula presented.) is considered. There is a set of jobs (Formula presented.) with identical processing times (Formula presented.) for all jobs (Formula presented.). All jobs have to be processed on a single machine. The optimization criterion is the minimization of maximum lateness (Formula presented.). We ...

Added: April 13, 2016

Optimization Letters, Springer Berlin Heidelberg, Berlin 2017 Vol. V.11 No. 1 P. 165-177

The following special case of the classical NP-hard scheduling problem 1|r_j |Lmax is considered. There is a set of jobs N = {1, 2, . . . , n} with identical processing times p_j = p for all jobs j ∈ N. All jobs have to be processed on a single machine. The optimization criterion ...

Added: October 20, 2017

IMA Journal Management Mathematics 2016 Vol. 28 No. 4 P. 553-578

This article deals with the logistics of a Ukrainian food and consumer goods distributor. Our main goal is to reduce the field costs of the company, which comprise the agent labour costs and company's transportation charges. The mathematical model used is an integer programming optimization one. The problem is heuristically decomposed into subproblems; methods to ...

Added: October 5, 2018

IFAC-PapersOnLine 2019 Vol. 52-13 P. 951-956

This paper is devoted to the problem of scheduling maintenance of locomotives in a depot. The problem based on the operation Eastern polygon of Russian Railways. A heuristic algorithm and a constraint programming model are presented. Numerical experiments on real data for real depot configurations were carried out to compare the performance of the heuristic ...

Added: April 27, 2020

Elsevier, 2018

The assembly process is extremely complex for aircraft and its management requires to address numerous optimization problems related to the assignment of tasks to workstations, staffing problem for each workstation and finally the assignment of tasks to operators at each workstation. This paper treats the latter problem dealing with the assignment of tasks to operators ...

Added: October 29, 2018

Communications in Computer and Information Science 2020 No. 1145 P. 311-325

In this article, we consider the problem of planning maintenance operations at a locomotive maintenance depot. There are three types of tracks at the depot: buffer tracks, access tracks and service tracks. A depot consists of up to one buffer track and a number of access tracks, each of them ending with one service track. ...

Added: April 26, 2020

Optimization Letters 2015 Vol. 9 No. 1 P. 91-104

This paper investigates the scheduling problems of a single serial-batching machine with independent setup time and deteriorating job processing times. With the assumption of deteriorating jobs, the job processing times are described by an increasing function of their starting times. All the jobs are first partitioned into serial batches and then processed on a single ...

Added: January 14, 2015

Mathematical and Computer Modelling 2009 Vol. 49 No. 9-10 P. 2061-2072

The scheduling problem of minimizing total tardiness on a single machine is known to be NP-hard in the ordinary sense. In this paper, we consider the special case of the problem when the processing times p_j and the due dates d_j of the jobs are oppositely ordered: p_1 >= p_2>=...>=p_n and d_1. ...

Added: November 24, 2012

A general approximation approach for multi-machine scheduling problems with minimizing the maximum penalty / Otto-von-Guericke Universitaet. 2019.

We consider NP-hard multi{machine scheduling problems with the criterion of minimizing the maximum penalty, e.g. maximum lateness. For such problems, we introduce a metric which delivers an upper bound on the absolute error of the objective function value. Taking the given in- stance of some problem and using the introduced metric, we determine the nearest ...

Added: April 26, 2020

Elsevier, 2018

In order to implement the human-centric manufacturing and sustainability concepts in industry, an important effort should be done in order to model working conditions for human operators and improve them. Several studies have been conducted for mass production assembly lines where short cycle times make the work content highly repetitive. However, the case of low-volume ...

Added: October 29, 2018

IFAC-PapersOnLine 2016 Vol. 49 No. 12 P. 226-230

In this paper, a generalized formulation of a classical single machine scheduling problem is considered. A set of n jobs characterized by their release dates, deadlines and a start time-dependent processing time function p(t) has to be processed on a single machine. The objective is to find a Pareto-optimal set of schedules with respect to ...

Added: October 27, 2016

ЛЕНАНД, 2021

Книга представляет собой экспресс-курс по теории вероятностей в контексте начального курса эконометрики. В курсе в максимально доступной форме изложен тот минимум, который необходим для осознанного изучения начального курса эконометрики. Данная книга может не только помочь ликвидировать пробелы в знаниях по теории вероятностей, но и позволить в первом приближении выучить предмет «с нуля». При этом, благодаря доступности изложения и небольшому объему книги, ...

Added: February 20, 2021

Математические заметки 2017 Т. 102 № 1 С. 72-80

Мы доказываем, что аффинно-треугольные подгруппы являются борелевскими подгруппами групп Кремоны. ...

Added: May 3, 2017

Selecta Mathematica, New Series 2018 Vol. 24 No. 1 P. 21-62

We study plane partitions satisfying condition a_{n+1,m+1}=0 (this condition is called “pit”) and asymptotic conditions along three coordinate axes. We find the formulas for generating function of such plane partitions. Such plane partitions label the basis vectors in certain representations of quantum toroidal gl1 algebra, therefore our formulas can be interpreted as the characters of ...

Added: October 24, 2018

Красноярск: ИВМ СО РАН, 2013

Труды Пятой Международной конференции «Системный анализ и информационные технологии» САИТ-2013 (19–25 сентября 2013 г., г.Красноярск, Россия): ...

Added: November 18, 2013

Russian Mathematical Surveys 2017 Vol. 71 No. 6 P. 1146-1148

In the paper a Palis problem on finding sufficient conditions on embedding of Morse-Smale diffeomorphisms in topological flow is discussed. ...

Added: May 17, 2017

Moscow Mathematical Journal 2017 Vol. 17 No. 4 P. 565-600

We associate an explicit equivalent descendent insertion to any relative insertion in quantum K-theory of Nakajima varieties.
This also serves as an explicit formula for off-shell Bethe eigenfunctions for general quantum loop algebras associated to quivers and gives the general integral solution to the corresponding quantum Knizhnik Zamolodchikov and dynamical q-difference equations. ...

Added: October 25, 2018

Moscow University Computational Mathematics and Cybernetics 2013 Vol. 37 No. 4 P. 180-188

The article investigates a model of delays in a network of functional elements (a gate network) in an arbitrary finite complete basis B, where basis elements delays are arbitrary positive real numbers that are specified for each input and each set of boolean variables supplied on the other inputs. Asymptotic bounds of the form τ ...

Added: December 2, 2019

Scientific Reports 2018 Vol. 8 No. 1 P. 16915-1-16915-18

Sequential state discrimination is a strategy for quantum state discrimination of a sender’s quantum
states when N receivers are separately located. In this report, we propose optical designs that can
perform sequential state discrimination of two coherent states. For this purpose, we consider not
only binary phase-shifting-key (BPSK) signals but also general coherent states, with arbitrary prior
probabilities. Since ...

Added: November 16, 2020

Дискретная математика 1991 Т. 3 № 3 С. 35-45

Added: October 17, 2014

Математический сборник 2015 Т. 206 № 9 С. 3-20

We formulate some term rewriting systems in which the number of computation steps is finite for each output, but this number cannot be bounded by a provably total computable function in Peano arithmetic PA. Thus, the termination of such systems is unprovable in PA. These systems are derived from an independent combinatorial result known as the Worm ...

Added: March 13, 2016

Вопросы защиты информации 2018 № 2 С. 66-71

Рассматривается статистическая модель одного этапа системы фрод-мониторинга транзакций в интернет-банкинге. Построен и рассчитан близкий к отношению правдоподобия критерий отсева мошеннических транзакций. Для выборочных распределений, полученных на выборке объема в 1 млн реальных транзакций, вычислены параметры эффективности этого критерия. ...

Added: June 14, 2018

Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Социальные науки 2019 Т. 55 № 3 С. 183-189

The article describes a method that allows to improve the content of disciplines of the mathematical cycle by dividing them into invariant (general) and variable parts. The invariants were identified for such disciplines as «Linear algebra», «Mathematical analysis», «Probability theory and mathematical statistics» delivered to Bachelors program students of economics at several universities. Based on ...

Added: January 28, 2020

Journal of Lie Theory 2000 Vol. 10 No. 2 P. 345-357

Added: July 8, 2014