SCHEDULING WITH DISCRETELY COMPRESSIBLE RELEASE DATES TO MINIMIZE MAKESPAN

Shu-Xia Zhang (), Zhi-Gang Cao and Yu-Zhong Zhang
Additional contact information
Shu-Xia Zhang: Department of Watercraft Command, Zhenjiang Watercraft College, Zhenjiang 212003, China
Zhi-Gang Cao: Key Laboratory of Management, Decision and Information Systems, AMSS, CAS, Beijing, 100190, China
Yu-Zhong Zhang: College of Operations Research and Management Science, Qufu Normal University, Rizhao 276826, China

Asia-Pacific Journal of Operational Research (APJOR), 2010, vol. 27, issue 04, 493-501

Abstract: In this paper, we address the scheduling model with discretely compressible release dates, where processing any job with a compressed release date incurs a corresponding compression cost. We consider the following problem for the first time: scheduling with discretely compressible release dates to minimize the sum of makespan plus total compression cost. We show its NP-hardness, and design an approximation algorithm with worst-case performance ratio 2, which is the best possible if the processing order of the jobs is pre-specified.

Keywords: Scheduling; discretely compressible release dates; approximation algorithm; makespan (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/S0217595910002818
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:04:n:s0217595910002818

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595910002818

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