Framework: Knowledge framework

Novel dual discounting functions for the Internet shopping optimization problem: new algorithms
One of the very important topics in discrete optimization, motivated by practical applications, is Internet shopping, which is becoming increasingly popular each year. More classical versions of the Internet shopping optimization problem (ISOP) are closely related to the facility location problem and some scheduling problems and have been intensively studied in the literature. In this paper, extensions of the problem are defined and studied. The issue is to buy all the necessary products for a minimum total possible price. This includes all prices of products as well as shipping costs. Studies in this paper include the ISOP with price sensitive discounts and a newly defined optimization problem: the ISOP including two different discounting functions, namely a shipping cost function as well as a price discounting function. First, these are formulated as mathematical programming problems. Then, some algorithms are constructed and extensively tested in a computational experiment.
Exact and heuristic approaches to solve the Internet shopping optimization problem with delivery costs
Internet shopping has been one of the most common online activities, carried out by millions of users every day. As the number of available offers grows, the difficulty in getting the best one among all the shops increases as well. In this paper we propose an integer linear programming (ILP) model and two heuristic solutions, the MinMin algorithm and the cellular processing algorithm, to tackle the Internet shopping optimization problem with delivery costs. The obtained results improve those achieved by the state-of-the-art heuristics, and for small real case scenarios ILP delivers exact solutions in a reasonable amount of time.
Algorithms solving the Internet shopping optimization problem with price discounts
The Internet shopping optimization problem arises when a customer aims to purchase a list of goods from a set of web-stores with a minimum total cost. This problem is NP-hard in the strong sense. We are interested in solving the Internet shopping optimization problem with additional delivery costs associated to the web-stores where the goods are bought. It is of interest to extend the model including price discounts of goods. The aim of this paper is to present a set of optimization algorithms to solve the problem. Our purpose is to find a compromise solution between computational time and results close to the optimum value. The performance of the set of algorithms is evaluated through simulations using real world data collected from 32 web-stores. The quality of the results provided by the set of algorithms is compared to the optimal solutions for small-size instances of the problem. The optimization algorithms are also evaluated regarding scalability when the size of the instances increases. The set of results revealed that the algorithms are able to compute good quality solutions close to the optimum in a reasonable time with very good scalability demonstrating their practicability.
Virtual Desktop Infrastructures: architecture, survey and green aspects proof of concept
Virtual Desktop Infrastructure (VDI) is a new generation of cloud service in which users operating systems execute in a cloud data center. Users can access their desktops and applications by using thin client devices. This thin client is consisting of only a screen attached with low power CPU. This new paradigm of delivering remote desktop provides benefits in terms of flexibility, cost reduction, data security and energy saving which are the green benefits from using VDI. VDI becomes an important technology in green computing and energy saving. In this paper, we present and review the green benefits for using VDI in large and small organizations. The usefulness and energy-saving features of VDI are also illustrated by some experiments.
On Service Level Agreement Assurance in Cloud Computing Data Centers
Cloud computing uses internet data centers to host applications and data storage. Cloud computing resources and services are offered to customers on pay-per-use model while the quality of the offered resources and services are defined using service level agreements also known as SLAs. Unfortunately, there is no standard mechanism to verify and assure that services delivered by the cloud provider satisfy the SLA agreement in an automatic way. To fill this gap we propose a framework for SLA assurance, which can be used by both cloud providers and cloud users. The proposed framework assesses performance of cloud applications with and without introducing system and component failures and then helps to resolve or mitigate failures to assure the required quality of cloud applications. The evaluation results obtained through simulations and using testbed experiments demonstrate good agreement with the design objectives.
Minimum Dependencies Energy-Efficient Scheduling in Data Centers
This work presents an on-line, energy- and communication-aware scheduling strategy for SaaS applications in data centers. The applications are composed of various services and represented as workflows. Each workflow consists of tasks related to each other by precedence constraints and represented by Directed Acyclic Graphs (DAGs). The proposed scheduling strategy combines advantages of state-of-the-art workflow scheduling strategies with energy-aware independent task scheduling approaches. The process of scheduling consists of two phases. In the first phase, virtual deadlines of individual tasks are set in the central scheduler. These deadlines are determined using a novel strategy that favors tasks which are less dependent on other tasks. During the second phase, tasks are dynamically assigned to computing servers based on the current load of network links and servers in a data center. The proposed approach, called Minimum Dependencies Energy-efficient DAG (MinD+ED) scheduling, has been implemented in the GreenCloud simulator. It outperforms other approaches in terms of energy efficiency, while keeping a satisfiable level of tardiness.
Cloud Brokering: Current Practices and Upcoming Challenges
The booming cloud computing industry offers a plethora of services. Navigation through these services is a long and perilous process. Cloud brokers can help in this journey, offering a more comprehensible view to the cloud service customers and service orchestration opportunities. From the service provider perspective, brokers facilitate reaching customers. In this invited article, the authors present a broad overview of cloud brokering. The article starts with a description of cloud brokers, the related taxonomy, their place in the business environment, and the legal framework. It briefly summarizes existing broker offers and cloud brokering research topics and discusses future challenges of cloud brokering.
A Survey of Evolutionary Computation for Resource Management of Processing in Cloud Computing
Cloud computing is significantly reshaping the computing industry. Individuals and small organizations can benefit from using state-of-the-art services and infrastructure, while large companies are attracted by the flexibility and the speed with which they can obtain the services. Service providers compete to offer the most attractive conditions at the lowest prices. However, the environmental impact and legal aspects of cloud solutions pose additional challenges. Indeed, the new cloud-related techniques for resource virtualization and sharing and the corresponding service level agreements call for new optimization models and solutions. It is important for computational intelligence researchers to understand the novelties introduced by cloud computing. The current survey highlights and classifies key research questions, the current state of the art, and open problems.
Scheduling on Parallel Identical Machines with Late Work Criterion. Offline and Online Cases
In the paper, we consider the problem of scheduling jobs on parallel identical machines with the late work criterion and a common due date, both offline and online cases. Since the late work criterion has not been studied in the online mode so far, the analysis of the online problem is preceded by the analysis of the offline problem, whose complexity status has not been formally stated in the literature yet. Namely, for the offline mode, we prove that the two-machine problem is binary NP-hard, and the general case is unary NP-hard. In the online mode we assume that jobs arrive in the system one by one, i.e., we consider the online over list model. We give an algorithm with a competitive ratio being a function of the number of machines, and we prove the optimality of this approach for two identical machines.
Time and Energy Performance of Parallel Systems with Hierarchical Memory
In this paper we analyze the impact of memory hierarchies on time-energy trade-off in parallel computations. Contemporary computing systems have deep memory hierarchies with significantly different speeds and power consumptions. This results in nonlinear phenomena in the processing time and energy usage emerging when the size of the computation is growing. In this paper the nonlinear dependence of the time and energy on the size of the solved problem is formalized and verified using measurements in practical computer systems. Then it is applied to formulate a problem of minimum time and minimum energy scheduling parallel processing of divisible loads. Divisible load theory is a scheduling and performance model of data-parallel applications. Mathematical programming is exploited to solve the scheduling problem. A trade-off between energy and schedule length is analyzed and again nonlinear relationships between these two criteria are observed. Further performance analysis reveals that energy consumption and schedule length are ruled by a complex interplay between the costs and speeds of on-core and out-of-core computations, communication delays, and activating new machines.
Analysis and Solution of CSS-Sprite Packing Problem
A CSS-sprite packing problem is considered in this article. CSS-sprite is a technique of combining many pictures of a web page into one image for the purpose of reducing network transfer time. The CSS-sprite packing problem is formulated here as an optimization challenge. The significance of geometric packing, image compression and communication performance is discussed. A mathematical model for constructing multiple sprites and optimization of load time is proposed. The impact of PNG-sprite aspect ratio on file size is studied experimentally. Benchmarking of real user web browsers communication performance covers latency, bandwidth, number of concurrent channels as well as speedup from parallel download. Existing software for building CSS-sprites is reviewed. A novel method, called Spritepack, is proposed and evaluated. Spritepack outperforms current software.
Budgeted Internet Shopping Optimization Problem (B-ISOP)
Internet changed a lot in the way we are shopping. The abundance of online shops not only improved the competition for the lowest prices, but also made sales of many niche products possible. A new way how such comparators could work is Internet Shopping Optimization Problem (ISOP). The idea is that instead of comparing prices of single products, user creates a list of the items he wants to buy, and algorithm using database chooses for him the cheapest solution, considering both prices of items in numerous shops, but also delivery costs. This paper relies on ISOP, however a somehow reversed version of the problem is considered. The customer still has a list of products he wants to buy, but is limited with a budget, i.e. an amount of money he can spend in total, including costs of products and delivery costs. With that, the customer will not be able to buy all of the items, but wants to maximize the total perceived value of products he will get. This perceived value can represent one of the following concepts: user preferences or priorities, ratings of the products, basic monetary value of the products, etc...
HEROS: Energy-Efficient Load Balancing for Heterogeneous Data Centers
Heterogeneous architectures have become more popular and widespread in the recent years with the growing popularity of general-purpose processing on graphics processing units, low-power systems on a chip, multi- and many-core architectures, asymmetric cores, coprocessors, and solid-state drives. The design and management of cloud computing data-centers must adapt to these changes while targeting objectives of improving system performance, energy efficiency and reliability. This paper presents HEROS, a novel load balancing algorithm for energy-efficient resource allocation in heterogeneous systems. HEROS takes into account the heterogeneity of a system during the decision-making process and uses a holistic representation of the system. As a result, servers that contain resources of multiple types (computing, memory, storage and networking) and have varying internal structures of their components can be utilized more efficiently.
Metaheuristics for the Virtual Machine Mapping Problem in Cloud
This article presents sequential and parallel metaheuristics to solve the virtual machines subletting problem in cloud systems, which deals with allocating virtual machine requests into pre-booked resources from a cloud broker, maximizing the broker profit. Three metaheuristic are studied: Simulated Annealing, Genetic Algorithm, and hybrid Evolutionary Algorithm. The experimental evaluation over instances accounting for workloads and scenarios using real data from cloud providers, indicates that the parallel hybrid Evolutionary Algorithm is the best method to solve the problem, computing solutions with up to 368.9% profit improvement over greedy heuristics results while accounting for accurate makespan and flowtime values.
Efficient Heuristics for Profit Optimization of Virtual Cloud Brokers
This article introduces a new kind of broker for cloud computing, whose business relies on outsourcing virtual machines (VMs) to its customers. More specifically, the broker owns a number of reserved instances of different VMs from several cloud providers and offers them to its customers in an on-demand basis, at cheaper prices than those of the cloud providers. The essence of the business resides in the large difference in price between on-demand and reserved VMs. We define the Virtual Machine Planning Problem, an optimization problem to maximize the profit of the broker. We also propose a number of efficient smart heuristics (seven two-phase list scheduling heuristics and a reordering local search) to allocate a set of VM requests from customers into the available pre-booked ones, that maximize the broker earnings. We perform experimental evaluation to analyze the profit and quality of service metrics for the resulting planning, including a set of 400 problem instances that account for realistic workloads and scenarios using real data from cloud providers.
Erratum to: Internet shopping with price-sensitive discounts
In Blazewicz et al. (4OR-Q J Oper Res 12(1):35–48, 2014), an Internet shopping problem with price-sensitive discounts was introduced, in which a customer wants to buy a given set of products in a given set of Internet shops. This problem is an extension of the original Internet shopping optimization problem (ISOP) presented in Blazewicz et al. (Int J Appl Math Comput Sci 20(2):385–390, 2010). For each Internet shop, standard prices for the products are given as well as a concave increasing discounting function of the total standard and delivery price. The problem is to buy all the required products at the minimum total discounted price. Among other results, approximability issues were shortly discussed. This note extends this discussion and corrects a flaw in Blazewich et al. (4OR-Q J Oper Res 12(1):35–48, 2014).
Novel dual discounting functions for Internet Shopping Optimization Problem: new algorithms
One of the very important topics in discrete optimization, motivated by practical applications, is Internet shopping, which is becoming increasingly popular each year. More classical versions of the Internet shopping optimization problem (ISOP) are closely related to the facility location problem and some scheduling problems and have been intensively studied in the literature. In this paper, extensions of the problem are defined and studied. The issue is to buy all the necessary products for a minimum total possible price. This includes all prices of products as well as shipping costs. Studies in this paper include the ISOP with price sensitive discounts and a newly defined optimization problem: the ISOP including two different discounting functions, namely a shipping cost function as well as a price discounting function. First, these are formulated as mathematical programming problems. Then, some algorithms are constructed and extensively tested in a computational experiment.
How to Efficiently Solve Internet Shopping Optimization Problem with Price Sensitive Discounts?
In this paper we deal with the Internet Shopping Optimization Problem. An extended model that includes price sensitive discounts is considered. A set of algorithms to solve the Internet Shopping Optimization Problem with Price Sensitivity Discounts (ISOPwD) is introduced. The algorithms are designed to consider a different solution quality regarding computational time and results close to the optimum solution. Simulations based on real world data assess the new set of heuristics. The results of the proposed algorithms were compared with the optimal solutions, computed by a branch and bound algorithm. The scalability is evaluated by increasing the problem sizes. Computational experiments are performed and their results are carefully analyzed and discussed. The paper should be perceived as a work in progress - position paper.
Internet shopping with price sensitive discounts
Internet shopping has been one of the most common online activities, carried out by millions of users every day. As the number of available offers grows, the difficulty in getting the best one among all the shops increases as well. In this paper we propose an integer linear programming (ILP) model and two heuristic solutions, the MinMin algorithm and the cellular processing algorithm, to tackle the Internet shopping optimization problem with delivery costs. The obtained results improve those achieved by the state-of-the-art heuristics, and for small real case scenarios ILP delivers exact solutions in a reasonable amount of time.
Internet shopping optimization problem real
In this paper we deal with the Internet Shopping Optimization Problem. An extended model that includes price sensitive discounts is considered. A set of algorithms to solve the Internet Shopping Optimization Problem with Price Sensitivity Discounts (ISOPwD) is introduced. The algorithms are designed to consider a different solution quality regarding computational time and results close to the optimum solution. Simulations based on real world data assess the new set of heuristics. The results of the proposed algorithms were compared with the optimal solutions, computed by a branch and bound algorithm. The scalability is evaluated by increasing the problem sizes. Computational experiments are performed and their results are carefully analyzed and discussed. The paper should be perceived as a work in progress - position paper.
Towards optimal multi-item shopping basket management: Heuristic approach
Shopping as a social activity may be a source of pleasure even if the shopping is very expensive. However, in many real-life situations customers are interested to buy products at possibly low prices. A shopping paradigm based on price comparison may be applied for both: buying in traditional shops and internet shopping. Unfortunately, price comparison applications available nowadays are focused on supporting customers in single product selection. Because of computational complexity, there is no support for managing multiple-item shopping basket optimization. Problem of optimal realization of multiple-item customer basket in Internet shops was proved to be NP-hard in computational sense. In the paper we propose a heuristic approach to optimizing shopping basket and report results of computational experiment. An application based on proposed algorithm provides an instant support for a customer while he builds his basket of products to be purchased.
E-Commerce Evaluation–Multi-Item Internet Shopping. Optimization and Heuristic Algorithms
Report [11] states that 32% of EU customers make purchases in Internet stores. By 2013, almost half of Europeans are expected to make a purchase online, up from 21% in 2006. On-line shopping is one of key business activities offered over the Internet. However a high number of Internet shops makes it difficult for a customer to review manually all the available offers and select optimal outlets for shopping, especially if a customer wants to buy more than one product. A partial solution of this problem has been supported by software agents so-called price comparison sites. Unfortunately price comparison works only on a single product and if the customer’s basket is composed of several products complete shopping list optimization needs to be done manually. Our present work is to define the problem (multiple-item shopping list over several shopping locations) in a formal way. The objective is to have all the shopping done at the minimum total expense. One should notice that dividing the original shopping list into several sub lists whose items will be delivered by different providers increases delivery costs. In the following sections a formal definition of the problem is given. Moreover a prove that problem is NP-hard in the strong sense was provided. It is also proven that it is not approx-imable in polynomial time. In the following section we demonstrate that shopping multiple items problem is solvable in polynomial time if the number of products to buy, n, or the number of shops, m, is a given constant.
A customer assistance system: Optimizing basket cost
A strong advantage of buying products in on-line shops is a wide choice of alternatives. From customers' point of view it is good to know where to go in order to buy all required products - the entire shopping list - at the best possible price. Making such decisions requires three elements: information where the required products are available, access to price lists in considered shops, and finally, specialized analytical tool that could find the minimal subset of shops where all the products from the customers' shopping list could be bought at the lowest price. In the paper we propose the mini-mini algorithm and describe a web-based customer assistance system dedicated to pharmacy shopping that helps customers find shops in a geographically defined range where the entire shopping list could be realized at the best price total. The same algorithms might be applied to other applications optimizing Internet shopping where the cost of basket delivery is negligible when compared to product prices.