 Online scheduling of two job types on a set of multipurpose machinesShlomo Karhi and Dvir Shabtay International Journal of Production Economics, 2014, vol. 150, issue C, 155-162 Abstract: We study an online-list scheduling problem on a set of m multipurpose machines for which the objective is to minimize the makespan. It is assumed that there are two different job types, and each job type can be processed on a unique subset of machines. We provide an online algorithm with a competitive ratio of 1+k(m−1)/(k(m−s)+s2) where M1={M1,…,Mk} is the set of machines eligible to process jobs of type 1 and where M2={Ms+1,…,Mm} is the set of machines eligible to process jobs of type 2 with k≥s. By analyzing the competitive ratio function, we show that the worst competitive ratio is obtained for an inclusive processing set structure in which the number of machines (m) is even, the first job type can be processed on any of the m machines and the second job type can be processed only on a subset of m/2 machines. Moreover, we provide a lower bound as a function of the processing set structure. Keywords: Multipurpose machine scheduling; Online scheduling; Eligibility constraint; Competitive ratio (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:proeco:v:150:y:2014:i:c:p:155-162 DOI: 10.1016/j.ijpe.2013.12.015 Access Statistics for this article International Journal of Production Economics is currently edited by Stefan Minner More articles in International Journal of Production Economics from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.