Preemptive Scheduling with Controllable Processing Times on Parallel Machines

Liu Guiqing (), Li Kai () and Cheng Bayi ()
Additional contact information
Liu Guiqing: School of Mathematics, Hefei University of Technology, Hefei230009, China
Li Kai: School of Mathematics, Hefei University of Technology, Hefei230009, China
Cheng Bayi: School of Mathematics, Hefei University of Technology, Hefei230009, China

Journal of Systems Science and Information, 2015, vol. 3, issue 1, 68-76

Abstract: This paper considers several parallel machine scheduling problems with controllable processing times, in which the goal is to minimize the makespan. Preemption is allowed. The processing times of the jobs can be compressed by some extra resources. Three resource use models are considered. If the jobs are released at the same time, the problems under all the three models can be solved in a polynomial time. The authors give the polynomial algorithm. When the jobs are not released at the same time, if all the resources are given at time zero, or the remaining resources in the front stages can be used to the next stages, the offline problems can be solved in a polynomial time, but the online problems have no optimal algorithm. If the jobs have different release dates, and the remaining resources in the front stages can not be used in the next stages, both the offline and online problems can be solved in a polynomial time.

Keywords: parallel machine; controllable processing time; offline; online; preemptive (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1515/JSSI-2015-0068 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bpj:jossai:v:3:y:2015:i:1:p:68-76:n:7

DOI: 10.1515/JSSI-2015-0068

Access Statistics for this article

Journal of Systems Science and Information is currently edited by Shouyang Wang

More articles in Journal of Systems Science and Information from De Gruyter
Bibliographic data for series maintained by Peter Golla ().