Online Scheduling with Unit Processing Times and Processing Set Restrictions

This paper investigates online scheduling problems with processing set restrictions. There is a sequence of jobs that are revealed one by one over list, where each job has unit processing time. A job can only be processed by a subset of the machines, namely the processing set of the job. The objecti...

Full description

Saved in:
Bibliographic Details
Published in:Journal of the Operations Research Society of China (Internet) 2019-09, Vol.7 (3), p.475-484
Main Authors: Chen, Yong, Chen, Guang-Ting, Liu, Long-Cheng, Jiang, Yi-Wei, Tan, Zhi-Yi, Zhang, An
Format: Article
Language:English
Subjects:
Algorithms
Competition
Computer aided scheduling
Employment
Schedules
Scheduling
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper investigates online scheduling problems with processing set restrictions. There is a sequence of jobs that are revealed one by one over list, where each job has unit processing time. A job can only be processed by a subset of the machines, namely the processing set of the job. The objective is to minimize the makespan. For m machines with two different processing sets, we propose an optimal algorithm with a competitive ratio of 32. For three machines with inclusive processing sets, an optimal algorithm with competitive ratio 53 is provided.
ISSN:2194-668X
2194-6698
DOI:10.1007/s40305-019-00256-x