Consider the execution of a parallel application that dynamically generates parallel jobs with specified resource requirements during its execution. We assume that there is not sufficient knowledge about the running t...
详细信息
Consider the execution of a parallel application that dynamically generates parallel jobs with specified resource requirements during its execution. We assume that there is not sufficient knowledge about the running times and the number of jobs generated in order to precompute a schedule for such applications. Rather, the scheduling decisions have to be made on-line during runtime based on incomplete information. We present several on-line scheduling algorithms for various interconnection topologies that use some a priori information about the job running times or guarantee a good competitive ratio that depends on the runtime ratio of all generated jobs. All algorithms presented have optimal competitive ratio up to small additive constants, and are easy to implement. (C) 2001 Elsevier Science B.V. All rights reserved.
Given a directed graph G=(V,E), it is supposed that edges are added to or deleted from G one at a time, and that one wishes to compute its transitive closure in the online manner, i.e., each time an edge is added or d...
详细信息
Given a directed graph G=(V,E), it is supposed that edges are added to or deleted from G one at a time, and that one wishes to compute its transitive closure in the online manner, i.e., each time an edge is added or deleted. In the case of an undirected graph, G, the problem of online computation of connected components of G has been comprehensively studied. However, no nontrivial onlinealgorithm for computing the transitive closure of general directed graphs has been reported. Online transitive closure algorithms are presented for 2 problems: 1. q edges are successively added to G=(V,E), and 2. q edges are successively deleted from G=(V,E).
In this paper, some results concerning the k-truck problem are produced. Firstly, the algorithms and their complexity concerning the off-line k-truck problem are discussed. Following that, a lower bound of competitive...
详细信息
In this paper, some results concerning the k-truck problem are produced. Firstly, the algorithms and their complexity concerning the off-line k-truck problem are discussed. Following that, a lower bound of competitive ratio (1 + 0) (.) k/(o (.) k + 2) for the on-line k-truck problem is given, where theta is the ratio of cost of the loaded truck and the empty truck on the same distance, and a relevant lower bound for the on-line k-taxi problem followed naturally. Thirdly, based on the Position Maintaining Strategy (PMS), some new results which are slightly better than those of [11] for general cases are obtained. For example, a c-competitive or (c/theta + 1/theta +1)-competitive algorithm for the on-line k-truck problem depending on the value of theta, where c is the competitive ratio of some algorithm to a relevant k-server problem, is developed. The Partial-Greedy algorithm (PG) is used as well to solve this problem on a line with n nodes and is proved to be a (1 + (n - k)/theta)-competitive algorithm for this case. Finally, the concepts of the on-line k-truck problem are extended to obtain a new variant: Deeper On-line k-Truck Problem (DTP). We claim that results of PMS for the STP (Standard Truck Problem) hold for the DTP.
In this paper, we consider a two-dimensional version of the on-line bin packing problem, in which each rectangular item that should be packed into unit square bins is "rotatable" by 90degrees. Two on-line al...
详细信息
In this paper, we consider a two-dimensional version of the on-line bin packing problem, in which each rectangular item that should be packed into unit square bins is "rotatable" by 90degrees. Two on-line algorithms for solving the problem are proposed. The second algorithm is an extension of the first algorithm, and the worst-case ratio of the second one is at least 2.25 and at most 2.565. (C) 2002 Elsevier Science B.V. All rights reserved.
We study the worst-case performance of approximation algorithms for the problem of multiprocessor task scheduling on m, identical processors with resource augmentation, whose objective is to minimize the makespan. In ...
详细信息
We study the worst-case performance of approximation algorithms for the problem of multiprocessor task scheduling on m, identical processors with resource augmentation, whose objective is to minimize the makespan. In this case, the approximation algorithms are given k (k >= 0) extra processors than the optimal off-linealgorithm. For on-line algorithms, the Greedy algorithm and shelf algorithms are studied. For off-linealgorithm, we consider the LPT (longest processing time) algorithm. Particularly, we prove that the schedule produced by the LPT algorithm is no longer than the optimal off-linealgorithm if and only if k >= m - 2.
In the on-line rescheduling on a single machine, a set of original jobs has already been scheduled to minimize some cost objective, when a new set of jobs arrives over time. The decision maker needs to insert the new ...
详细信息
ISBN:
(纸本)9780769537788
In the on-line rescheduling on a single machine, a set of original jobs has already been scheduled to minimize some cost objective, when a new set of jobs arrives over time. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. In this paper, we consider the on-line rescheduling problem to minimize makespan under a limit on the maximum disruption constraints and give an on-line algorithm of competitive ratio 3/2.
This paper studies the on-line supply chain scheduling problem for single machine with multiple customers under the constraint of the unlimited number of vehicles but limited vehicle capacity. The customers place thei...
详细信息
This paper studies the on-line supply chain scheduling problem for single machine with multiple customers under the constraint of the unlimited number of vehicles but limited vehicle capacity. The customers place their orders on-line, which means that no information of future jobs is known beforehand. The jobs are processed on a single machine and then delivered to the customers by vehicles. Every vehicle can only contain the jobs of the same customer and every batch has the same fixed cost. The objective of the scheduling is to minimize the total makespan and the total delivery cost. Such a problem is called on-line problem. An on-line algorithm for the problem is designed, which is proved to be 2 + 1/2-competitive. The paper also presents a case study for demonstrating the robustness and efficiency of the algorithm. (C) 2015, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved.
This paper presents an on-line algorithm for the construction of position trees, i.e., an algorithm which constructs the position tree for a given string while reading the string from left to right. In addition, an on...
详细信息
This paper presents an on-line algorithm for the construction of position trees, i.e., an algorithm which constructs the position tree for a given string while reading the string from left to right. In addition, an on-line correction algorithm is presented which—upon a change in the string—can be used to construct the new position tree. Moreover, special attention is paid to computers with small memory. compactification of the trees and transport costs between main and secondary storage are discussed.
In this paper, we consider the on-line scheduling of unit time jobs with rejection on rn identical parallel machines. The objective is to minimize the total completion time of the accepted jobs plus the total penalty ...
详细信息
In this paper, we consider the on-line scheduling of unit time jobs with rejection on rn identical parallel machines. The objective is to minimize the total completion time of the accepted jobs plus the total penalty of the rejected jobs. We give an on-line algorithm for the problem with competitive ratio 1/2 （2 ＋√3） ≈ 1.86602.
In this paper we consider an on-line scheduling problem, where jobs with similar processing times within [1, r] arrive one by one to be scheduled in an on-line setting on two identical parallel processors without pree...
详细信息
In this paper we consider an on-line scheduling problem, where jobs with similar processing times within [1, r] arrive one by one to be scheduled in an on-line setting on two identical parallel processors without preemption. The objective is to nlinimize makespan. We devise a randomized on-line algorithm for this problem along with a lower bound.
暂无评论