A Comprehensive Utility Function for Resource Allocation in Mobile Edge Computing

In mobile edge computing (MEC), one of the important challenges is how much resources of which mobile edge server (MES) should be allocated to which user equipment (UE). The existing resource allocation schemes only consider CPU as the requested resource and assume utility for MESs as either a random variable or dependent on the requested CPU only. This paper presents a novel comprehensive utility function for resource allocation in MEC. The utility function considers the heterogeneous nature of applications that a UE offloads to MES. The proposed utility function considers all important parameters, including CPU, RAM, hard disk space, required time, and distance, to calculate a more realistic utility value for MESs. Moreover, we improve upon some general algorithms, used for resource allocation in MEC and cloud computing, by considering our proposed utility function. We name the improved versions of these resource allocation schemes as comprehensive resource allocation schemes. The UE requests are modeled to represent the amount of resources requested by the UE as well as the time for which the UE has requested these resources. The utility function depends upon the UE requests and the distance between UEs and MES, and serves as a realistic means of comparison between different types of UE requests. Choosing (or selecting) an optimal MES with the optimal amount of resources to be allocated to each UE request is a challenging task. We show that MES resource allocation is sub-optimal if CPU is the only resource considered. By taking into account the other resources, i.e., RAM, disk space, request time, and distance in the utility function, we demonstrate improvement in the resource allocation algorithms in terms of service rate, utility, and MES energy consumption.     

Working time constraints in operational fixed job scheduling

In this study we consider the operational fixed job scheduling problem under working time limitations. The problem has several practical implications in both production and service operations; however the relevant research is scarce. We analyse pre-emptive and non pre-emptive versions of the problem and its special cases. We provide polynomial-time algorithms for some special cases. We show that the non pre-emptive jobs problem is strongly NP-hard, and propose a branch-and-bound algorithm that employs efficient bounding procedures and dominance properties. We conduct a numerical experiment to observe the effects of parameters on the quality of the solution. The results of our computational tests for the branch-and-bound algorithm reveal that our algorithm can solve the instances with up to 100 jobs in reasonable times. To the best of our knowledge our branch-and-bound algorithm is the first optimisation attempt to solve the problem.     

Storage Decisions in Information Systems

The problem is to dynamically store different data records in different storage devices in each period so as to minimize the total expected discounted cost over a planning horizon. Each device has a fixed total capacity, each record has a given storage space requirement, while the number of requests for each record per period is changing stochastically through time. Given an allocation, the total cost per period consists of the storage cost (depending on the storage requirements and device), the access cost including update and retrieval costs (depending on the number of requests) and the transfer cost (depending upon the change of allocation from the previous period). A dynamic programming model is presented to yield optimal strategies. The special case of independent identically distributed demands is completely solved, using a generalized transportation algorithm while a heuristic procedure is indicated for the general problem using parametric analysis.     

Scheduling job shop associated with multiple routings with genetic and ant colony heuristics

The general job shop problem is one of the well known machine scheduling problems, in which the operation sequence of jobs are fixed that correspond to their optimal process plans and/or resource availability. Scheduling and sequencing problems, in general, are very difficult to solve to optimality and are well known as combinatorial optimisation problems. The existence of multiple job routings makes such problems more cumbersome and complicated. This paper addresses a job shop scheduling problem associated with multiple job routings, which belongs to the class of NP hard problems. To solve such NP-hard problems, metaheuristics have emerged as a promising alternative to the traditional mathematical approaches. Two metaheuristic approaches, a genetic algorithm and an ant colony algorithm are proposed for the optimal allocation of operations to the machines for minimum makespan time criterion. ILOG Solver, a scheduler package, is used to evaluate the performance of the proposed algorithms. The comparison reveals that both the algorithms are capable of providing solutions better than the solution obtained with ILOG Solver.     

Reliability optimization of series-parallel systems with a choice of redundancy strategies using a genetic algorithm

This paper proposes a genetic algorithm (GA) for a redundancy allocation problem for the series-parallel system when the redundancy strategy can be chosen for individual subsystems. Majority of the solution methods for the general redundancy allocation problems assume that the redundancy strategy for each subsystem is predetermined and fixed. In general, active redundancy has received more attention in the past. However, in practice both active and cold-standby redundancies may be used within a particular system design and the choice of the redundancy strategy becomes an additional decision variable. Thus, the problem is to select the best redundancy strategy, component, and redundancy level for each subsystem in order to maximize the system reliability under system-level constraints. This belongs to the NP-hard class of problems. Due to its complexity, it is so difficult to optimally solve such a problem by using traditional optimization tools. It is demonstrated in this paper that GA is an efficient method for solving this type of problems. Finally, computational results for a typical scenario are presented and the robustness of the proposed algorithm is discussed.     

