Single Machine Scheduling With Forbidden Intervals And Job Delivery Times
AbstractWe 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoArticle provided by World Scientific Publishing Co. Pte. Ltd. in its journal Asia-Pacific Journal of Operational Research.
Volume (Year): 25 (2008)
Issue (Month): 03 ()
Contact details of provider:
Web page: http://www.worldscinet.com/apjor/apjor.shtml
You can help add them by filling out this form.
reading list or among the top items on IDEAS.Access and download statisticsgeneral information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Tai Tone Lim).
If references are entirely missing, you can add them using this form.