{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T06:03:55Z","timestamp":1648965835050},"reference-count":22,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2009,6]]},"abstract":"<jats:p> We investigate the problems of scheduling n jobs to m machines with availability constraints. We consider two different models of availability constraints: the preventive model where the unavailability is due to preventive machine maintenance, and the fixed job model where the unavailability is due to a priori assignment of some of the n jobs to certain machines at certain times. In both models, the objective is to minimize the makespan. We assume that m is a constant, and if a job is interrupted by the unavailable interval, it can be resumed after the machine becomes available. <\/jats:p><jats:p> For fixed job model, we show there is an FPTAS. For the preventive model, we show that if at least one machine is always available, then the PTAS for Multiple Subset Sum problem given by Kellerer can be applied to get a PTAS; otherwise, every machine has some unavailable intervals, we show that if (m - 1) machines each of which has unavailable intervals with total length bounded by \u03b1(n) \u00b7 P<jats:sub> sum <\/jats:sub>\/m where P<jats:sub> sum <\/jats:sub> is the total processing time of all jobs and \u03b1(n) can be any non-negative function, we can develop a (1 + \u03b1(n) + \u220a)-approximation algorithm for any constant 0 &lt; \u220a &lt; 1; further we show that there does not exist any polynomial time (1 + \u03b1(n) - o(1))-approximation unless P = NP. <\/jats:p>","DOI":"10.1142\/s1793830909000129","type":"journal-article","created":{"date-parts":[[2009,7,2]],"date-time":"2009-07-02T11:53:30Z","timestamp":1246535610000},"page":"141-151","source":"Crossref","is-referenced-by-count":3,"title":["MAKESPAN MINIMIZATION WITH MACHINE AVAILABILITY CONSTRAINTS"],"prefix":"10.1142","volume":"01","author":[{"given":"BIN","family":"FU","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Texas\u2013Pan American, Edinburg, TX 78539, USA"}]},{"given":"YUMEI","family":"HUO","sequence":"additional","affiliation":[{"name":"Department of Computer Science, College of Staten Island, CUNY, Staten Island, New York 10314, USA"}]},{"given":"HAIRONG","family":"ZHAO","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Computer Science &amp; Statistics, Purdue University Calumet, Hammond, IN 46323, USA"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf1","first-page":"1195","volume":"26","author":"Baewicz J.","journal-title":"Parallel Comput."},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/s001860200267"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00010-7"},{"key":"rf4","unstructured":"B.\u00a0Chen, C.\u00a0Potts and G.\u00a0Woeginger, Handbook of Combinatorial Optimization, eds. D. Z.\u00a0Du and P.\u00a0Pardalos (Kluwer, Boston, 1998)\u00a0pp. 21\u2013169."},{"key":"rf7","author":"Fu B.","journal-title":"Theor. Comput. Sci."},{"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.1145\/7531.7535"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2004.12.002"},{"key":"rf11","first-page":"991","volume":"30","author":"Kellerer H.","journal-title":"IIE Trans."},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(01)00083-2"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2007.10.013"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1007\/BF00121681"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2003.08.034"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/s00170-006-0524-4"},{"key":"rf17","unstructured":"C. Y.\u00a0Lee, Handbook of Scheduling, ed. J. Y.T.\u00a0Leung (CRC Press, 2004)\u00a0pp. 22.1\u201322.13."},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2006.11.027"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(91)90013-M"},{"key":"rf21","first-page":"360","volume":"1","author":"Saidy H.","journal-title":"J. Ind. Sys. Eng."},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1425(199911\/12)2:6<267::AID-JOS31>3.0.CO;2-H"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(98)00367-1"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2005.09.002"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1016\/j.camwa.2005.07.008"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830909000129","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:57:50Z","timestamp":1565193470000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830909000129"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6]]},"references-count":22,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2009,6]]}},"alternative-id":["10.1142\/S1793830909000129"],"URL":"https:\/\/doi.org\/10.1142\/s1793830909000129","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6]]}}}