{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:27:48Z","timestamp":1759847268799},"reference-count":23,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p> 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. <\/jats:p>","DOI":"10.1142\/s0217595908001778","type":"journal-article","created":{"date-parts":[[2008,7,18]],"date-time":"2008-07-18T10:21:41Z","timestamp":1216376501000},"page":"317-325","source":"Crossref","is-referenced-by-count":15,"title":["SINGLE MACHINE SCHEDULING WITH FORBIDDEN INTERVALS AND JOB DELIVERY TIMES"],"prefix":"10.1142","volume":"25","author":[{"given":"JINJIANG","family":"YUAN","sequence":"first","affiliation":[{"name":"Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450052, China"}]},{"given":"LEI","family":"SHI","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Anyang Normal University, Anyang, Henan 455000, China"}]},{"given":"JINWEN","family":"OU","sequence":"additional","affiliation":[{"name":"Department of Administrative Management, Jinan University, Guangzhou, Guangdong 510632, China"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288977"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.10045"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(03)00232-7"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1287\/opre.31.2.381"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04550-3"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1080\/07408170304416"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2601998"},{"key":"rf8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1520-6750(199910)46:7<845::AID-NAV6>3.0.CO;2-#"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1287\/moor.17.1.22"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1002\/nav.20083"},{"key":"rf15","doi-asserted-by":"crossref","first-page":"205","DOI":"10.15807\/jorsj.22.205","volume":"22","author":"Kise H.","journal-title":"Journal of Operation Research Society Japan"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/S0927-0507(05)80189-6"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1007\/BF00121681"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(00)00322-2"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026272526225"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.06.005"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2600791"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2003.08.026"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1425(199911\/12)2:6<267::AID-JOS31>3.0.CO;2-H"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(98)00367-1"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2003.10.043"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595908001778","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T14:01:13Z","timestamp":1565186473000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0217595908001778"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":23,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,6]]}},"alternative-id":["10.1142\/S0217595908001778"],"URL":"https:\/\/doi.org\/10.1142\/s0217595908001778","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"value":"0217-5959","type":"print"},{"value":"1793-7019","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}