The optimal configuration and workload allocation problem in flexible manufacturing systems

In this article we consider the problem of determining the minimum cost configuration (number of machines and pallets) for a flexible manufacturing system with the constraint of meeting a prespecified throughput, while simultaneously allocating the total workload among the machines (or groups of machines). Our procedure allows consideration of upper and lower bounds on the workload at each machine group. These bounds arise as a consequence of precedence constraints among the various operations and/or limitations on the number or combinations of operations that can be assigned to a machine because of constraints on tool slots or the space required to store assembly components. Earlier work on problems of this nature assumes that the workload allocation is given. For the single-machine-type problem we develop an efficient implicit enumeration procedure that uses fathoming rules to eliminate dominated configurations, and we present computational results. We discuss how this procedure can be used as a building block in solving the problem with multiple machine types.     

An iterative approach to system setup problems in flexible manufacturing systems

System setup problems in flexible manufacturing systems deal with short-term planning problems such as part type selection, machine grouping, operation assignment, tooling, fixture and pallet allocation, and routing. In this article, we consider three of the subproblems: part type selection, machine grouping, and loading. We suggest a heuristic approach to solve the subproblems consistently with the objective of maximizing the expected production rate. The proposed procedure includes routines to generate all possible machine grouping alternatives for a given set of machines, to obtain optimal target workloads for each grouping alternative, and to allocate operations and tools to machine groups. These routines are executed iteratively until a good solution to the system setup problem is obtained. Computational experience is reported.     

A heuristic algorithm for the loading problem in flexible manufacturing systems

The paper considers the loading problem in flexible manufacturing systems (FMSs). This problem involves the assignment to the machine tools of all operations and associated cutting tools required for part types that have been selected to be produced simultaneously. The loading problem is first formulated as a linear mixed 0–1 program with the objective to minimize the greatest workload assigned to each machine. A heuristic procedure is presented in which an assignment of operations to machine tools is obtained by solving a parameterized generalized assignment problem with an objective function that approximates the use of tool slots required by the operations assigned to the machines. The algorithm is coded in FORTRAN and tested on an IBM-compatible personal computer. Computational results are presented for different test problems to demonstrate the efficiency and effectiveness of the suggested procedure.     

VRAA: virtualized resource auction and allocation based on incentive and penalty

Virtualization is widely used in cloud computing environments to efficiently manage resources, but it also raises several challenges. One of them is the fairness issue of resource allocation among virtual machines. Traditional virtualized resource allocation approaches distribute physical resources equally without taking into account the actual workload of each virtual machine and thus often leads to wasting. In this paper, we propose a virtualized resource auction and allocation model (VRAA) based on incentive and penalty to correct this wasting problem. In our approach, we use Nash equilibrium of cooperative games to fairly allocate resources among multiple virtual machines to maximize revenue of the system. To illustrate the effectiveness of the proposed approach, we then apply the basic laws of auction gaming to investigate how CPU allocation and contention can affect applications’ performance (i.e., response time), and its effect on CPU utilization. We find that in our VRAA model, the fairness index is high, and the resource allocation is closely proportional to the actual workloads of the virtual machines, so the wasting of resources is reduced. Experiment results show that our model is general, and can be applied to other virtualized non-CPU resources.     

Heuristics for the FMS-loading and part-type-selection problems

In this article, we study the FMS-loading and part-type-selection problems, in which each part is processed by a series of operations. Two heuristic methods are presented for the objectives of balancing workloads and meeting due dates. These heuristics perform a specific evaluation of the objective function at each iteration. The goal of Heuristic#1 is to achieve workload balance. The additional goal of Heuristic#2 is to reduce the number of late part types. The loading and part-type selection must satisfy a tooling constraint. Computational results are encouraging and indicate significant improvement over the existing methods.     

Pre-execution power consumption prediction of computational multithreaded workloads

