SINGLE MACHINE SCHEDULING WITH FORBIDDEN INTERVALS AND JOB DELIVERY TIMES

Jinjiang Yuan (), Lei Shi and Jinwen Ou
Additional contact information
Jinjiang Yuan: Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450052, China
Lei Shi: Department of Mathematics, Anyang Normal University, Anyang, Henan 455000, China
Jinwen Ou: Department of Administrative Management, Jinan University, Guangzhou, Guangdong 510632, China

Asia-Pacific Journal of Operational Research (APJOR), 2008, vol. 25, issue 03, pages 317-325

Abstract: We consider a non-preemptive single machine scheduling problem with forbidden intervals. Associated with each job is a given processing time and a delivery time to its customer, when the processing of the job is complete. The objective is to minimize the time taken for all the jobs to be delivered to the customers. The problem is strongly NP-hard in general. In this study, we show that the case with a fixed number of forbidden intervals can be solved by a pseudo-polynomial time algorithm, while no polynomial time approximation algorithm with a fixed performance ratio exists for the case with two forbidden intervals. We also develop a polynomial time approximation scheme (PTAS) for the case with a single forbidden interval.

Keywords: Forbidden intervals; delivery times; polynomial time approximation algorithms; PTAS; performance ratio (search for similar items in EconPapers)
Date: 2008
References: Add references at CitEc
Citations Track citations by RSS feed

Downloads: (external link)
http://www.worldscinet.com/cgi-bin/details.cgi?type=pdf&id=pii:S0217595908001778 (application/pdf)
http://www.worldscinet.com/cgi-bin/details.cgi?typ ... ii:S0217595908001778 (text/html)
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: http://EconPapers.repec.org/RePEc:wsi:apjorx:v:25:y:2008:i:03:p:317-325

Ordering information: This journal article can be ordered from

Access Statistics for this article

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

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