Uniform Parallel Machine Scheduling Problem with Controllable Delivery Times

Li Kai (), Li Hui (), Cheng Bayi () and Luo Qing ()
Additional contact information
Li Kai: School of Management, Hefei University of Technology, Hefei230009, China
Li Hui: School of Management, Hefei University of Technology, Hefei230009, China
Cheng Bayi: School of Management, Hefei University of Technology, Hefei230009, China
Luo Qing: Nanling Branch, China Mobile Group Anhui Co., Ltd., Nanling242400, China

Journal of Systems Science and Information, 2015, vol. 3, issue 6, 525-537

Abstract: This paper considers the uniform parallel machine scheduling problem with controllable delivery times, which assumes that the delivery times of jobs are linear decreasing functions of the consumed resource. It aims to minimize the maximum completion time under the constraint that the total resource consumption does not exceed a given limit. For this NP-hard problem, we propose a resource allocation algorithm, named RAA, according to the feasible solution of the uniform parallel machine scheduling problem with fixed delivery times. It proves that RAA algorithm can obtain the optimal resource allocation scheme for any given scheduling scheme in O(n log n)time. Some algorithms based on heuristic algorithm LDT, heuristic algorithm LPDT and simulated annealing are proposed to solve the uniform parallel machine scheduling problem with controllable delivery times. The accuracy and efficiency of the proposed algorithms are tested based on those data with problem sizes varying from 40 to 200 jobs and 2 to 8 machines. The computational results indicate that the SA approach is promising and capable of solving large-scale problems in a reasonable time.

Keywords: scheduling; uniform parallel machine; resource allocation; delivery times (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1515/JSSI-2015-0525 (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:6:p:525-537:n:4

DOI: 10.1515/JSSI-2015-0525

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 ().