Cloud computing is encountering a fast development in industrial and academical elds, providing on-demand services such as infrastructures and applications whether the resource type is physical or virtual. Data Center Networks (DCNs) architecture re ects directly on its scalability, fault-tolerance and more importantly on the Cloud workow. For that matter, server-centric data centers are facing a main issue regarding applications scheduling due to tra c forwarding that relies on servers imitating switches. The challenge is to choose an optimization method so that Cloud users constraints are satis ed. If the problem is of small size and reduced complexity, the implementation of an exact method may be su cient to determine an optimal solution. In the case of massive size problems, the approximate methods are the most e cient way to get as close as possible to the optimal solution. In this paper, we focused on the job-shop scheduling type problem, with Makespan minimization as a criterion. The problem is known NP-hard, we propose for its resolution the meta-heuristic "Harmony Search." After a phase of experimental determinations of the approach parameter values using the CloudSim which is a framework for simulation and modeling of cloud computing, a set of validation tests was carried out on the most known benchmarks. Overall, the results remain encouraging.
Since its rst launch, Cloud computing is proving an evolving resistance and
a scalability development over various elds in our practical life. This growth
made user access experience similar to any daily life needs like electricity or
water. Hence, numerous requests are continuously received. Therefore several
resource management policies were adopted to maintain an e cient performance
across application scheduling in DCNs. Cloud scheduling can be divided into
two categories. When all tasks are independent, it can be assigned to the
processors independently without any prede ned order of execution. In the case of
dependent scheduling (work ows), scheduling is very complicated [
A proper task scheduling creates a clear vision about resource availability and
helps de ne the objectives associated. Researchers still face complicated
optimization problems that are very di cult to solve. Over the past few years, Cloud
computing has adopted many operational research methods like meta-heuristics
methods, which are usually iterative stochastic algorithms that progress towards
a global optimum. Our work presents an adaptation of a recent meta-heuristic
called Harmony Search (HS) for the resolution of the job-shop scheduling in a
Cloud-based server-centric architecture. Indeed, this method, which was recently
developed by Geem [
Many previous studies inspected the consolidation of Cloud-based environment
issues with industrial manufacturing problems. However, just a few works were
dedicated to solve local tasks scheduling problems. Fathi and khanli [
Job-shop scheduling provides multiple advantages such as getting real-time feedback noti cations; it can operate di erent types of resource simultaneously and more importantly, it grants regrouping secondary objectives in one single objective, unlike the previously mentioned works which focus on developing a mechanism to solve one speci c constraint. All this has motivated us to implement HSA to reduce the makespan of Cloud application as our primary goal and eventually lowering processing requirements, energy consumption and resource utilization in DCNs by examining several job-shop benchmark problems in the literature. 3
Today's data centers (DCs) enters span widely in the eld of Cloud computing. In
server-centric architectures, servers are responsible for networking and routing,
whereas commodity switches without modi cation are used only for forwarding
packets [
A BCube topology relies on servers to take part in the tra c network, requiring
a high bandwidth to support intensive computing application. As shown in gure
1, the bene ts of BCube design is that it can provide fault tolerance and load
balancing and while requiring lower cooling and manufacturing cost [
A Dcell is a typical server-centric topology where we can nd a direct point to
point connectivity between servers as shown in gure 3, which requires a lot of
ports. This topology has Dcell0 as an essential element that includes a
miniswitch connected to n servers and provide excellent results in fault-tolerance
using its routing protocol [
Just like the optimization process to nd an optimal overall solution of an
objective function, the harmonization process relies on an orchestra playing a
combination of harmonies to nd the pleasant harmony determined by an aesthetic
standard. To achieve this, a set of musicians proceeds by successive
improvisations based on their experience. Each player sounds any pitch in the possible
range, following one of these three rules rstly, play a tone of his memory,
after that he plays a tone adjacent to the tone of his mind and nally, perform
a random tone in the set of possible sounds[
Standard HSA proceeds with the following steps: Start by initializing a set of parameters. Next step, improvise the HM to get a new harmony and then update it until some criteria are satis ed. We have added a randomization parameter to allow the selection of a random value in the range of possible values, to use it in a replacement that is applied in the evaluation step presented in Section 5, which allows the update of the memory to keep the best solutions and use them later. 4.2
The job-shop scheduling type is known in the literature as a very complicated combinatorial problem and very di cult to solve. On account of its industrial origins, Table 1 gives a projection of necessary elements from an industrial workshop to a Cloud environment. A piece takes the place of an application process running inside a virtual machine (VM) which is software running within a server to imitate the behavior of a physical machine and have multiple Cloudlets that use the VM capacity and store its id to run a le on it.
From the analogy mentioned above, we used HSA to solve that context due to its ability to deal with the immensity of data that can be found in JSP, in addition to that, HSA provides a simple concept regarding its model and a smooth implementation besides, it relies on few adjustable parameters to speed up the convergence process. 5
DCNs are at the heart of almost every private facility in Cloud computing, with a speci c architecture pre-installed. This work takes into consideration the issue of application scheduling in the Cloud and adopting a JSP as a study case, that is suitable with the server-centric architecture, focusing on the DCell topology, to optimize the Makespan using HS process illustrated in gure 4.
Improvisation is the most critical phase in the meta-heuristic HS because it allows the generation of a new harmony. It is based on the adjustment operator e ciency which we designed di erently compared to the basic algorithm in order to avoid the risk of having unrealistic harmonies, this second part from the HS procedure is based on three dependent parts. Firstly, we run through the benchmark le to create a random harmony of Cloudlets in a no-discount draw which will be in the end a vector of Cloudlets (i.e., an OS vector), then add this vector to vector of vectors, all this inside a loop. Part two consists of adjusting this last vector by using an adjustment method that randomly arranges the index of the rst Cloudlet in the vector OS, so that its new position takes the one of the rst box containing a null value. The last part of the improvisation will receive an adjusted vector of vectors as an input to collect the cloudlets in a speci c position from all the vectors and add it to a new nal OS vector. This vector will be considered as the ultimate scheduling harmony and to be evaluated for the best tness in afterward. 5.1
The current work has been implemented using the toolkit NetworkCloudSim [
In our contribution, dealing with job-shop scheduling problem which is monoobjective, the objective function respects a single criterion which is the Makespan. The evaluation step from the HS procedure ( g.4) appends an extra data processing to the basic procedure and therefore a tness function presented in Algorithm 1 was developed. It proceeds by reading some VMs (N VMs) from the benchmark le and then for each Cloudlet in the OS vector orderly, retrieve the a ected machine and the corresponding duration from the problem data le, after that assign the cloudlet at the end of the current VM respecting the precedence constraints. After completing the scheduling, calculate the tness of the solution and for that recovering the value of the Makespan. 5.2
In our study, we used benchmark samples ABZ, LA, FT, and ORB [
(a) ABZ5 benchmark(10x10) (b) ABZ benchmark Fig. 5: ABZ5 sample instance and ABZ comparison result
In order to determine the best set of parameters, several series of tests were performed on ve instances of the ABZ class (ABZ5, ABZ6, ABZ7, ABZ8, ABZ59), ve times each by combining di erent parameter values of HMCR and PAR with 300000 iterations. In what follows an explanation in detail on the set of tests carried out. The experiments were performed on an Intel i5-6200U CPU up to 2.8GHz with 4gb of Ram. Initially, a size of 100 of HM is more than enough according to the calculated tness. The best combination of HMCR and PAR parameters is decided after xing the PAR each time to a given value belonging to the following set of values: (0.1; 0.2; 0.01) and by varying the HMCR between (0.7; 0.8; 0.9). The best combination obtained is PAR = 0.01 and HMCR = 0.9. Final tests are required to validate our implementation results, by comparing our best-obtained tness from ABZ, LA, ORB instances to the knowing best solution (KBS) in the literature and also to Genetic Algorithm (GA). (a) ORB benchmark (b) LA benchmark
From the previous gures, we notice that our method gives on the majority of the benchmarks the same tness values found in the literature, and manages to exceed them, as in gure 6a with 40% of ORB instances that our HS approach Makespan was better than what was found. Same goes in gure 6b with 32.5% of LA instances and 40% of ABZ instances in gure 5b. 6
Despite the constant evolution of Cloud Computing, The optimal resolution of Job Shop type scheduling problems is in some cases impossible, owing that to their size and complexity of the problem are taken into account when choosing the optimization method. In summary, we have presented an approach based on HSA to schedule a set of applications with a DCell topology in a Cloud environment using NetCloudSim. The results obtained are mostly satisfactory and remain in their encouraging overall, compared to those found in the literature. In perspective, we plan to integrate meta-heuristics for local search to improve resources utilization and services performance in the Cloud and explore other types of scheduling issues such as exible job-shop, ow-shop, and hybrid ow-shop.