A Linear Time Exact Algorithm for Scheduling Unit-processing-time-jobs with Sizes 1 or k

DOI

10.2991/msmee-17.2017.320How to use a DOI?

Keywords

Scheduling, Batch machines, Job sizes, Makespan, Linear time exact algorithm

Abstract

The problem of scheduling jobs with sizes on batch machines is considered. Each machine can process several jobs as a batch simultaneously as long as the total size of these jobs does not exceed the capacity of the machine. The processing time of a batch is defined to be the longest processing time of the jobs in the batch. The goal is to minimize makespan, i.e., the maximum job completion time. It has been known to be strongly NP-hard. A linear time exact algorithm is presented for a special case where all the jobs have processing times 1 and sizes 1 or k (k is not fixed).

Copyright

© 2017, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Xiao Xin
AU  - Guohua Mu
AU  - Min Mou
PY  - 2017/05
DA  - 2017/05
TI  - A Linear Time Exact Algorithm for Scheduling Unit-processing-time-jobs with Sizes 1 or k
BT  - Proceedings of the 2017 2nd International Conference on Materials Science, Machinery and Energy Engineering (MSMEE 2017)
PB  - Atlantis Press
SP  - 1760
EP  - 1763
SN  - 2352-5401
UR  - https://doi.org/10.2991/msmee-17.2017.320
DO  - 10.2991/msmee-17.2017.320
ID  - Xin2017/05
ER  -