A QoS-based resource economic scheduling in manufacturing grid/Aptarnavimo kokybe paremtas ekonominis istekliu planavimas naudojant gamybos tinklelius.

Yifei, Tong ; Dongbo, Li ; Yong, He 等

1. Introduction

In 2000, manufacturing grid was defined as "resource sharing and coordinated problem solving in dynamic, multi-institutional virtual organizations" by Ian Foster [1]. Subsequentially, manufacturing grid was advanced as a novel manufacturing pattern [2], which can realize global resources sharing and distributed enterprises coordination and support the agile manufacturing and the operations of virtual enterprise by providing unitarian resource access interface and transparent resource service [1, 3]. The main problems in manufacturing grid resource management system are the ability to discover user-demand-satisfied services and resources and how to allocate these services and resources to complete tasks.

There are already some research efforts in computational grid resource scheduling and allocation, whose solutions may be summarized as system-centric mechanism, user-centric mechanism and economy-based mechanism [4]. Besides, many scheduling algorithms were studied according to certain scheduling problem and objective. Casanova proposed a complex self-adaptation scheduling algorithm to automatically execute dynamic resource selection and data and computation allocation as well as some simple heuristic algorithms to schedule independent task: Min-min, Max-min, Sufferage and so on. But the scheduling objective of Casanova's algorithm is only to minimize the application execution time [5]. The above researches mainly focus on one or more scheduling problems and objectives with certain application limitation. Obviously the approach is locally optimal based.

The use of economic theory as an increasingly relevant tool for the analysis of operations management issues has been discussed in literature [6]. Nowadays, economy-based grid resource scheduling is becoming the research hot spot of grid resource scheduling. The intention of this present paper is to apply market mechanism into grid resource scheduling allocation. Based on the idea, the behaviors of resource requester (e.g. grid user) and resource provider can be conducted rationally under the guide of economy principles and the utilities of them can be optimized. In the next section, QoS-based (quality of service) resource economic scheduling model is proposed. The QoS-based resource economic scheduling algorithm is presented and discussed detailedly in section 3. The proposed quality of service (QoS) scheduling algorithm simulation is introduced in section 4 as well as the results analysis. Finally the future work will be pointed out.

2. QoS-based resource economic scheduling model

The goal of manufacturing grid resource management system is to match grid resources with grid users' requests described by different types and levels of QoS. Chatterjee et al. proposed to manage grid resource from application level, system level and resource level [7]. While Wu Zhiang et al. considered that the research by Chatterjee et al. neglected the relationship of resources and that the physical reources should be abstracted as logical resources and the logical resources should be clustered into virtual organization (VO) to provide combinatorial services. Our QoS-based resource economic scheduling model on the basis of research in literature [8] is represented in Fig. 1.

* Grid service layer. Applications in manufacturing grid usually are workflows composed of a series of subtasks and in this case grid service layer should access logical resources and aggregate them into combinatorial service to achieve preplanned goals. When the gird user submits applications to service organization, QoS for each service in applications will be negotiated.

* VO layer [8]. VO layer is an important interface between grid service layer and grid resource layer. VO layer maps the QoS demand of the grid users into one certain grid QoS by shielding the resource heterogeneousness. In our research, grid QoS parameter is classified into logical resource type, system type, security type and trust type. By classification, grid QoS parameters can be specified and QoS of VO layer can be easily mapped to grid service layer and grid resource layer.

* Grid resource layer. VO service accesses grid resource layer to achieve preplanned goals. When a grid resource provides services for VOs, QoS for services will be negotiated.

* Grid scheduler. Grid scheduler matches resources with requests and optimizes the goals of systems or users by scheduling algorithm. During the process of scheduling, the grid scheduler acts as a mediation to find and select resources, negotiate service level, match request-resource, monitor requests in whole lifecycle, record intermediate results and historical data and finally to feed the operation results back to users. On the whole, users only need submit tasks to grid scheduler and QoS demand.