Scheduling with non-decreasing deterioration jobs and variable maintenance activities on a single machine

There is a situation found in many manufacturing systems, such as steel rolling mills, fire fighting or single-server cycle-queues, where a job that is processed later consumes more time than that same job when processed earlier. The research finds that machine maintenance can improve the worsening of processing conditions. After maintenance activity, the machine will be restored. The maintenance duration is a positive and non-decreasing differentiable convex function of the total processing times of the jobs between maintenance activities. Motivated by this observation, the makespan and the total completion time minimization problems in the scheduling of jobs with non-decreasing rates of job processing time on a single machine are considered in this article. It is shown that both the makespan and the total completion time minimization problems are NP-hard in the strong sense when the number of maintenance activities is arbitrary, while the makespan minimization problem is NP-hard in the ordinary sense when the number of maintenance activities is fixed. If the deterioration rates of the jobs are identical and the maintenance duration is a linear function of the total processing times of the jobs between maintenance activities, then this article shows that the group balance principle is satisfied for the makespan minimization problem. Furthermore, two polynomial-time algorithms are presented for solving the makespan problem and the total completion time problem under identical deterioration rates, respectively.     

Integrated optimization of location assignment and sequencing in multi-shuttle automated storage and retrieval systems under modified 2n-command cycle pattern

This article explores the integrated optimization problem of location assignment and sequencing in multi-shuttle automated storage/retrieval systems under the modified 2n-command cycle pattern. The decision of storage and retrieval (S/R) location assignment and S/R request sequencing are jointly considered. An integer quadratic programming model is formulated to describe this integrated optimization problem. The optimal travel cycles for multi-shuttle S/R machines can be obtained to process S/R requests in the storage and retrieval request order lists by solving the model. The small-sized instances are optimally solved using CPLEX. For large-sized problems, two tabu search algorithms are proposed, in which the first come, first served and nearest neighbour are used to generate initial solutions. Various numerical experiments are conducted to examine the heuristics’ performance and the sensitivity of algorithm parameters. Furthermore, the experimental results are analysed from the viewpoint of practical application, and a parameter list for applying the proposed heuristics is recommended under different real-life scenarios.     

Unequal-area stochastic facility layout problems: solutions using improved covariance matrix adaptation evolution strategy,particle swarm optimisation,and genetic algorithm

Determining the locations of departments or machines in a shop floor is classified as a facility layout problem. This article studies unequal-area stochastic facility layout problems where the shapes of departments are fixed during the iteration of an algorithm and the product demands are stochastic with a known variance and expected value. These problems are non-deterministic polynomial-time hard and very complex, thus meta-heuristic algorithms and evolution strategies are needed to solve them. In this paper, an improved covariance matrix adaptation evolution strategy (CMA ES) was developed and its results were compared with those of two improved meta-heuristic algorithms (i.e. improved particle swarm optimisation [PSO] and genetic algorithm [GA]). In the three proposed algorithms, the swapping method and two local search techniques which altered the positions of departments were used to avoid local optima and to improve the quality of solutions for the problems. A real case and two problem instances were introduced to test the proposed algorithms. The results showed that the proposed CMA ES has found better layouts in contrast to the proposed PSO and GA.     

Request queueing for magnetic bubble memories

The improvements in request throughput that result from the use of the shortest seek time first (SSTF) request, scheduling algorithm for major/minor loop organized magnetic bubble memories are considered. For the satisfaction of read requests the bubble memory can be considered as equivalent to a file drum with fixed block size. Bubble memories are considered with 64 kbits per chip running at a 5.6 μs stepping rate and serving 750 to 830 read requests pet second (as opposed to ≤ 419 requests per second without queueing) with both uniform and Poisson arrival rates. A priority interrupt algorithm is implemented that assures that all requests are served in ≤ 60ms, while average service times are 10 to 20 ms. Results of simulation runs, corresponding to the various cases of interest, are presented. It is concluded that request queueing with the appropriate scheduling algorithm is a practical way of improving bubble memory performance.     

Non-linear game models for large-scale network bandwidth management

