DOI

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

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

НазваниеAdvances in Intelligent Systems and Computing
ИздательSPRINGER INTERNATIONAL PUBLISHING AG
Том1052
ISSN (печатное издание)2194-5357

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

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

    Области исследований

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

ID: 47653562