Power management in large-scale computational environments can significantly benefit from predictive models. Such models provide information about the power consumption behavior of workloads prior to running them. Power consumption depends on the characteristics of both the machine and the workload. However, combinational features such as the cache miss rate cannot be considered due to their unavailability before running the workload. Therefore, pre-execution power modeling requires both machine-independent workload characteristics and workload-independent machine characteristics. In this paper the predictive modeling problem is tackled by the proposal of a two-stage modeling framework. In the first stage, a machine learning approach is taken to predict single-threaded workload power consumption at a specific frequency. The second stage analytically scales this output to any intended thread/frequency configuration. Experimental results show that the proposed approach can yield highly accurate predictions about workload power consumption with an average error of 3.7 % on six different test platforms.     

Minimizing total flow time on a single flexible machine

In this study, we address a job sequencing and tool switching problem arising in flexible manufacturing systems. We consider the single machine problem of minimizing total flow time. We prove that the problem is NP-hard in the strong sense and show that the tool switching problem is polynomially solvable for a given sequence. We propose a branch-and-bound algorithm whose efficiency is improved by precedence relations and several lower and upper bounding techniques. Our computational results reveal that the branch and bound approach produces optimal solutions in reasonable times for moderate sized problems. Our upper bounds produce very satisfactory solutions; therefore they can be an attractive alternative to solve larger sized problems.     

Scheduling data analytics work with performance guarantees: queuing and machine learning models in synergy

In today’s scaled out systems, co-scheduling data analytics work with high priority user workloads is common as it utilizes better the vast hardware availability. User workloads are dominated by periodic patterns, with alternating periods of high and low utilization, creating promising conditions to schedule data analytics work during low activity periods. To this end, we show the effectiveness of machine learning models in accurately predicting user workload intensities, essentially by suggesting the most opportune time to co-schedule data analytics work. Yet, machine learning models cannot predict the effects of performance interference when co-scheduling is employed, as this constitutes a “new” observation. Specifically, in tiered storage systems, their hierarchical design makes performance interference even more complex, thus accurate performance prediction is more challenging. Here, we quantify the unknown performance effects of workload co-scheduling by enhancing machine learning models with queuing theory ones to develop a hybrid approach that can accurately predict performance and guide scheduling decisions in a tiered storage system. Using traces from commercial systems we illustrate that queuing theory and machine learning models can be used in synergy to surpass their respective weaknesses and deliver robust co-scheduling solutions that achieve high performance.     

Planning the routing mix in FASs to minimize total transportation time

The routing mix problem in flexible assembly systems is considered. The problem consists of assigning the operations for each part to the machines, with the two objectives of balancing the machine workloads and minimizing the burden of the transportation system. These two objectives are sometimes conflicting, since the latter tends to support assigning operations to the same machine(s) as much as possible, and this may be bad for workload balancing. A linear programming problem is presented that, given a constraint on the workload of each machine, finds one solution that minimizes the overall time spent moving the parts from one machine to another. Since such a linear program may have an exponential number of variables, an efficient column generation technique to solve the problem is devised. The efficiency of the method is validated by experiments on a large number of random problems.     

Influence of Yo-Yo IR2 Scores on Internal and External Workloads and Fatigue Responses of Tag Football Players during Tournament Competition

The purpose of this study was to: a) identify changes in jump height and perceived well-being as indirect markers of fatigue, b) determine the internal and external workloads performed by players, and c) examine the influence of Yo-Yo IR2 on changes in jump height, perceived well-being and internal and external workloads during a tag football tournament. Microtechnology devices combined with heart rate (HR) chest straps provided external and internal measures of match work-rate and workload for twelve male tag football players during the 2014 Australian National Championships. Jump height and perceived well-being were assessed prior to and during the tournament as indirect measures of fatigue. Changes in work-rate, workload and fatigue measures between high- and low-fitness groups were examined based on players’ Yo-Yo IR2 score using a median split technique. The low- and high-fitness groups reported similar mean HR, Playerload^TM/min, and distance/min for matches, however the low-fitness group reported higher perceived match-intensities (ES = 0.90–1.35) for several matches. Further, the high-fitness group reported higher measures of tournament workload, including distance (ES = 0.71), Playerload^TM (ES = 0.85) and Edwards’ training impulse (TRIMP) (ES = 1.23) than the low-fitness group. High- and low-fitness groups both showed large decreases (ES = 1.46–1.49) in perceived well-being during the tournament, although jump height did not decrease below pre-tournament values. Increased Yo-Yo IR2 appears to offer a protective effect against player fatigue despite increased workloads during a tag football tournament. It is vital that training programs adequately prepare tag football players for tournament competition to maximise performance and minimise player fatigue.     