The design of dynamic Label-Switched Paths (LSP’s) in MultiProtocol Label Switched (MPLS) networks is an NP-hard optimization problem. An LSP is a logical path between two nodes in the network. This path has a pre-reserved amount of bandwidth that defines its size. The LSP design problem consists of determining the number of these logical links and configuring the physical path and the size of each LSP. This paper presents an optimization model based on game theory. In this approach, connection requests are modeled as competitive players in a noncooperative game context. The transport network bandwidth constitutes the resource for which optimization is sought. The outcome of this optimization is a set of LSPs upon which the competing connections are routed.     

WRLSP: A Single-Machine, Warehouse Restricted Lot Scheduling Problem

This paper treats a single-machine, multi-product scheduling problem arising from an application in an automobile factory. The problem is to sequence the production lots of N products in a common cycle schedule to minimize the maximum storage space required by the machine's output, given constant production and demand rates, sequence-independent setup times and sharing of the storage space among the products. As the problem is strongly NP-hard, a heuristic and a branch and bound algorithm are developed for solving it. The algorithms are assessed on a set of random test problems similar in size and complexity to the original application.     

Retrieval sequencing for unit-load automated storage and retrieval systems with multiple openings

Automated storage and retrieval systems (AS/RS) have made a dramatic impact on material handling and inventory control in warehouses and product systems. A unit-load AS/RS is generic and other AS/RS represent its variations. In this paper, we study a problem of sequencing retrieval requests in a unit-load AS/RS. In a unit-load AS/RS, there are usually multiple openings and a unit-load can be stored in any opening. Given a list of retrieval requests and the locations of openings, this problem seeks a sequence of dual cycles that minimizes total travel time taken by a storage/retrieval machine. Previous researchers believed that this problem is computationally intractable and provided greedy-style heuristic algorithms. In this paper, we present an algorithm that combines the Hungarian method and the ranking algorithm for the assignment problem with tour-checking and tour-breaking algorithms. We show that this algorithm finds either a verified optimal or near-optimal solution quickly for moderate size problems. Using this algorithm, we also evaluate the effectiveness of the existing simple heuristics. Computational results are reported.     

Reduction techniques for the PNS problems: a novel technique and a review

Process Network Synthesis (PNS) has an enormous practical impact. The problem is very difficult to solve, determining the cost optimal network of operating units with fixed charge belongs to the complexity class of NP-hard problems. Therefore, it is important to develop reduction algorithms to minimize the size of the problem. In the present work the available reduction techniques for PNS problems are reviewed as well as a further reduction algorithm is presented. The performance of the new algorithm is examined by empirical analysis.     

On sequencing policies for unit-load automated storage and retrieval systems

Automated Storage and Retrieval System (AS/RS) performance highly depends on the characteristics of the mechanical equipment. However, once the system has been physically implemented, achieving its maximum efficiency depends on the way the system is operated. This paper shows that request sequencing (i.e. planning the order in which storage and retrieval requests are performed) is of paramount importance in AS/RS performance. This paper reviews and adapts the most popular storage and sequencing policies to dynamic contexts, and then it proposes a ‘sequencing mathematical model’ (SMM) to simultaneously solve the sequencing and storage location problems. Extensive computational results based on a thorough simulation experiment plan confirm that performing the requests in the right sequence can have a positive impact on AS/RS performance. Our results show that the proposed SMM regularly outperforms other methods. When used in a dynamic context, the proposed SMM may yield up to a 25% reduction in average travel-time compared to the situation where a no-sequencing method is applied.     

Evaluation of a hybrid genetic tabu search framework on job shop scheduling benchmark problems

It has been well established that to find an optimal or near-optimal solution to job shop scheduling problems (JSSPs), which are NP-hard, one needs to harness different features of many techniques, such as genetic algorithms (GAs) and tabu search (TS). In this paper, we report usage of such a framework which exploits the diversified global search and the intensified local search capabilities of GA and TS, respectively. The system takes its input directly from the process information in contrast to having a problem-specific input format, making it versatile in dealing with different JSSP. This framework has been successfully implemented to solve industrial JSSPs. In this paper, we evaluate its suitability by applying it on a set of well-known job shop benchmark problems. The results have been variable. The system did find optimal solutions for moderately hard benchmark problems (40 out of 43 problems tested). This performance is similar to, and in some cases better than, comparable systems, which also establishes the versatility of the system. However for the harder benchmark problems it had difficulty in finding a new improved solution. We analyse the possible reasons for such a performance.     

Alternate video broadcasting scheme for popular videos

