Heterogeneous multi-cores utilize the strength of different architectures for executing particular types of workload, and usually offer higher performance and energy efficiency. In this paper, we study the worst-case response time (WCRT) analysis of scheduling of parallel DAG tasks on heterogeneous multi-cores, where the workload of each vertex in the DAG is only allowed to execute on a particular type of cores. The only known WCRT bound for this problem is grossly pessimistic and suffers the problem. In this paper, we propose two new WCRT bounds. The first new bound has the same time complexity as the existing bound, but is more precise and solves its problem. The second new bound explores more detailed task graph structure information to greatly improve the precision, but is computationally more expensive. We prove that the problem of computing the second bound is strongly NP-hard if the number of types in the system is a variable, and develop an efficient algorithm which has polynomial time complexity if the number of types is a constant. Experiments with randomly generated workload show that our proposed new methods are significantly more precise than the existing bound while having good scalability.
@cite_35 @cite_33 studied a special case of the problem model of this paper, which assumes (1) two types of machines, (2) chain-type precedence constraints (3) unit execution time for each scheduling unit. @cite_8 studied the special case where the task graph structures are either in-trees, out-trees or disjoint unions of chains. @cite_13 considered a special case with only two types of machines and assume the execution time of each scheduling unit to be constant so that they can generate a static scheduling list offline (which suffers timing anomalies if applied to the problem model in this paper where each task may execute shorter than its WCET).
@cite_35 @cite_13 @cite_33 @cite_8
2002235837 2027120502 2067597859 2091164478
Abstract [Jansen, K., Woeginger, G. J. and Yu, Z., UET-Scheduling with chain-type precedence constraints . Report 277, Technische Universitat Graz, Institut fur Mathematik, Graz, Austria, 1993.] studied the U2Chain problem in which two processors are given and all jobs have unit processing time; every job can be executed on only one machine; there are chain-type precedence constraints among the jobs and the objective is to minimize the makespan. This problem arises from the job-system where different jobs require different resources, thus a job may be processed only on some special machine. Since the problem is strongly NP-hard, they gave an approximation algorithm with performance ratio of 5 3. The purpose of our paper is to improve their result by giving a new approximation algorithm with a worst-case guarantee 3 2 for this problem. In this paper a new approximation algorithm with worst case performance ratio 3 2 is presented for the problem of scheduling unit execution time jobs on two parallel machines with the objective of minimizing the makespan where each job can be processed on only one machine and there are chain-type precedence constraints in the jobs. This result answers an open problem in [Jansen, K., Woeginger, G. J. and Yu, Z., UET-Scheduling with chain-type precedence constraints . Report 277, Technische Universitat Graz, Institut fur Mathematik, Graz, Austria, 1993.]: “Does there exist a polynomial time heuristic with worst-case guarantee better than 5 3 for the problem U2Chain?”. The new approximation algorithm is also applied to the problem J 2| pmtn | C max . This paper addresses the single machine scheduling problem with a common due date aiming to minimize earliness and tardiness penalties. Due to its complexity, most of the previous studies in the literature deal with this problem using heuristics and metaheuristics approaches. With the intention of contributing to the study of this problem, a branch-and-bound algorithm is proposed. Lower bounds and pruning rules that exploit properties of the problem are introduced. The proposed approach is examined through a computational comparative study with 280 problems involving different due date scenarios. In addition, the values of optimal solutions for small problems from a known benchmark are provided. Mathematical subject classification: 90C11, 62P30, 90B35. We consider the problem of scheduling a given set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a given release date and is compatible to only a subset of the machines. The machines are ordered and indexed in such a way that a higher-indexed machine can process all the jobs that a lower-indexed machine can process. We present a solution procedure to solve this problem in O(n2+mnlogn) time. We also extend our results to the tree-hierarchical processing sets case and the uniform machine case. A companion paper Part I considers the problem of minimizing the weighted earliness and tardiness of jobs scheduled on a single machine around a common due date, d, which is unrestrictively late. This paper Part II considers the problem of minimizing the unweighted earliness and tardiness of jobs, allowing the possibility that d is early enough to constrain the scheduling decision. We describe several optimality conditions. The recognition version of the problem is shown to be NP-complete in the ordinary sense, confirming a well known conjecture. Moreover, this complexity definition is precise, since we describe a dynamic programming algorithm which runs in pseudopolynomial time. This algorithm is also extremely efficient computationally, providing an improvement over earlier procedures, of almost two orders of magnitude in the size of instance that can be solved. Finally, we describe a special case of the problem which is polynomially solvable.