* Global QoS utility. QoS-based resource economic scheduling algorithm presented in this paper is decomposing of the global QoS into QoS of grid service layer, VO layer and grid resource layer and optimizing QoS of each layer to achieve global utility optimization.

[FIGURE 1 OMITTED]

3. QoS-based resource economic scheduling algorithm

3.1. Notations of mathematical model

The notations used in this paper are as follows:

[check] n [so.sup.j.sub.i], n [h.sup.k.sub.i], n [f.sup.k.sub.i], n [p.sup.m.sub.i], n [st.sup.n.sub.i] : software, hardware, file, processor and resource allocation obtained by VO service i from every kind of resource provider j, k, l, m, n (dimension depends the resource type);

[check] c [so.sup.j.sub.i], c [h.sup.k.sub.i], c [f.sup.l.sub.i], c [p.sup.m.sub.i], c [st.sup.n.sub.i] : payments of VO service i to every kind of resource provider j, k, l, m, n (dimension: Yuan);

[check] c [s.sup.i.sub.u] : payments of grid user u to VO service i (dimension: Yuan);

[check] [SOC.sub.j], [HC.sub.k], [FC.sub.l], [PC.sub.m], [STC.sub.n] : capacity of the above five types of resource provider j, k, l, m, n (dimension depends the resource type);

[check] n [s.sup.i.sub.u] : service allocation obtained by grid user i from VO service u (dimension depends the service type);

[check] [VOC.sub.i] : capacity of VO service i (dimension depends the service type);

[check] J [so.sub.i], J [h.sub.i], J [f.sub.i], J [p.sub.i], J [st.sub.i] : jobs of the above five types of resource provider (dimension depends the job type);

[check] p [so.sub.j], p [h.sub.j], p [f.sub.j], p [p.sub.j], p [st.sub.j] : the price of resource offered by the above five types of resource provider (dimension: Yuan);

[check] p [vs.sub.i] : : the price of VO service (dimension: Yuan);

[check] [E.sub.u], [VOS.sub.i] : the budget of grid user u and VO service i (dimension: Yuan);

[check] [t.sub.i.sup.n] : time taken by grid user i to finish nth job (dimension: second);

[check] [T.sub.i] : time limits of grid user i to finish all jobs (dimension: second).

3.2. Mathematical model

As introduced in Section 2, in our research the grid global QoS is decomposed into QoS of grid service layer, VO layer and grid resource layer, denoted by

[Q.sub.total] = [[Q.sub.service], [Q.sub.VO], [Q.sub.resource],]

Let [q.sup.l.sub.i] be the lth QoS dimension of ith layer and a, b, c denote the number of QoS dimensions of grid service, VO and resource layer respectively. Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

Associated with each QoS dimension of the three layers is a utility function defining the benefits or utility in choosing certain value of QoS choices in that dimension and representing the global utility of each layer [9]. QoS-based resource economic scheduling can allocate and schedule manufacturing grid resources by optimizing each layer's utility and maximize the system utility under each layer's restraints. The system utility [U.sub.sys] ([Q.sub.global]) can be denoted by

[U.sub.sys] ([Q.sub.global]) = [U.sub.resource] ([q.sup.a.sub.i]) + [U.sub.VO] ([q.sup.b.sub.i]) +

+ [U.sub.service] ([q.sup.c.sub.i]) = [3.summation over (i=1)] [[omega].sub.i][U.sup.l.sub.i]([q.sup.l.sub.i]) (2)

where [U.sup.l.sub.1]([q.sup.l.sub.i]) denote the utility associated with [q.sup.l.sub.i] and 0 [less than or equal to] [[omega].sub.i] [less than or equal to] 1 denote the weight assigned to the ith layer.

The problem of QoS-based resource economic scheduling is formulated as follows

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (3)

3.3. Utility function of each layer and its optimization

3.3.1. Utility optimization of grid resource layer/resource provider

Just as described above, resources in manufacturing grid are classified into software resource, hardware resource, file resource, processor resource and storage resource. So, the utility function of grid resource layer can be defined as the total earnings from sold resources for their service capacities [10], which is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

Every resource provider wishes to maximize the utility subject to that the sold resources' capacity shouldn't exceed the capacity resources can provide. The problem of grid resource layer utility optimization is formulated as follows

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

It can be seen easily that this optimization problem is a conditional extremum problem. The Lagrangian method can be applied to solve such a problem. Let us construct a Lagrangian function ([[lambda].sub.i]-Lagrangian multiplier):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7.1)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7.2)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7.3)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7.4)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7.5)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7.6)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7.7)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7.8)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7.9)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7.10)

From (7.1), we can obtain

c [so.sup.j.sub.i]/n [so.sup.j.sub.i] = [[lambda].sub.j] (8)

From (7.6), we can obtain

[SOC.sub.j] = [summation over (i)] n [so.sup.j.sub.i] (9)

Combining (8) and (9), we can obtain

n [so].sup.j*.sub.i] = c [so.sup.j.sub.i] [SOC.sub.j]/[summation over (i)] c [so.sup.j.sub.i] (10)

where n [so.sup.j*.sub.i] is the unique optimal solution to the software resource j allocation for each VO so as to achieve the maximal its utility. Likewise, we can obtain unique optimal solutions of the rest four types of resources allocation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

3.3.2. Utility optimization of VO layer

VO is the key factor of grid characteristics as an important interface between the grid resource layer (resource provider) and the grid service layer (resource consumer), which can bind grid resource service level with grid application service protocol by searching and matching within VO. The utility function of VO layer can be defined as follows

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

The function utility considers comprehensively logical resource QoS (time taken by services of VO to complete tasks indicated by the polynomial of the above equation), system QoS ([l.sub.i]: environment satisfaction), security QoS ([SAL.sub.i]: security level of each VO service indicated by 0, 1, 2), trust QoS (indicated by success probability of VO service: [N.sub.Suc] / [N.sub.invo], where [N.sub.suc] and [N.sub.invo] denote the times of tasks completion and service invoke respectively).

VO layer wishes to maximize the utility of each service subject to that the reminder funds exceed zero and the output service capacities should be smaller than the capacities services can provide. The problem of VO layer utility optimization is formulated as follows

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (13)

Likewise, so as to achieve the maximal VO's utility, we can adopt the Lagrangian method to obtain unique optimal solution of the VO service allocation for grid user service utility [n.s.sup.i*.sub.u]

n [s.sup.i*.sub.u] = c [s.sup.i.sub.u] [VOC.sub.i]/[summation over (u)] c [s.sup.i.sub.u] (14)

and unique optimal solutions of the payments to every type of manufacturing grid resources

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (16)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (17)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (18)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (19)

3.3.3. Utility optimization of grid service layer/resource consumer

We assume that the utility of each grid service layer is the same and it can be defined as the reminder of funds and time after resource consumption [10], denoted by

[U.sub.service] (c [s.sup.i.sub.u]) = ([E.sub.u] - [summation over (i)] c [s.sup.i.sub.u]) + ([T.sub.i] - [summation over (v)] [QU.sub.uv]/n [s.sup.i.sub.u]) (20)

Each grid user wishes to maximize the utility subject to that the time taken by grid user to complete services shouldn't exceed the deadline. The problem of grid resource layer utility optimization is formulated as follows [10]

max {([E.sub.u] - [summation over (i)] c [s.sup.i.sub.u]) + [T.sub.i] - [summation over (v)] [[QU.sub.uv]/n [s.sup.i.sub.u]])}

s.t. [summation over (n)] [t.sup.n.sub.i] [less than or equal to]

where [QU.sub.uv] denotes the QoS demand of the uth grid user's vth task and n [s.sup.i.sub.u] equals to [VOC.sub.i]c [s.sup.i.sub.u]/p [vs.sub.i] indicated that VO service is allocated according to price-oriented mechanism.

Likewise, so as to achieve the maximal grid user's utility, we adopt the Lagrangian method to obtain unique optimal solution of the payments for VO service c [s.sup.i*.sub.u]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (21)

3.4. Price and demand readjustment mechanism

In Section 3.3, the unique optimal solutions of each layer are presented. However, initial price/payment, supply/demand cannot make the global QoS optimization. The problem can be solved based on economic theory to reflect and readjust the supply and demand of resources according to the resource's price. So, the iteration equation P = P + [delta](S - D) is introduced in our research to determine the resource' price [11]: P denotes the resource price, [delta] denotes the price readjustment multiplier with supply and demand, S denotes the supply and D denotes the demand. The iteration algorithm is shown in the dotted frame of Fig. 2.

3.5. QoS scheduling algorithm for manufacturing grid utility optimization

The process of QoS-based resource economic scheduling algorithm in our research is illustrated in Fig. 2. The synchronous negotiation between the grid user layer and VO layer, the VO layer and manufacturing grid resource layer can be realized by allocating adequate VO services and grid resources according to price-oriented mechanism. Take the negotiation between a grid service layer and VO layer as an example to describe the process of QoS-based resource economic scheduling algorithm.

Firstly, initial price information of grid VO is sent to the grid service layer. Then the optimal solutions of payments to each VO service are calculated. Thirdly, the demand of VO service is readjusted and the results of adjustment are fed back to VO layer. Fourthly, VO layer readjust the VO services' prices and send them to the grid user. The iteration ends until supply and demand are balanced by price mechanism to readjust supply and demand. The negotiation between the VO layer and grid resource layer is alike.

Besides, from Fig. 2 it can be seen that the optimal solving is carried in meantime T repeatedly. When the supply of resource/VO service is more than the demand, then the price of resource/VO service descends. And when the demand of resource/VO service is more than the supply, then the price of resource/VO service ascends. The above process is called Tatonnement process in economic theory [11]. The convergence property of Tatonnement process can be proved by constructing Lyapunov energy function as well as its fast convergence rate [11]. The balanced price can be obtained by Tatonnement process.

[FIGURE 2 OMITTED]

4. QoS scheduling algorithm simulation

In our research, we adopt the simulation parameters in literature [12] and analyze the proposed algorithm performance using grid simulator- GridSim. To demonstrate our algorithm, we compare our algorithm performance with the algorithm in literature 13 and cost-time algorithm proposed by Buyya [13] in task accomplishment rate and resource allocation rate. The simulated and compared results are listed in Table.

The data listed in Table is the improvement percentage of the two comparative indexes. From the simulation results, it can be concluded that the task accomplishment rate improves 14.8% compared with the algorithm in literature [12] and 22.9% compared with the cost-time algorithm. Besides, the resource allocation rate improves 1.795% compared with the algorithm in literature [12] owing to the adjustment mechanism. The simulation results denominate that the proposed QoS-based manufacturing grid resource economic scheduling algorithm can make manufacturing grid global optimization considering all QoS attributes and it is flexible and effective.

5. Conclusions

The work reported here on QoS-based resource economic scheduling in manufacturing grid is an extended part of APPGS reported by the authors before. This research seeks to solve manufacturing grid resource scheduling by QoS-based resource economic scheduling to achieve global utility optimization. An initial round of investigation has been completed, and a scheduling algorithm has been proposed and proved to be effective and flexible. The next steps are to study the intellectual property protection mechanism so as to guarantee the legal rights of resource providers. Findings from the ongoing investigation will be reported separately in the near future.

Acknowledgements

This work was financially supported by Postdoctoral Program of Science Foundation of Jiangsu Province of China (0901041C), Zijin Star of Outstanding Program of NJUST and the National Natural Science Foundation of China(61104171). The supports are gratefully acknowledged. The authors would also acknowledge the Editor of Mechanika.

Received April 05, 2011

Accepted August 21, 2012

References

[1.] Foster, I.; Kesselman, C.; Tuecke, S. 2001.The anatomy of the grid, International Journal of Supercomputer Application 15: 1-21.

[2.] Fan Yushun. 2005. The conception of manufacturing grid and its architecture, Aeronautical Manufacturing Technology (10): 42-45.

[3.] Anuziene, L.; Bargelis, A. 2007. Decision support system framework for agile manufacturing of mechanical products, Mechanika 3(65): 51-66.

[4.] Huang Zhixing; Liu Hongtao; Qiu Yuhui. 2006. The research progress of economic-based resource management and grid economics, Computer Science 33(9): 110-114.

[5.] Casanova, H.; Obertelli, G.; Berman, F.; et al. 2000. The apples parameter sweep template: user-level middleware for the grid, Scientific Programming 8(3): 111-126.

[6.] Rajiv D. Banker; Inder S. Khosla. 1995. Economics of operations management: A research perspective, Journal of Operations Management (12): 423-435. http://dx.doi.org/10.1016/0272-6963(95)00022-K.

[7.] Chatterjee, B.; Sydir, M.; Lawrence, T. FTaxonomy for QoS specifications. Proc. Of the 3rd Int'l Workshop on Objected-Oriented Real-Time Dependable Systems (WORDS'97), Newreport Beach: 100-107.

[8.] Wu Zhiang; Luo Junzhou; Song Aibo. 2006. QoS-based grid resource management, Journal of Software, 17(11): 2264-2276. http://dx.doi.org/10.1360/jos172264.

[9.] Li Chunlin, Li Layuan. 2006. QoS based resource scheduling by computational economy in computational grid, Information Processing Letters (98): 119-126. http://dx.doi.org/10.1016/j.ipl.2006.01.002.

[10.] Li Chunlin, Li Layuan. 2005. A distributed utility-based two level market solution for optimal resource scheduling in computational grid, Parallel Computing (31): 332-351. http://dx.doi.org/10.1016/j.parco.2005.02.011.

[11.] Varian HR. 1992. Microeconomic Analysis, New York: W.W. Norton & Company.

[12.] Yu Jianjun; Zheng Yuezhai; Yang Mingxia. 2007. Resource scheduling algorithm for computing grid based on utility optimization, Journal of Computer Applications (3): 541-549.

[13.] Buyya R. 2002. Economic-based Distributed Resource Management and Scheduling for Grid Computing, Melbourne: Monash University.

Tong Yifei, Nanjing University of Science and Technology, School of Mechanical Engineering, 210094 Nanjing, People's Republic of China, E-mail:tyf51129@yahoo.com.cn

Li Dongbo, Nanjing University of Science and Technology, School of Mechanical Engineering, 210094 Nanjing, People's Republic of China, E-mail: db_callar@yahoo.com.cn

He Yong, Nanjing University of Science and Technology, School of Mechanical Engineering, 210094 Nanjing, People's Republic of China, E-mail: yhe1964@mail.njust.edu.cn

He Fei, Huazhong University of Science & Technology, School of Mechanical Engineering, 430074 Wuhan, People's Republic of China, E-mail: feihe1982@163.com

cross ref http://dx.doi.org/10.5755/j01.mech.18.4.2336

Table
Simulation results of QoS scheduling algorithm

       Budget       5000   9000   13000   17000

Dead   Contrast
line   index (%)

100    task         2.5    4.9     7.8     9.7
       finish
       rate

       resource     2.1    1.9     0.5     0.2
       allocation
       rate

600    task         25.5   25.4   22.1    15.2
       finish
       rate

       resource     2.3    2.0     0.9     0.4
       allocation
       rate

1100   task         30.1   34.7   24.8     5.4
       finish
       rate

       resource     2.7    2.3     1.4     0.9
       allocation
       rate

1600   task         28.4   25.7   20.6     5.2
       finish
       rate

       resource     3.1    2.6     1.5     1.1
       allocation
       rate

2100   task         5.5    3.7     0.3    -1.4
       finish
       rate

       resource     3.8    3.0     1.9     1.3
       allocation
       rate