### ?

## Scheduling jobs with equal processing times on a single machine: minimizing maximum lateness and makespan

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

Архипов Д.И. Д. И., Werner F. F.

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 is the minimization of maximum lateness Lmax. We analyze algorithms for the makespan problem 1|r_j |Cmax, presented by Garey et al. (SIAM J Comput 10(2):256–269, 1981), Simons (A fast algorithm for single processor scheduling. In: 19th Annual symposium on foundations of computer science (Ann Arbor, Mich., 1978, 1978) and Benson’s algorithm (J Glob Optim 13(1):1–24, 1998) 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(n^3 log n), respectively, where 10^−Q is the accuracy of the input-output parameters.

Lazarev A. A., Arkhipov D. I., Werner F., / Institut fur Mathematische Optimierung. Series -- "Otto-von-Guericke University Magdeburg, Germany". 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 ...

Added: April 10, 2015

Lazarev A. A., Arkhipov D. I., Werner F., 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

Alexander Lazarev, Cegarra J., Battaia O. O. et al., Procedia CIRP 2018 Vol. 76 P. 63-66

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 1, 2018

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

Pei J., Liu X., Pardalos P. M. et al., 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

Lazarev A. A., Werner F., 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

Kuznietsov K., Gromov V., Skorohod V., 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

Lazarev A. A., Dmitry Arkhipov D. I., Battaia O. O., , in : Proceedings of the 16th International Conference on Project Management and Scheduling (Rome, 2018). : TexMat, 2018. P. 22-25.

The Resource-Constrained Project Scheduling Problem (RCPSP) is considered. This problem is NP-hard in strong sense (Garey and Johnson 1975). In this paper, a new polynomial-time approach is developed to find an upper bound on resource consumption. This bound can be also used to calaculate a lower bound for makespan. The procedure also helps to increase ...

Added: October 1, 2018

Lazarev A. A., Arkhipov D. I., Werner F., 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

Lazarev A. A., Lemtuzhnikova D., Werner F., / 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

Lazarev A. A., Grishin E. M., Galakhov S. A. et al., 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

Lazarev A. A., Pravdivets N., Nekrasov I., Algorithms 2018 Vol. 11 No. 4 P. 1-13

We consider one approach to formalize the Resource-Constrained Project Scheduling Problem (RCPSP) in terms of combinatorial optimization theory. The transformation of the original problem into combinatorial setting is based on interpreting each operation as an atomic entity that has a defined duration and has to be resided on the continuous time axis meeting additional restrictions. ...

Added: October 1, 2018

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

Gafarov E., Lazarev A. A., Werner F., Automation and Remote Control 2020 Vol. 81 No. 5 P. 853-868

In this paper, we consider the problem of minimizing total weighted tardiness for equal-length jobs with arbitrary release dates on a single machine. This problem is mentioned as a minimal open problem, see http://www2.informatik.uni osnabrueck.de/knust/class/dateien/classes/ein_ma/ein_ma, i.e., its complexity status is still open. The latest results on this problem were presented in the years 2000 and ...

Added: September 1, 2020

TexMat, 2018

This volume contains the papers that will be presented at PMS 2018, the 16th International Conference on Project Management and Scheduling to be held on April, 17-20 2018 in Rome - Italy. The EURO Working Group on Project Management and Scheduling was established by Professors Lu´ıs Valadares Tavares and Jan Weglarz during the EURO VIII ...

Added: October 1, 2018

191574970, Functional Analysis and Its Applications 2006 Vol. 40 No. 2 P. 81-90

It is well known that every module M over the algebra ℒ(X) of operators on a finite-dimensional space X can be represented as the tensor product of X by some vector space E, M ≅ = E ⊗ X. We generalize this assertion to the case of topological modules by proving that if X is a stereotype space with the stereotype approximation property, then for each stereotype module M over the ...

Added: September 23, 2016

Losev A. S., Slizovskiy S., JETP Letters 2010 Vol. 91 P. 620-624

Added: February 27, 2013

Ilyashenko Y., Яковенко С. Ю., М. : МЦНМО, 2013

Предлагаемая книга—первый том двухтомной монографии, посвящённой аналитической теории дифференциальных уравнений.
В первой части этого тома излагается формальная и аналитическая теория нормальных форм и теорема о разрешении особенностей для векторных полей на плоскости.
Вторая часть посвящена алгебраически разрешимым локальным задачам теории аналитических дифференциальных уравнений , квадратичным векторным полям и проблеме локальной классификации ростков векторных полей в комплексной области ...

Added: February 5, 2014

Kalyagin V.A., Koldanov A.P., Koldanov P.A. et al., Physica A: Statistical Mechanics and its Applications 2014 Vol. 413 No. 1 P. 59-70

A general approach to measure statistical uncertainty of different filtration techniques for market network analysis is proposed. Two measures of statistical uncertainty are introduced and discussed. One is based on conditional risk for multiple decision statistical procedures and another one is based on average fraction of errors. It is shown that for some important cases ...

Added: July 19, 2014

Maslov V., Теоретическая и математическая физика 2019 Т. 201 № 1 С. 65-83

We study the process of a nucleon separating from an atomic nucleus from the mathematical standpoint
using experimental values of the binding energy for the nucleus of the given substance. A nucleon becomes
a boson at the instant of separating from a fermionic nucleus. We study the further transformations of
boson and fermion states of separation in a ...

Added: November 1, 2019

Pahomov F., Известия РАН. Серия математическая 2016 Т. 80 № 6 С. 173-216

Полимодальная логика доказуемости
GLP была введена Г. К. Джапаридзе в 1986 г. Она является логикой доказуемости для ряда цепочек предикатов доказуемости возрастающей силы. Всякой полимодальной логике соответствует многообразие полимодальных алгебр. Л. Д. Беклемишевым и А. Виссером был поставлен вопрос о разрешимости элементарной теории свободной GLP-алгебры, порожденной константами 0, 1 [1]. В этой статье для любого натурального n решается аналогичный вопрос для логик GLPn, являющихся ...

Added: December 4, 2017

Sinelshchikov D., Кудряшов Н. А., Theoretical and Mathematical Physics 2018 Vol. 196 No. 2 P. 1230-1240

We study a family of nonautonomous generalized Liénard-type equations. We consider the equivalence problem via the generalized Sundman transformations between this family of equations and type-I Painlevé–Gambier equations. As a result, we find four criteria of equivalence, which give four integrable families of Liénard-type equations. We demonstrate that these criteria can be used to construct ...

Added: February 9, 2019

Min Namkung, Younghun K., 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

Kotelnikova M. V., Aistov A., Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Социальные науки 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