Performance and energy modeling for live migration of virtual machines

Live migration of virtual machine (VM) provides a significant benefit for virtual server mobility without disrupting service. It is widely used for system management in virtualized data centers. However, migration costs may vary significantly for different workloads due to the variety of VM configurations and workload characteristics. To take into account the migration overhead in migration decision-making, we investigate design methodologies to quantitatively predict the migration performance and energy consumption. We thoroughly analyze the key parameters that affect the migration cost from theory to practice. We construct application-oblivious models for the cost prediction by using learned knowledge about the workloads at the hypervisor (also called VMM) level. This should be the first kind of work to estimate VM live migration cost in terms of both performance and energy in a quantitative approach. We evaluate the models using five representative workloads on a Xen virtualized environment. Experimental results show that the refined model yields higher than 90% prediction accuracy in comparison with measured cost. Model-guided decisions can significantly reduce the migration cost by more than 72.9% at an energy saving of 73.6%.     

Service control with the preemptive parallel job scheduler Scojo-PECT

User satisfaction and scheduling on grids makes predictability of response times and quality-of-service highly desirable. However, existing approaches for response-time prediction still show significant prediction errors, mostly due to problems in dynamic arrival of jobs with potentially higher priority and hard-to-anticipate packing and backfilling effects. The same problems imply that quality-of-service cannot be solved with standard approaches from communication systems. Thus, this paper presents a scheduling approach which provides a more suitable framework for service guarantees and predictability. The approach is based on coarse-grain preemption, combined with an innovative separation of job classes. Resource shares can be determined as necessary to meet target service levels. A further extension permits limited dynamic resource allocation to adapt to variations in machine load and job mixes. The feasibility of service control is demonstrated with various workloads.     

Tool addition strategies for flexible manufacturing systems

The allocation of tools to machines determines potential part routes in flexible manufacturing systems. Given production requirements and a minimum feasible set of tools, the decision of how to fill vacant slots in tool magazines to maximize routing flexibility is shown to be a minimum cost network flow problem for the cases when routing flexibility is a function of the average workload per tool aggregated over tool types, or of the number of possible routes through the system. A linear programming model is then used to plan a set of routes for each part type so as to minimize either the material handling requirement or the maximum workload on any machine. The impact of these tool addition strategies on the material handling and workload equalization is investigated and computational results presented. The advantage of the overall approach is computational simplicity at each step and the ability to react to dynamic changes.     

Clustered Scheduling Algorithms for Mixed-Media Disk Workloads in a Multimedia Server

Divisible load scenarios occur in modern media server applications since most multimedia applications typically require access to continuous and discrete data. A high performance Continuous Media (CM) server greatly depends on the ability of its disk IO subsystem to serve both types of workloads efficiently. Disk scheduling algorithms for mixed media workloads, although they play a central role in this task, have been overlooked by related research efforts. These algorithms must satisfy several stringent performance goals, such as achieving low response time and ensuring fairness, for the discrete-data workload, while at the same time guaranteeing the uninterrupted delivery of continuous data, for the continuous-data workload. The focus of this paper is on disk scheduling algorithms for mixed media workloads in a multimedia information server. We propose novel algorithms, present a taxonomy of relevant algorithms, and study their performance through experimentation. Our results show that our algorithms offer drastic improvements in discrete request average response times, are fair, serve continuous requests without interruptions, and that the disk technology trends are such that the expected performance benefits can be even greater in the future.     

Sequencing of Parts in Robotic Cells

