Single Machine Scheduling with Precedence Constrains, Release and Delivery Times

Переведенное название: Задача составления расписания для одного процессора с ограничениями предшествования, временами посупления и доставки заданий

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференции

Выдержка

The goal of this paper is to propose algorithms for scheduling problem, where set of jobs performed on a single processor. Each job has a release time, when it becomes available for processing, a processing time and a delivery time. We study the case in which there exist precedence constrains among jobs and preemption is not allowed. The objective is to minimize the time, by which all jobs are delivered. The single machine scheduling problem is one of the classic NP-hard optimization problems, and it is useful in solving flowshop and jobshop scheduling problems. We develop branch and bound algorithm for the problem. We propose an approximation algorithm to find an upper bound, solve the preemptive version of the problem to provide a lower bound and use a binary branching rule, where at each branch node, a complete schedule is generated. To illustrate the effectiveness of our algorithms we tested them on randomly generated set of jobs.

Язык оригиналаанглийский
Название основной публикацииInformation Systems Architecture and Technology
Подзаголовок основной публикацииProceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology – ISAT 2019 - Part III
РедакторыZofia Wilimowska, Leszek Borzemski, Jerzy Swiatek
Место публикацииCham
ИздательSpringer
Страницы188 -198
Число страниц11
Том1052
ISBN (электронное издание)9783030304430
ISBN (печатное издание)9783030304423
DOI
СостояниеОпубликовано - 1 янв 2020

Серия публикаций

НазваниеAdvances in Intelligent Systems and Computing
Том1052
ISSN (печатное издание)2194-5357
ISSN (электронное издание)2194-5365

Отпечаток

Single Machine Scheduling
Scheduling
Scheduling Problem
Branching Rules
Release Time
Job Shop Scheduling Problem
Preemption
Flow Shop Scheduling
Branch and Bound Algorithm
Approximation algorithms
NP-hard Problems
Processing
Approximation Algorithms
Schedule
Branch
Binary
Lower bound
Upper bound
Optimization Problem
Minimise

Предметные области Scopus

  • Математика (все)
  • Компьютерные науки (все)

Ключевые слова

  • Single processor · Branch and bound algorithm · Release and delivery time · Precedence constrains

Цитировать

Grigoreva, N. (2020). Single Machine Scheduling with Precedence Constrains, Release and Delivery Times. В Z. Wilimowska, L. Borzemski, & J. Swiatek (Ред.), Information Systems Architecture and Technology: Proceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology – ISAT 2019 - Part III (Том 1052, стр. 188 -198). (Advances in Intelligent Systems and Computing; Том 1052). Cham: Springer. https://doi.org/10.1007/978-3-030-30443-0_17, https://doi.org/10.1007/978-3-030-30443-0_17
Grigoreva, Natalia . / Single Machine Scheduling with Precedence Constrains, Release and Delivery Times. Information Systems Architecture and Technology: Proceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology – ISAT 2019 - Part III. редактор / Zofia Wilimowska ; Leszek Borzemski ; Jerzy Swiatek. Том 1052 Cham : Springer, 2020. стр. 188 -198 (Advances in Intelligent Systems and Computing).
@inproceedings{307c3766f63245b5b7e6426a969ca0e1,
title = "Single Machine Scheduling with Precedence Constrains, Release and Delivery Times",
abstract = "The goal of this paper is to propose algorithms for scheduling problem, where set of jobs performed on a single processor. Each job has a release time, when it becomes available for processing, a processing time and a delivery time. We study the case in which there exist precedence constrains among jobs and preemption is not allowed. The objective is to minimize the time, by which all jobs are delivered. The single machine scheduling problem is one of the classic NP-hard optimization problems, and it is useful in solving flowshop and jobshop scheduling problems. We develop branch and bound algorithm for the problem. We propose an approximation algorithm to find an upper bound, solve the preemptive version of the problem to provide a lower bound and use a binary branching rule, where at each branch node, a complete schedule is generated. To illustrate the effectiveness of our algorithms we tested them on randomly generated set of jobs.",
keywords = "Single processor · Branch and bound algorithm · Release and delivery time · Precedence constrains, Single processor, Branch and bound algorithm, Release and delivery time, Precedence constrains",
author = "Natalia Grigoreva",
note = "Grigoreva N. (2020) Single Machine Scheduling with Precedence Constrains, Release and Delivery Times. In: Wilimowska Z., Borzemski L., Świątek J. (eds) Information Systems Architecture and Technology: Proceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology – ISAT 2019. ISAT 2019. Advances in Intelligent Systems and Computing, vol 1052. Springer, Cham",
year = "2020",
month = "1",
day = "1",
doi = "10.1007/978-3-030-30443-0_17",
language = "English",
isbn = "9783030304423",
volume = "1052",
series = "Advances in Intelligent Systems and Computing",
publisher = "Springer",
pages = "188 --198",
editor = "Zofia Wilimowska and Leszek Borzemski and Jerzy Swiatek",
booktitle = "Information Systems Architecture and Technology",
address = "Germany",

}

