### ?

## Lower and Upper Bounds for the Preemptive Single Machine Scheduling Problem with Equal Processing Times

Ch. 2. P. 11-27.

The preemptive single machine scheduling problem of minimizing the total weighted completion time with equal processing times and arbitrary release dates is one of the four single machine scheduling problems with an open computational complexity status. In this paper we present lower and upper bounds for the exact solution of this problem based on the assignment problem. We also investigate properties of these bounds and worst-case behavior.

Burkov A. A., Shneer S., Turlikov A. M., , in : WAVE ELECTRONICS AND ITS APPLICATION IN INFORMATION AND TELECOMMUNICATION SYSTEMS. 2021. (WECONF 2021) St. Petersburg, Russia, 31 May - 4 June 2021. : IEEE, 2021. Ch. 9470700. P. 1-8.

The development of the Internet of Things technology in cellular networks is considered within the framework of massive machine-type communications with the use of random multiple access algorithms such as ALOHA and its modifications. Despite the fact that this class of algorithms has been studied for a long time, there are no numerical methods for ...

Added: October 28, 2022

Lazarev A. A., Arkhipov D. I., Werner F., Finding the Pareto Set for a Bi-criteria Scheduling Problem on a Single Machine with Equal Processing Times / 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

Itsykson D., Riazanov Artur, Sagunov Danil et al., Computational Complexity 2021 Vol. 30 Article 13

This paper is motivated by seeking the exact complexity of resolution refutation of Tseitin formulas. We prove that the size of any regular resolution refutation of a Tseitin formula T(G,c) based on a connected graph G=(V,E) is at least 2^Ω(tw(G)/log|V|), where tw(G) denotes the treewidth of a graph G. For constant-degree graphs, there is a ...

Added: June 3, 2022

Nesterenkov O., Chemodanov A., Turlikov A., , in : 2022 Wave Electronics and its Application in Information and Telecommunication Systems (WECONF) 30 May - 3 June 2022, St. Petersburg, Russia. : IEEE, 2022. Ch. 180440. P. 1-5.

The number of devices transmitting any data is increasing rapidly every day, so modern wireless networks (especially sensor networks, where the number of sensors connected to one base station can be enormous) must adapt to new realities, and developers must change data transmission algorithms. In this article, we consider the problem of constructing the lower ...

Added: October 28, 2022

Dmitry Arkhipov D. I., Battaia O. O., Cegarra J. et al., , in : 7th CIRP Conference on Assembly Technologies and Systems. * 76.: Elsevier, 2018. Ch. 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 29, 2018

Gafarov E., Dolgui A., Lazarev A. A., Computers & Industrial Engineering 2015 Vol. 85 P. 260-267

In this paper, the single-track railway scheduling problem with two stations and several segments of the track is considered. Two subsets of trains are given, where trains from the first subset go from the first station to the second station, and trains from the second subset go in the opposite direction. The speed of trains ...

Added: December 7, 2015

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

Zyablov V., Rybin P., Problems of Information Transmission 2009 Vol. 45 No. 3 P. 204-220

We generalize the method for computing the number of errors correctable by a low-density parity-check (LDPC) code in a binary symmetric channel, which was proposed by V.V. Zyablov and M.S. Pinsker in 1975. This method is for the first time applied for computing the fraction of guaranteed correctable erasures for an LDPC code with a ...

Added: December 11, 2017

Podolskaya O., В кн. : Материалы IX молодежной научной школы по дискретной математике и ее приложениям (Москва, 16-21 сентября 2013 г.). : М. : Издательство ИПМ РАН, 2013. С. 97-100.

We study Boolean circuit complexity in an infinite basis consisting of all Boolean functions that equal 1 only on sets of pair-wise incomparable tuples. It is known that lower bounds on the complexity of linear function, majority function and almost all boolean functions of $n$ variables are of the order $\sqrt n.$ We show that ...

Added: May 31, 2015