This paper considers scheduling problems in robotic cells that produce a set of part types on several machines served by one robot. We study the problem of sequencing parts of different types in a cell to minimize the production cycle time when the sequence of the robot moves is given. This problem is NP-hard for most of the one-unit robot move cycles in a robotic cell with more than two machines and producing more than two part types. We first give a mathematical formulation to the problem, and then propose a branch-and-bound algorithm to solve it. The bounding scheme of this algorithm is based on relaxing, for all of the machines except two, the constraints that a machine should be occupied by a part for a period at least as long as the processing time of the part. The lower bound obtained in this way is tight. This relaxation allows us to overcome the complexity of the problem. The lower bound can be computed using the algorithm of Gilmore and Gomory. Computational experiments on part sequencing problems in three-machine robotic cells are given.     

Comparison of three flow line layouts with unreliable machines and profit maximization

Manufacturing system design is a complex challenge when a new factory is being built. Although some factories produce the same product, the layouts of the factories may be different. Manufacturing systems for automotive engines can be modelled with several types of queueing networks with finite buffers and unreliable machines. In this paper, three types of layout structures which are commonly used in automotive engine shops are compared with respect to maximizing profit that is determined by throughput and the investment cost of buffers. We assume that the service times are constant but inhomogeneous, and the time to failure and the time to repair are exponentially distributed. To solve this problem we used approximation methods which are based on aggregation and overlapping decomposition for computing performance measures, and a gradient search method for finding an optimal buffer allocation.     

A fast GPU-based hybrid algorithm for addition chains

A graphics processing unit (GPU) has been widely used to accelerate discrete optimization problems. In this paper, we introduce a novel hybrid parallel algorithm to generate a shortest addition chain for a positive integer e. The main idea of the proposed algorithm is to divide the search tree into a sequence of three subtrees: top, middle, and bottom. The top subtree works using a branch and bound depth first strategy. The middle subtree works using a branch and bound breadth first strategy, while the bottom subtree works using a parallel (GPU) branch and bound depth first strategy. Our experimental results show that, compared to the fastest sequential algorithm for generating a shortest addition chain, we improve the generation by about 70% using one GPU (NVIDIA GeForce GTX 770). For generating all shortest addition chains, the percentage of the improvement is about 50%.     

A Genetic Algorithm Approach to the Scheduling of FMSs with Multiple Routes

Usually, most of the typical job shop scheduling approaches deal with the processing sequence of parts in a fixed routing condition. In this paper, we suggest a genetic algorithm (GA) to solve the job-sequencing problem for a production shop that is characterized by flexible routing and flexible machines. This means that all parts, of all part types, can be processed through alternative routings. Also, there can be several machines for each machine type. To solve these general scheduling problems, a genetic algorithm approach is proposed and the concepts of virtual and real operations are introduced. Chromosome coding and genetic operators of GAs are defined during the problem solving. A minimum weighted tardiness objective function is used to define code fitness, which is used for selecting species and producing a new generation of codes. Finally, several experimental results are given.     

The combinatorial distance geometry method for the calculation of molecular conformation. II. Sample problems and computational statistics

The performance of a branch and bound algorithm for molecular energy minimization is evaluated on a variety of test problems. Although not at present efficient enough for use in most practical situations, we show that it has distinct advantages over more conventional methods of global minimization. In addition, this study illustrates the technique on which the present algorithm is based, and the problems which must be overcome in developing an efficient algorithm based on similar principles.     

A truthful online mechanism for virtual machine provisioning and allocation in clouds

We address the problem of online virtual machine (VM) provisioning and allocation with multiple types of resources. Formulating this problem in an auction-based setting, we propose an accurate mathematical model incorporating the ability to preempt and resume a given task for the sake of best overall use of resources. Our objective is to efficiently provide and allocate multiple VMs to maximize social welfare and encourage users to declare truthful requests. We first design an offline optimal mechanism based on the VCG mechanism; this mechanism has full knowledge of all users and offers ideal solutions. We also design an online greedy mechanism that considers only current knowledge while offering near-optimal solutions instead. Our proposed greedy mechanism consists of winner determination and payment algorithms. Furthermore, we show that the winner determination algorithm is monotonic and that the payment algorithm implements the critical payment. Both our allocation methods offer incentives to users providing true values for the sake of obtaining the best utility. We performed extensive experiments to investigate the performance of our proposed greedy mechanism compared to the optimal mechanism. Experimental results demonstrate that our proposed greedy mechanism obtains near-optimal solutions in a reasonable time.