TY - JOUR
T1 - The Loading Time Scheduling Problem
AU - Bhatia, Randeep
AU - Khuller, Samir
AU - Naor, Joseph
N1 - Funding Information:
In this paper we study precedence constrained scheduling problems, where the tasks can only be executed on a specified subset of the set of 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 and query optimization in databases and in other artificial intelligence applications. We give the first nontrivial approximation algorithm for this problem. We also prove nontrivial lower bounds on best possible approximation ratios for these problems. These improve on the nonapproximability results that are implied by the nonapproxima-bility results for the shortest common supersequence problem. We use the same algorithm 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. Q 2000 Academic Press 1An extended abstract of this paper appeared in the Proceedings of the 36th IEEE Conference on Foundations of Computer Science, Milwaukee, Wisconsin, pp. 72—81, 1995. 2E-mail: [email protected]. 3 Research supported by NSF Research Initiation Award CCR-9307462 and NSF CAREER Award CCR-9501355. E-mail: [email protected]. 4Research supported in part by Grant No. 92-00225 from the United States—Israel Binational Science Foundation (BSF), Jerusalem. Research also supported by the Technion V.P.R. Fund 120-882, Israel. E-mail: [email protected].
PY - 2000/7
Y1 - 2000/7
N2 - In this paper we study precedence constrained scheduling problems, where the tasks can only be executed on a specified subset of the set of 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 and query optimization in databases and in other artificial intelligence applications. We give the first nontrivial approximation algorithm for this problem. We also prove nontrivial lower bounds on best possible approximation ratios for these problems. These improve on the nonapproximability results that are implied by the nonapproximability results for the shortest common supersequence problem. We use the same algorithm 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.
AB - In this paper we study precedence constrained scheduling problems, where the tasks can only be executed on a specified subset of the set of 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 and query optimization in databases and in other artificial intelligence applications. We give the first nontrivial approximation algorithm for this problem. We also prove nontrivial lower bounds on best possible approximation ratios for these problems. These improve on the nonapproximability results that are implied by the nonapproximability results for the shortest common supersequence problem. We use the same algorithm 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.
UR - http://www.scopus.com/inward/record.url?scp=0346045905&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0346045905&partnerID=8YFLogxK
U2 - 10.1006/jagm.2000.1076
DO - 10.1006/jagm.2000.1076
M3 - Article
AN - SCOPUS:0346045905
SN - 0196-6774
VL - 36
SP - 1
EP - 33
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 1
ER -