Mikhail Batsyn, Boris Goldengorin, Panos M. Pardalos et al., Optimization Methods and Software 2014 Vol. 29 No. 5 P. 955-963

The preemptive single machine scheduling problem of minimizing the total weighted completion time with arbitrary processing times and release dates is an important NP-hard problem in scheduling theory. In this paper we present an efficient high-quality heuristic for this problem based on the WSRPT (Weighted Shortest Remaining Processing Time) rule. The running time of the ...

Added: September 21, 2013

Zyablov V., Rybin P., Problems of Information Transmission 2012 Vol. 48 No. 4 P. 297-323

A new method for estimating the number of errors guaranteed to be corrected by a low-density parity-check code is proposed. The method is obtained by analyzing edges with special properties of an appropriate Tanner graph. In this paper we consider binary LDPC codes with constituent single-parity-check and Hamming codes and an iterative decoding algorithm. Numerical ...

Added: December 11, 2017

Chistopolskaya A., Podolskii V. V., Theory of Computing Systems 2022

In this paper we study decision tree models with various types of queries. For a given function it is usually not hard to determine the complexity in the standard decision tree model (each query evaluates a variable). However in more general settings showing tight lower bounds is substantially harder. Threshold functions often have non-trivial complexity ...

Added: September 13, 2022

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

Chistopolskaya A., Podolskii V. V., , in : Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings. Vol. 12159.: Springer, 2020. P. 198-210.

In this paper we study decision tree models with various types of queries. For a given function it is usually not hard to determine the complexity in the standard decision tree model (each query evaluates a variable). However in more general settings showing tight lower bounds is substantially harder. Threshold functions often have non-trivial complexity ...

Added: September 7, 2020

Gafarov E., Dolgui A., Lazarev A. A., Two-Station Single-Track Railway Scheduling Problem With Trains of Equal Speed / Elsevier. Series -- "Computers & Industrial Engineering". 2014.

In this paper, the single-track railway scheduling problem with two stations and several segments of the track is considered. Two subsets of trains are given, where trains from the first subset go from the first station to the second station, and trains from the second subset go in the opposite direction. The speed of trains ...

Added: April 10, 2015

Архипов Д.И. Д. И., Werner F. F., 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

Irina Utkina, Mikhail Batsyn, , in : Models, Algorithms and Technologies for Network Analysis, Springer Proceedings in Mathematics & Statistics. Vol. 156.: Switzerland : Springer, 2016. P. 115-124.

The cell formation problem (CFP) is an NP-hard optimization problem considered for cell manufacturing systems. Because of its high computational complexity several heuristics have been developed for solving this problem. In this paper we present a branch and bound algorithm which provides exact solutions of the CFP. This algorithm finds optimal solutions for 13 problems ...

Added: October 23, 2018

Rybin P., Zyablov V., Problems of Information Transmission 2015 Vol. 51 No. 3 P. 205-216

Two ensembles of low-density parity-check (LDPC) codes with low-complexity decoding algorithms are considered. The first ensemble consists of generalized LDPC codes, and the second consists of concatenated codes with an outer LDPC code. Error exponent lower bounds for these ensembles under the corresponding low-complexity decoding algorithms are compared. A modification of the decoding algorithm of ...

Added: December 11, 2017

Gafarov E., Dolgui A., Lazarev A. A., Computers & Industrial Engineering 2015 No. 85 P. 260-267

In this paper, the single-track railway scheduling problem with two stations and several segments of the track is considered. Two subsets of trains are given, where trains from the first subset go from the first station to the second station, and trains from the second subset go in the opposite direction. The speed of trains ...

Added: December 1, 2015

Kulikov A. S., Podolskii V. V., , in : 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). March 8–11, 2017, Hannover, Germany. Т. 66.: Лейпциг : Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2017. P. 1-14.

We study the following computational problem: for which values of k, the majority of n bits MAJn can be computed with a depth two formula whose each gate computes a majority function of at most k bits? The corresponding computational model is denoted by MAJk o MAJk. We observe that the minimum value of k ...

Added: June 1, 2017

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