PARALLEL MACHINE SCHEDULING WITH A SIMULTANEITY CONSTRAINT AND UNIT-LENGTH JOBS TO MINIMIZE THE MAKESPAN

Lin Lin (), Yixun Lin, Xianwei Zhou and Ruyan Fu
Additional contact information
Lin Lin: State Key Laboratory of Wireless Mobile Communications, China Academy of Telecommunications Technology (CATT), Beijing, 100191, P. R. China
Yixun Lin: Department of Mathematics, Zhengzhou University, Zhengzhou, Henan, 450052, P. R. China
Xianwei Zhou: Department of Communication Engineering, School of Information Engineering, University of Science and Technology Beijing, Beijing, 100083, P. R. China
Ruyan Fu: School of Sciences, China University of Mining and Technology, Xuzhou, Jiangsu 221116, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2010, vol. 27, issue 06, 669-676

Abstract: In this paper, we consider the parallel machine scheduling with a simultaneity constraint and unit-length jobs. The problem can be described as follows. There are givenmparallel machines and a graphG, whose vertices represent jobs. Simultaneity constraint means that we can process a vertex jobvif and only if there exists at leastdG(v)idle machines, wheredG(v)is the degree of vertexvin graphG. Once a vertex job is completed, we delete the vertex and its incident edges from the graph. The number of machines that a vertex job needing depends on its degree in current graph. Changes of graph result in changes of vertex degree. Here, we consider a special case that all jobs in the original graph are unit-length. Letpvdenote the processing time of vertex jobv, we definepv= 0ifd(v) = 0, andpv= 1, otherwise. The objective is to minimize the time by which each vertex job is completed, i.e., the time by which the graph becomes an empty graph. We show that this problem is strongly NP-hard and provide a$(2-\frac{1}{m})$-approximation algorithm.

Keywords: Parallel machine scheduling; simultaneity constraint; approximation algorithm (search for similar items in EconPapers)
Date: 2010
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595910002934
Access to full text is restricted to subscribers

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:wsi:apjorx:v:27:y:2010:i:06:n:s0217595910002934

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595910002934

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().