Show simple item record

The Loading Time Scheduling Problem

dc.contributor.authorBhatia, Randeepen_US
dc.contributor.authorKhuller, Samiren_US
dc.contributor.authorNaor, Joseph (Seffi)en_US
dc.description.abstractIn this paper we study precedence constrained scheduling problems, where the tasks can only be executed on a specified subset of the machines. Each machine has a loading time that is incurred only for the first task that is scheduled on the machine in a particular run. This basic scheduling problem arises in the context of machining on numerically controlled machines, query optimization in databases, and in other artificial intelligence applications. We give the first non-trivial approximation algorithm for this problem. We also prove non-trivial lower bounds on best possible approximation ratios for these problems. These improve on the non-approximability results that are implied by the non-approximability results for the shortests common supersequence problem. We use the same algorithmic technique to obtain approximation algorithms for a problem arising in the context of code generation for parallel machines, and for the weighted shortest common supersequence problem.en_US
dc.format.extent283294 bytes
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3653en_US
dc.titleThe Loading Time Scheduling Problemen_US
dc.typeTechnical Reporten_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtComputer Science Department Technical Reportsen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record