Single Machine Scheduling with Precedence Constrains, Release and Delivery Times

Research outputpeer-review

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.

Translated title of the contributionЗадача составления расписания для одного процессора с ограничениями предшествования, временами посупления и доставки заданий
Original languageEnglish
Title of host publicationInformation Systems Architecture and Technology
Subtitle of host publicationProceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology – ISAT 2019 - Part III
EditorsZofia Wilimowska, Leszek Borzemski, Jerzy Swiatek
Place of PublicationCham
PublisherSpringer Nature
Pages188 -198
Number of pages11
Volume1052
ISBN (Electronic)9783030304430
ISBN (Print)9783030304423
DOIs
Publication statusPublished - 1 Jan 2020

Publication series

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

Scopus subject areas

  • Mathematics(all)
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Single Machine Scheduling with Precedence Constrains, Release and Delivery Times'. Together they form a unique fingerprint.

  • Cite this

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