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

Mikhail Batsyn; Boris Goldengorin; Pavel Sukhov; Panos M. Pardalos

?

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

Ch. 2. P. 11–27.

Mikhail Batsyn, Boris Goldengorin, Pavel Sukhov, Panos M. Pardalos

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.

Язык: английский

Полный текст

Текст на другом сайте

Ключевые слова: Single machine scheduling Lower bound Upper bound Assignment problem Weighted completion time Equal processing times Release dates

В книге

Models, Algorithms, and Technologies for Network Analysis

Vol. 59. , NY: Springer, 2013.

A New Approach for Automatic Search for Families of Optimal Undirected Double-Loop Networks

Monakhova E., Monakhov O., Edward R. Rzaev и др., IEEE Access 2025 Vol. 13 P. 104716–104727

Добавлено: 30 июня 2025 г.

Approximation of the Objective Function of Single-Machine Scheduling Problem

Alexander Lazarev, Nikolay Pravdivets, Barashov E., Mathematics 2024 Vol. 12 No. 5 Article 699

The problem of the approximation of the coefficients of the objective function of a scheduling problem for a single machine is considered. It is necessary to minimize the total weighted completion times of jobs with unknown weight coefficients when a set of problem instances with known optimal schedules is given. It is shown that the ...

Добавлено: 16 мая 2024 г.

Delay Analysis of Massive Unsourced ALOHA-based Protocols with User Authentication

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.

Добавлено: 28 октября 2022 г.

Arbitrarily accurate approximation of numerical characteristics of stationary ALOHA Channels

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.

Добавлено: 28 октября 2022 г.

On the Decision Tree Complexity of Threshold Functions

Чистопольская А. И., Подольский В. В., Theory of Computing Systems 2022

Добавлено: 13 сентября 2022 г.

On the Decision Tree Complexity of Threshold Functions

Чистопольская А. И., Подольский В. В., , in: Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, ProceedingsVol. 12159.: Springer, 2020. P. 198–210.

Добавлено: 7 сентября 2020 г.

Operator assignment problem in aircraft assembly lines: a new planning approach taking into account economic and ergonomic constraints

Dmitry Arkhipov D. I., Battaia O. O., Cegarra J. и др., , in: 7th CIRP Conference on Assembly Technologies and Systems* 76.: Elsevier, 2018. Ch. 76 P. 63–66.

Добавлено: 29 октября 2018 г.

51st CIRP Conference on Manufacturing Systems

Elsevier, 2018.

Добавлено: 29 октября 2018 г.

A Branch and Bound Algorithm for the Cell Formation Problem

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

Добавлено: 23 октября 2018 г.

Operator assignment problem in aircraft assembly lines: a new planning approach taking into account economic and ergonomic constraints

Alexander Lazarev, Cegarra J., Battaia O. O. и др., Procedia CIRP 2018 Vol. 76 P. 63–66

Добавлено: 1 октября 2018 г.

Erasure correction by low-density codes

Zyablov V., Рыбин П. С., Problems of Information Transmission 2009 Vol. 45 No. 3 P. 204–220

Добавлено: 11 декабря 2017 г.

Analysis of the relation between properties of LDPC codes and the tanner graph

Zyablov V., Рыбин П. С., Problems of Information Transmission 2012 Vol. 48 No. 4 P. 297–323

Добавлено: 11 декабря 2017 г.

Asymptotic bounds on the decoding error probability for two ensembles of LDPC codes

Рыбин П. С., Zyablov V., Problems of Information Transmission 2015 Vol. 51 No. 3 P. 205–216

Добавлено: 11 декабря 2017 г.

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

Архипов Д.И. Д. И., Werner F. F., Optimization Letters, Springer Berlin Heidelberg, Berlin 2017 Vol. V.11 No. 1 P. 165–177

Добавлено: 20 октября 2017 г.

Computing majority by constant depth majority circuits with low fan-in gates

Kulikov A. S., Подольский В. В., , 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 ...

Добавлено: 1 июня 2017 г.

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

Лазарев А. А., 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 ...

Добавлено: 13 апреля 2016 г.

Two-station single-track railway scheduling problem with trains of equal speed

Gafarov E., Dolgui 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 ...

Добавлено: 7 декабря 2015 г.