caa a22 4500 445838469 CHVBK 20180317145336.0 cr unu---uuuuu 170323e20110201xx s 000 0 eng 10.1007/s10951-010-0190-0 doi (NATIONALLICENCE)springer-10.1007/s10951-010-0190-0 Scheduling jobs with equal processing times subject to machine eligibility constraints [Elektronische Daten] [Kangbok Lee, Joseph Leung, Michael Pinedo] We consider the problem of nonpreemptively scheduling a set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a prespecified set of machines on which it can be processed, called its eligible set. We consider the most general case of machine eligibility constraints as well as special cases of nested and inclusive eligible sets. Both online and offline models are considered. For offline problems we develop optimal algorithms that run in polynomial time, while for online problems we focus on the development of optimal algorithms of a new and more elaborate structure as well as approximation algorithms with good competitive ratios. Springer Science+Business Media, LLC, 2010 Parallel machine scheduling nationallicence Eligibility constraint nationallicence Nested and inclusive eligible sets nationallicence Equal-processing-time jobs nationallicence Online and offline scheduling nationallicence Makespan nationallicence Competitive ratio nationallicence Worst-case ratio nationallicence Lee Kangbok Department of Information, Operations & Management Sciences, Stern School of Business, New York University, 44 West 4th Street, 10012-1126, New York, NY, USA aut Leung Joseph Department of Computer Science, New Jersey Institute of Technology, 07102, Newark, NJ, USA aut Pinedo Michael Department of Information, Operations & Management Sciences, Stern School of Business, New York University, 44 West 4th Street, 10012-1126, New York, NY, USA aut Journal of Scheduling Springer US; http://www.springer-ny.com 14/1(2011-02-01), 27-38 1094-6136 14:1<27 2011 14 10951 https://doi.org/10.1007/s10951-010-0190-0 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10951-010-0190-0 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Lee Kangbok Department of Information, Operations & Management Sciences, Stern School of Business, New York University, 44 West 4th Street, 10012-1126, New York, NY, USA aut NATIONALLICENCE 700 1- Leung Joseph Department of Computer Science, New Jersey Institute of Technology, 07102, Newark, NJ, USA aut NATIONALLICENCE 700 1- Pinedo Michael Department of Information, Operations & Management Sciences, Stern School of Business, New York University, 44 West 4th Street, 10012-1126, New York, NY, USA aut NATIONALLICENCE 773 0- Journal of Scheduling Springer US; http://www.springer-ny.com 14/1(2011-02-01), 27-38 1094-6136 14:1<27 2011 14 10951 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer