Abstract
Cloud manufacturing (CMfg) is a service-oriented manufacturing paradigm that distributes resources in an on-demand business model. In the cloud manufacturing environment, scheduling is considered as an effective tool for satisfying customer requirements which has attracted attention from researchers. In this case, quality of service (QoS) in the scheduling plays a vital role in assessing the impacts of the distributed resources in operation on the performance of scheduling functions. In this paper, a queuing system is employed to model the scheduling problem with multiple servers and then scheduling in cloud manufacturing is classified based on various QoS requirements. Moreover, a set of heavy traffic limit theorems is introduced as a new approach to solving this scheduling problem in which different heavy traffic limits are provided for each of QoS-based scheduling classes. Finally, the number of operational resources in the scheduling is determined by considering the results obtained in the numerical analysis of the heavy traffic limit with different queue disciplines. The results show that different numbers of active machines in various QoS requirements classes play a vital role in that the required QoS metrics such as the expected waiting time and the expected completion time which are critical performance indicators of the cloud’s service are intimately related.
You have full access to this open access chapter, Download conference paper PDF
Similar content being viewed by others
Keywords
1 Introduction
In the cloud manufacturing (CMfg) paradigm which is inspired from the cloud computing, the connected enterprises/customers can offer their core competencies as services or acquire services on demand and the service providers share their resources in this environment [1, 2]. In terms of a central cloud management system, it is necessary to have a mechanism such as computer simulation [3] or optimization. The task scheduling in cloud manufacturing is an arduous process due to different and heterogeneous tasks (Jobs, Orders) with various functional and non-functional requirements that should be scheduled and accomplished together [4]. CMfg is customer-oriented manufacturing and in order to satisfy customer, the research papers focused on the influences of timeliness [5]. Wu et al. [6] develop a mixed linear programming model of 3D printing based on additive manufacturing cloud platform to minimize average cost per volume of material. According to [7], a cloud-based system is capable of facilitating adaptive shop floor scheduling and condition-based maintenance. When client submits all tasks into the cloud platform, then they would be decomposed into a number of subtasks and a scheduling plan would be built [8]. Scheduling in cloud manufacturing is fundamentally different from traditional scheduling scenarios as it deals with a “many-resources/services-to-many orders/tasks” scenario in that cloud-based manufacturing (CMfg) platforms are large-scale complex manufacturing tasks [9, 10]. In the cloud-based scheduling, Quality of Service (QoS) and low cost are requested by cloud client side while using optimal resources and making profit are brought under one roof by cloud providers [11].
In view of all mentioned so far, it may be supposed that the CMfg system with many resources in line up is a queuing system. In this paper, we identify four different types of QoS requirements that characterize the performance of the cloud-based scheduling under heavy traffic limits. Taking a design point of view, this paper attempts to show how many machines a cloud needs to support a specified system load and provide a level of quality of service. A mathematical model is developed based on heavy traffic limits in order to realize the relationship between traffic intensity and the number of machines in cloud-based environment. This model allows us to determine the number of operational machines so that they meet the QoS requirements while maintaining a cost-effective and stable operation.
A new method of formulating queueing problems is in terms of a “heavy traffic” that is developed in this study which is a new approach instead of using stochastic differential equations [12] and has received considerable critical attention in the research papers. Kingman [13] describes the behaviour of the queue system with different impartial queue discipline under heavy traffic regime. A queue system is in heavy traffic regime when the traffic intensity ρ is less than, but very near, one at which jobs are served and the number of machines n is considered very large (n → ∞) [12]. Authors in [14] propose the linear combinations of queue lengths in heavy traffic in that the input-queued switch with correlated arrivals is considered. A heavy traffic limit for GI/G/1-type Markov chains in [15] is applied in which the heavy-traffic-limit formula for the moments of the stationary distribution is proposed. Maguluri et al. [16] provide a stochastic model for load balancing problems and scheduling problems under the heavy traffic limit and optimization algorithms to analyse the queue length. The performance of longest idle server first (LISF) rule and the random routing (RR) is analysed by theoretical support [17] in that the many server heavy traffic limit and quality driven (QD) are established. The term “heavy traffic” is an adequate tool when the load on the system is equal to capacity of the system [18]. A framework developed by [19] uses the Moment Generating Function (MGF) method to distribute the tasks in a queue system under heavy traffic limits. Scully et al. [20] provide a new variation of Gittins policy to optimize the response time in the heavy traffic M/G/1 in which the multi-server scheduling distributes a class of finite job size in the system. Atar et al. [21] propose formulas that approximate these performance measures and depend on the steady-state mean number of available servers in that a model with many servers and server vacations is considered.
The methodological approach taken in this study is a mixed methodology based on QoS requirements and heavy traffic limit theory in cloud-based scheduling. This paper has been organized in the following way. Section 2 describes cloud manufacturing systems (CMfg) focusing on aspects of scheduling in CMfg in order to address the scheduling concept using mathematical models. In Sect. 3 different QoS requirements are classified and then, the heavy traffic limits formulas based on QoS classes are presented. Section 4 provides the mathematical models for heavy traffic limits in each QoS class in which based some assumptions, the number of machines in each QoS class is obtained. The fifth section presents the results of the study and discusses the importance of them and finally, Sect. 6 concludes the research paper.
2 Cloud Manufacturing Platform
In a cloud manufacturing environment, a central cloud platform is responsible for handling the submission of tasks by service consumers, and result delivery to the consumers on one hand and resource publication/registration by the service providers and task dispatching to the providers on the other hand. Figure 1 illustrates various sections of a Cloud-based manufacturing system. In the first step, when a complex task is submitted into the cloud, it must go through the decomposition process so that it will be broken down into multiple single functional subtasks. Then, all the virtualized resources that exist in the cloud manufacturing platform will be retrieved based on their functional attributes in the service discovery and matching process. After forming the service candidate sets, it is the time for the service composition which can be defined as selecting one candidate service from each corresponding candidate set to compose the service while ensuring the overall QoS (a function of non-functional attributes) is optimal. Once a set of composed paths were found, the resource scheduling module will strive for finding the optimal schedule through solving the optimization problem associated with those paths.
The best definition of scheduling is given by Pinedo [22]: ‘‘Scheduling is a decision-making process that is used on a regular basis in many manufacturing and services industries; it deals with the allocation of resources to tasks over given time periods and its goal is to optimize one or more objectives.’’ Various researchers have built up their models based on different objective functions, attributes, and constraints. These details will be summarized and discussed in the upcoming paragraph.
A mathematical model regarding objective functions and constraints in the scheduling model is presented. The scheduling provides the required service resources to perform some processes on the subtasks [8]. Scheduling mathematical models are advisable to define objective functions and optimize them. There are four main objective function Time (T), Cost (C), Quality (Q) and Utilization (U). Considering the objective function and constraints, the mathematical model is presented [24] by Eq. (1) in which \({a}_{1},{a}_{2},{a}_{3},{a}_{4}\) are the weight values of the objective functions and \({x}_{ij}\) is decision variable.
Quality is an important component in efficient scheduling and plays a key role in the cloud-based environment. Evidence suggests that the number of resources in the cloud manufacturing system is among the most important factors that can exert influence on the efficient scheduling since, increasing the number of machines helps the system to improve the QoS and on the other hand, it brings about the higher cost. As mentioned in the introduction, heavy traffic limit as a new approach regarding quality of service (QoS) classes is proposed to obtain the number of operational machines in a cloud-based scheduling.
3 Methodology
As mentioned above, a cloud manufacturing system with many resources is considered a queue system. To satisfy the QoS requirements and optimize the cost at the same time, the performance of the queue system based on the different QoS requirements is investigated. In order to achieve this aim, scheduling in cloud manufacturing systems has been classified based QoS requirements in which waiting time has a pivotal impact, and then each class is analysed using the heavy traffic limit theory.
3.1 Heavy Traffic Limit Theory in Different Classified QoS
Based on wating time, four different QoS is considered [12]. This system of classification is more scientific since it is based on the QoS requirements demanded by the customers.
-
1-
Zero-Waiting-Time (ZWT): it provides the strictest of the QoS requirements in which the waiting time is zero and the tasks must be accomplished immediately when they arrive. Function P represents QoS requirements in (2).
$$\underset{\mathrm{n}\to \mathrm{ \infty }}{\mathrm{lim}}P\left\{N\ge n\right\}=0$$(2)where N is the total number of tasks in cloud and n is the number of operational machines.
-
2-
Minimal-Waiting-Time (MWT): in this class, waiting time is near to zero and when the jobs arrive at the system, they are served with some probability.
$$\underset{\mathrm{n}\to \mathrm{ \infty }}{\mathrm{lim}}P\left\{N\ge n\right\}=\alpha$$(3)In Eq. 3, \(\alpha\) represents a constant that \(0<\alpha <1\)
-
3-
Bounded-Waiting-Time (BWT): in this case, waiting time is between 0 and \({t}_{1}\) and when the number of machines goes to infinity the probability is 1.
$$\mathop {\lim }\limits_{{\text{n}} \to { }\infty } P\left\{ {N \ge n} \right\} = 1,\mathop {\lim }\limits_{{\text{n}} \to { }\infty } P\left\{ {W \ge t_1 } \right\} = \sigma_n , \mathop {\lim }\limits_{{\text{n}} \to { }\infty } \sigma_n = 0$$(4)where W, \({t}_{1}\), and \({\sigma }_{n}\) are waiting time, waiting time threshold, and decreasing rate, respectively.
-
4-
Probabilistic-Waiting-Time (PWT): this class is the least strict QoS, waiting time is between 0 and \({t}_{2}\) with probability \(1-\sigma\) where \(\sigma\) is constant and \(0<\sigma <1\).
$$\mathop {\lim }\limits_{{\text{n}} \to { }\infty } P\left\{ {N \ge n} \right\} = 1,\,\, \mathop{\lim }\limits_{{\text{n}} \to { }\infty } P\left\{ {W \ge t_2 } \right\} = \sigma$$(5)The analysis of the QoS classes is based on the conceptual framework proposed by [25] in a queue system with numerous servers. As discussed above, the traffic intensity must be less than 1 so that the cloud system becomes stable, and it is close to 1 when the number of machines is infinite. In this investigation, the heavy traffic limit for the various QoS classes is developed based on proposition 1 and theorem 4 analysed in [25].
For the class 1 (ZWT) Eq. (6) is true.
If f(n) is defined as \(\left(1-{\rho }_{n}\right)\) in that \({\rho }_{n}\) is traffic intensity then,
In Class 2 (MWT) the QoS is satisfied if:
\(\beta\), c are constant value and coefficient of variance.
For class 3 (BWT), the QoS meets the requirements if a suitable \({\sigma }_{n}\) is used in it under equations given in (9):
where \(\tau\) is \(\tau = \frac{1+{c}^{2}}{2\mu {t}_{1}}\) in that \(\mu\) is mean service time. k is constant and \(k>0\)
In the class 4 (PWT), QoS is satisfied if
\(\gamma\) is the probability of threshold that is represented by \(\gamma =\frac{-(1+{c}^{2})\mathrm{ln}\sigma }{2\mu {t}_{2}}\).
The results of equations provide guidelines that show how many machines should be active to meet the QoS requirements in the cloud environment. To do this, the next section develops a queuing system in which different QoS classes under heavy traffic limit terms are brought up.
4 Modelling of Queuing Process Based on Cloud Classification
The cloud-based system consists of a wide variety of machines to accomplish tasks and subtasks; therefore, it can be viewed in a queuing system. Moreover, a queuing system is in heavy traffic regime when the traffic intensity ρ is less than one in that traffic intensity is defined as the rate of job arrivals divided by the rate of served tasks [12]. In this model, it is assumed that job arrivals are independent, and the passion arrival process is considered. In addition, service time is exponentially distributed in which arrival rate and variation coefficient and mean denote λn, c, and 1/µ. Each task is completed by only one machine based on First-Come-First-Serve (FCFS) rule and resources have fully similar capability.
4.1 Number of Operational Resources in the Queuing System
In order to satisfy the QoS requirements of clients and reach the optimal performance in the cloud environment, different heavy limits are applied for different QoS classes. Based on the analysis, the minimum number of machines is computed for each QoS class in which the traffic intensity is estimated by mathematical methods. As mentioned above, an exponential service time distribution is chosen in the cloud model (µ = 0.3) and variation coefficient (c = 1) is presumed [26]. The number of machines is obtained to have efficient scheduling in the cloud environment. When traffic intensity is close to one and the number of machines is large, the heavy traffic limit is an appropriate methodology. Based on the heavy traffic limit, the number of machines in each class is provided. Table 1 shows the number of machines in each QoS class with estimated traffic intensity.
The unknown parameters in aforementioned equations are computed for each class [26]. For class 1 (ZWT), \(f\left(n\right)= {n}^{-x}\) where x = 0.25. In class 2 (MWT), the waiting probability is f(α) = 0.01 and c = 1, therefore form Eq. (8), we have \(\beta =0.005\). In class 3 (BWT) class, t1 = 1 and \({\sigma }_{n}=\mathrm{exp}(-{n}^{0.25}\)). Finally, in the class 4 (PWT), the probability of threshold (\(\gamma )\) is 0.2 and t2 = 1 is considered. According to the assumptions mentioned above, a relationship between the number of operational machines and traffic intensity in each Cloud-based class is obtained.
5 Results and Discussion
Based on a cloud scheduling, heavy traffic limit in the queueing system is designed for formulating and solving the scheduling model based on Eqs. (2)–(11). To achieve this purpose, the aforementioned example is developed to find the unknown parameters. Based on the mathematical formulas mentioned in Table 1 for each class and assumptions indicated above, the relationship between the number of machines and traffic intensity in each QoS class for the cloud-based scheduling is illustrated in Fig. 2. It indicates that the number of machines in each specific traffic intensity (0 < ρ < 1) is fully dependent on the different QoS classes.
The results illustrate that in the designed cloud model, there is an intersection between MWT and PWT classes in ρ = 0.6. With a given value of traffic intensity, ZWT and BWT classes need the most and least number of machines, respectively. Before ρ = 0.6, MWT class meets the QoS requirements in the model with less resources compared with PWT. Table 2 shows the number of machines for different traffic intensity in each QoS requirement class. It demonstrates that in the same condition, Bounded Waiting Time (BWT) class has the best performance. As mentioned above, there is a significant correlation between QoS and cost in the cloud manufacturing system, therefore, this class meets the QoS requirements with the least machine and cost in the cloud system.
No significant difference between the MWT and PWT classes is evident when traffic intensity is equal and less than 0.6 however for traffic intensity more than 0.6, PWT is a more appropriate class in terms of satisfying QoS requirements and saving cost.
6 Conclusion
Cloud manufacturing is a novel paradigm of using centralized cloud for manufacturing systems to distribute resources in an on-demand business model in which the role of resource scheduling has received increased attention across a number of research in recent years. The aim of this paper is to describe the design and implementation of heavy traffic limits based on QoS requirements for the resource scheduling in the cloud-based manufacturing system in that the cloud system is considered as a queuing system. Different heavy traffic limits as new approaches are attained based on four QoS classes to find the optimal number of operational machines for each class. The results, as shown in Fig. 2, indicate that there is a significant positive correlation between the number of active machines in each class and the traffic intensity. The higher the traffic intensity becomes; the greater number of operational machines are needed to meet QoS requirements desired by customers. The analysis of each class demonstrates that the Bounded Waiting Time (BWT) class has the best performance in that both saving cost and satisfying QoS requirements arise simultaneously. As represented in Table 2, ρ = 0.6 is a turning point for MWT and PWT classes; however, PWT is a better class in terms of both satisfaction and cost. Results of the study provide insights for future research. Investigation of optimization algorithms and machine learning methods based on big data techniques are possible areas to analyse and optimize scheduling problems in cloud manufacturing environments.
References
Yang, C., Peng, T., Lan, S., Shen, W., Wang, L.: Towards IoT-enabled dynamic service optimal selection in multiple manufacturing clouds. J. Manuf. Syst. 56, 213–226 (2020)
Bouzary, H., Chen, F.F., Shahin, M.: Natural language processing for comprehensive service composition in cloud manufacturing systems. Procedia Manuf. 55, 343–349 (2021). https://doi.org/10.1016/j.promfg.2021.10.048
Rashidifar, R., Khataei, M., Poursina, M., Ebrahimi, N.: Comparison and evaluation of criteria ductile damage FLD & MSFLD to predict crack growth in forming processes (2014)
Li, F., Zhang, L., Liao, T.W., Liu, Y.: Multi-objective optimisation of multi-task scheduling in cloud manufacturing. Int. J. Prod. Res. 57(12), 3847–3863 (2019). https://doi.org/10.1080/00207543.2018.1538579
Tong, H., Zhu, J.: A novel method for customer-oriented scheduling with available manufacturing time windows in cloud manufacturing. Robot. Comput. Integr. Manuf. 75, 102303 (2022)
Wu, Q., Xie, N., Zheng, S., Bernard, A.: Online order scheduling of multi 3D printing tasks based on the additive manufacturing cloud platform. J. Manuf. Syst. 63, 23–34 (2022)
Mourtzis, D., Vlachou, E.: A cloud-based cyber-physical system for adaptive shop-floor scheduling and condition-based maintenance. J. Manuf. Syst. 47, 179–198 (2018)
Delaram, J., Valilai, O.F.: A mathematical model for task scheduling in cloud manufacturing systems focusing on global logistics. Procedia Manuf. 17, 387–394 (2018)
Liu, Y., Xu, X., Zhang, L., Wang, L., Zhong, R.Y.: Workload-based multi-task scheduling in cloud manufacturing. Robot. Comput. Integr. Manuf. 45, 3–20 (2017)
Jian, C., Ping, J., Zhang, M.: A cloud edge-based two-level hybrid scheduling learning model in cloud manufacturing. Int. J. Prod. Res. 59(16), 4836–4850 (2021)
Bittencourt, L.F., Goldman, A., Madeira, E.R., da Fonseca, N.L., Sakellariou, R.: Scheduling in distributed systems: a cloud computing perspective. Comput. Sci. Rev. 30, 31–54 (2018)
Zheng, Y., Shroff, N., Sinha, P.: Heavy traffic limits for GI/H/n queues: theory and application. ArXiv Prepr. ArXiv14093463 (2014)
Kingman, J.F.C.: Queue disciplines in heavy traffic. Math. Oper. Res. 7(2), 262–271 (1982)
Hurtado Lange, D.A., Maguluri, S.T.: Heavy-traffic analysis of queueing systems with no complete resource pooling. Math. Oper. Res. (2022)
Kimura, T., Masuyama, H.: A heavy-traffic-limit formula for the moments of the stationary distribution in GI/G/1-type Markov chains. Oper. Res. Lett. 49(6), 862–867 (2021)
Maguluri, S.T., Srikant, R., Ying, L.: Heavy traffic optimal resource allocation algorithms for cloud computing clusters. Perform. Eval. 81, 20–39 (2014)
Sun, X.: Heavy-traffic limits for server idle times with customary server-assignment rules. Oper. Res. Lett. 46(1), 44–50 (2018)
Uysal, E.: An overview of the application of heavy traffic theory and Brownian approximations to the control of multiclass queuing networks
Hurtado-Lange, D., Maguluri, S.T.: Transform methods for heavy-traffic analysis. Stoch. Syst. 10(4), 275–309 (2020)
Scully, Z., Grosof, I., Harchol-Balter, M.: Optimal multiserver scheduling with unknown job sizes in heavy traffic. Perform. Eval. 145, 102150 (2021)
Atar, R., Karmakar, P., Lipshutz, D.: Customer-server population dynamics in heavy traffic. Stoch. Syst. 12(1), 68–91 (2022)
Pinedo, M., Hadavi, K.: Scheduling: theory, algorithms and systems development. In: Gaul, W., Bachem, A., Habenicht, W., Runge, W., Stahl, W.W. (eds.) Operations Research Proceedings 1991. Operations Research Proceedings 1991, vol. 1991, pp. 35–42. Springer, Heidelberg (1992). https://doi.org/10.1007/978-3-642-46773-8_5
Liu, Y., Wang, L., Wang, X.V., Xu, X., Zhang, L.: Scheduling in cloud manufacturing: state-of-the-art and research challenges. Int. J. Prod. Res. 57(15–16), 4854–4879 (2019)
Yuan, M., Cai, X., Zhou, Z., Sun, C., Gu, W., Huang, J.: Dynamic service resources scheduling method in cloud manufacturing environment. Int. J. Prod. Res. 59(2), 542–559 (2021). https://doi.org/10.1080/00207543.2019.1697000
Halfin, S., Whitt, W.: Heavy-traffic limits for queues with many exponential servers. Oper. Res. 29(3), 567–588 (1981). https://doi.org/10.1287/opre.29.3.567
Zheng, Y., Shroff, N., Sinha, P., Tan, J.: Design of a power efficient cloud computing environment: heavy traffic limits and QoS, preprint (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2023 The Author(s)
About this paper
Cite this paper
Rashidifar, R., Chen, F.F., Bouzary, H., Shahin, M. (2023). A Mathematical Model for Cloud-Based Scheduling Using Heavy Traffic Limit Theorem in Queuing Process. In: Kim, KY., Monplaisir, L., Rickli, J. (eds) Flexible Automation and Intelligent Manufacturing: The Human-Data-Technology Nexus . FAIM 2022. Lecture Notes in Mechanical Engineering. Springer, Cham. https://doi.org/10.1007/978-3-031-18326-3_20
Download citation
DOI: https://doi.org/10.1007/978-3-031-18326-3_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-18325-6
Online ISBN: 978-3-031-18326-3
eBook Packages: EngineeringEngineering (R0)