Single Machine Scheduling with Precedence Constrains, release and Delivety Times

Research output

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.
Original languageEnglish
Title of host publicationInformation Systems Architecture and Technology: Proceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology – ISAT 2019. Part III
EditorsZofia Wilimowska, Leszek Borzemski, Jerzy Świątek
Place of PublicationCham
PublisherSpringer
Pages188 -198
ISBN (Electronic)9783030304430
ISBN (Print)9783030304423
DOIs
Publication statusPublished - 16 Oct 2019

Publication series

NameAdvances in Intelligent Systems and Computing
PublisherSpringer
Volume1052
ISSN (Print)2194-5357

Fingerprint

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 subject areas

  • Mathematics(all)
  • Computer Science(all)

Cite this

Grigoreva, N. (2019). Single Machine Scheduling with Precedence Constrains, release and Delivety Times. In Z. Wilimowska, L. Borzemski, & J. Świątek (Eds.), Information Systems Architecture and Technology: Proceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology – ISAT 2019. Part III (pp. 188 -198). (Advances in Intelligent Systems and Computing; Vol. 1052). Cham: Springer. https://doi.org/10.1007/978-3-030-30443-0_17
Grigoreva, Natalia . / Single Machine Scheduling with Precedence Constrains, release and Delivety Times. Information Systems Architecture and Technology: Proceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology – ISAT 2019. Part III. editor / Zofia Wilimowska ; Leszek Borzemski ; Jerzy Świątek. Cham : Springer, 2019. pp. 188 -198 (Advances in Intelligent Systems and Computing).
@inproceedings{307c3766f63245b5b7e6426a969ca0e1,
title = "Single Machine Scheduling with Precedence Constrains, release and Delivety 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.",
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 = "2019",
month = "10",
day = "16",
doi = "10.1007/978-3-030-30443-0_17",
language = "English",
isbn = "9783030304423",
series = "Advances in Intelligent Systems and Computing",
publisher = "Springer",
pages = "188 --198",
editor = "Wilimowska, {Zofia } and Borzemski, {Leszek } and Świątek, {Jerzy }",
booktitle = "Information Systems Architecture and Technology: Proceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology – ISAT 2019. Part III",
address = "Germany",

}

Grigoreva, N 2019, Single Machine Scheduling with Precedence Constrains, release and Delivety Times. in Z Wilimowska, L Borzemski & J Świątek (eds), Information Systems Architecture and Technology: Proceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology – ISAT 2019. Part III. Advances in Intelligent Systems and Computing, vol. 1052, Springer, Cham, pp. 188 -198. https://doi.org/10.1007/978-3-030-30443-0_17

Single Machine Scheduling with Precedence Constrains, release and Delivety Times. / Grigoreva, Natalia .

Information Systems Architecture and Technology: Proceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology – ISAT 2019. Part III. ed. / Zofia Wilimowska; Leszek Borzemski; Jerzy Świątek. Cham : Springer, 2019. p. 188 -198 (Advances in Intelligent Systems and Computing; Vol. 1052).

Research output

TY - GEN

T1 - Single Machine Scheduling with Precedence Constrains, release and Delivety 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 - 2019/10/16

Y1 - 2019/10/16

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.

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.

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

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

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

M3 - Conference contribution

SN - 9783030304423

T3 - Advances in Intelligent Systems and Computing

SP - 188

EP - 198

BT - Information Systems Architecture and Technology: Proceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology – ISAT 2019. Part III

A2 - Wilimowska, Zofia

A2 - Borzemski, Leszek

A2 - Świątek, Jerzy

PB - Springer

CY - Cham

ER -

Grigoreva N. Single Machine Scheduling with Precedence Constrains, release and Delivety Times. In Wilimowska Z, Borzemski L, Świątek J, editors, Information Systems Architecture and Technology: Proceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology – ISAT 2019. Part III. Cham: Springer. 2019. p. 188 -198. (Advances in Intelligent Systems and Computing). https://doi.org/10.1007/978-3-030-30443-0_17