Grigoreva, N 2020, Single Machine Scheduling with Precedence Constrains, Release and Delivery Times. в Z Wilimowska, L Borzemski & J Swiatek (ред.), Information Systems Architecture and Technology: Proceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology – ISAT 2019 - Part III. том. 1052, Advances in Intelligent Systems and Computing, том. 1052, Springer, Cham, стр. 188 -198. https://doi.org/10.1007/978-3-030-30443-0_17, https://doi.org/10.1007/978-3-030-30443-0_17

Single Machine Scheduling with Precedence Constrains, Release and Delivery Times. / Grigoreva, Natalia .

Information Systems Architecture and Technology: Proceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology – ISAT 2019 - Part III. ред. / Zofia Wilimowska; Leszek Borzemski; Jerzy Swiatek. Том 1052 Cham : Springer, 2020. стр. 188 -198 (Advances in Intelligent Systems and Computing; Том 1052).

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференции

TY - GEN

T1 - Single Machine Scheduling with Precedence Constrains, Release and Delivery Times

AU - Grigoreva, Natalia

N1 - Grigoreva N. (2020) Single Machine Scheduling with Precedence Constrains, Release and Delivery Times. In: Wilimowska Z., Borzemski L., Świątek J. (eds) Information Systems Architecture and Technology: Proceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology – ISAT 2019. ISAT 2019. Advances in Intelligent Systems and Computing, vol 1052. Springer, Cham

PY - 2020/1/1

Y1 - 2020/1/1

N2 - The goal of this paper is to propose algorithms for scheduling problem, where set of jobs performed on a single processor. Each job has a release time, when it becomes available for processing, a processing time and a delivery time. We study the case in which there exist precedence constrains among jobs and preemption is not allowed. The objective is to minimize the time, by which all jobs are delivered. The single machine scheduling problem is one of the classic NP-hard optimization problems, and it is useful in solving flowshop and jobshop scheduling problems. We develop branch and bound algorithm for the problem. We propose an approximation algorithm to find an upper bound, solve the preemptive version of the problem to provide a lower bound and use a binary branching rule, where at each branch node, a complete schedule is generated. To illustrate the effectiveness of our algorithms we tested them on randomly generated set of jobs.

AB - The goal of this paper is to propose algorithms for scheduling problem, where set of jobs performed on a single processor. Each job has a release time, when it becomes available for processing, a processing time and a delivery time. We study the case in which there exist precedence constrains among jobs and preemption is not allowed. The objective is to minimize the time, by which all jobs are delivered. The single machine scheduling problem is one of the classic NP-hard optimization problems, and it is useful in solving flowshop and jobshop scheduling problems. We develop branch and bound algorithm for the problem. We propose an approximation algorithm to find an upper bound, solve the preemptive version of the problem to provide a lower bound and use a binary branching rule, where at each branch node, a complete schedule is generated. To illustrate the effectiveness of our algorithms we tested them on randomly generated set of jobs.

KW - Single processor · Branch and bound algorithm · Release and delivery time · Precedence constrains

KW - Single processor

KW - Branch and bound algorithm

KW - Release and delivery time

KW - Precedence constrains

UR - http://www.scopus.com/inward/record.url?scp=85072840136&partnerID=8YFLogxK

UR - http://www.mendeley.com/research/single-machine-scheduling-precedence-constrains-release-delivery-times

U2 - 10.1007/978-3-030-30443-0_17

DO - 10.1007/978-3-030-30443-0_17

M3 - Conference contribution

SN - 9783030304423

VL - 1052

T3 - Advances in Intelligent Systems and Computing

SP - 188

EP - 198

BT - Information Systems Architecture and Technology

A2 - Wilimowska, Zofia

A2 - Borzemski, Leszek

A2 - Swiatek, Jerzy

PB - Springer

CY - Cham

ER -

Grigoreva N. Single Machine Scheduling with Precedence Constrains, Release and Delivery Times. В Wilimowska Z, Borzemski L, Swiatek J, редакторы, Information Systems Architecture and Technology: Proceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology – ISAT 2019 - Part III. Том 1052. Cham: Springer. 2020. стр. 188 -198. (Advances in Intelligent Systems and Computing). https://doi.org/10.1007/978-3-030-30443-0_17, https://doi.org/10.1007/978-3-030-30443-0_17