A video segment broadcasting scheme can reduce server and network bandwidth by periodically broadcasting popular videos that are most likely demanded by clients, instead of responding to each client requests. When video segments broadcast on a channel, in general, alternate broadcasting schemes periodically transmit all segments on a given channel with the same transmission period, which reduces the transmission efficiency of stream channels and requires sufficient client storage space for video segments broadcast on simultaneous channels. The author proposed a novel alternate video broadcast scheme, a delayed buffering broadcast that requires lower server bandwidth and client buffer space compared with those of previous approaches. In addition, the study provides an analytical analysis of the scheme, including a lower bound on the video segment transmission rate for any alternate broadcast scheme. It also derives an upper bound on its storage requirements from the client side. Using the performance study of the proposed scheme and simulation results, the author establishes that the proposed scheme uses fewer server channels and storage resources than previously reported alternate video broadcast schemes for any given client waiting time.     

Two-stage assembly flow-shop scheduling problem with non-identical assembly machines considering setup times

In this paper, we address the two stage assembly flow-shop problem with multiple non-identical assembly machines in stage two to minimise weighted sum of makespan and mean completion time. Also, sequence dependent setup times are considered for the first stage. This problem is a generalisation of previously proposed two stage assembly flow-shop problems (TSAFSP). In many real world industrial and production systems, there is more than one assembly machine to assemble job components. After extending a mathematical mixed-integer linear programming model to solve the problem, we use GAMS software. The TSAFSP has been known as NP-hard. Therefore, our more general problem is NP-hard too and so for large sized problems the right way to proceed is with the use of heuristic algorithms. So in this paper a hybrid VNS heuristic, which is a combination of the variable neighbourhood search (VNS) algorithm and a novel heuristic is developed and its solutions compared with solutions obtained by GAMS. Computational experiments reveal that the hybrid VNS heuristic performs much better than GAMS with respect to the percentage errors and run times.     

Machine Learning Based Resource Allocation of Cloud Computing in Auction

Resource allocation in auctions is a challenging problem for cloud computing. However, the resource allocation problem is NP-hard and cannot be solved in polynomial time. The existing studies mainly use approximate algorithms such as PTAS or heuristic algorithms to determine a feasible solution; however, these algorithms have the disadvantages of low computational efficiency or low allocate accuracy. In this paper, we use the classification of machine learning to model and analyze the multi-dimensional cloud resource allocation problem and propose two resource allocation prediction algorithms based on linear and logistic regressions. By learning a small-scale training set, the prediction model can guarantee that the social welfare, allocation accuracy, and resource utilization in the feasible solution are very close to those of the optimal allocation solution. The experimental results show that the proposed scheme has good effect on resource allocation in cloud computing.     

Batch scheduling in differentiation flow shops for makespan minimisation

This paper considers a two-stage three-machine differentiation flow shop that comprises a common machine at stage 1 and two independent dedicated machines at stage 2. Two types of jobs are to be processed. All jobs must visit the stage-1 machine, and then the jobs of each type proceed to their dedicated machine for stage-2 processing. The stage-1 machine processes the jobs in batches, each of which, whenever formed, requires a constant setup time. The objective is to find a schedule that attains the minimum makespan. While the problem is strongly NP-hard, we investigate the case where the processing sequences of the two types of jobs are given and fixed. A polynomial-time dynamic programming algorithm is designed to solve this problem. We then deploy this algorithm to compute the lower bounds of the general problem.     

Considerations of core storage arising from the finite element analysis of radiation diffusion-transport benchmark problems

Problems involving the diffusion and transport (angular dependence considered) of neutron radiation are frequently encountered in radiation physics and nuclear engineering. Neutron diffusion problems require substantial computer storage arising from the energy and spatial dependence, while in the case of transport problems the angular dependence of the neutron flux and of the neutron scattering process gives rise to a further considerable increase in storage. In the present work, a method has been developed which greatly eases the bandwidth problem in the solution of large systems of linear equations and algorithms have been developed to assemble and solve such systems of equations in one and two dimensions. The formalism used is the variational method and, for simplicity, linear interpolating functions have been used to derive a symmetric banded system of equations. Finite element algorithms have been implemented in the codes FEED1 and FEED2, which treat one and two space dimensions, respectively. Three benchmark problems are analysed in this paper and results are compared with finite difference discrete ordinate method solutions. It is shown that the finite element method provides fast and accurate solutions to neutron diffusion and transport problems.