Dynamical Artificial Bee Colony for Energy-Efficient Unrelated Parallel Machine Scheduling with Additional Resources and Maintenance

Unrelated parallel machine scheduling problem(UPMSP)is a typical scheduling one and UPMSP with various reallife constraints such as additional resources has been widely studied;however,UPMSP with additional resources,maintenance,and energy-related objectives is seldom investigated.The Artificial Bee Colony(ABC)algorithm has been successfully applied to various production scheduling problems and demonstrates potential search advantages in solving UPMSP with additional resources,among other factors.In this study,an energy-efficient UPMSP with additional resources and maintenance is considered.A dynamical artificial bee colony(DABC)algorithm is presented to minimize makespan and total energy consumption simultaneously.Three heuristics are applied to produce the initial population.Employed bee swarm and onlooker bee swarm are constructed.Computing resources are shifted from the dominated solutions to non-dominated solutions in each swarm when the given condition is met.Dynamical employed bee phase is implemented by computing resource shifting and solution migration.Computing resource shifting and feedback are used to construct dynamical onlooker bee phase.Computational experiments are conducted on 300 instances from the literature and three comparative algorithms and ABC are compared after parameter settings of all algorithms are given.The computational results demonstrate that the new strategies of DABC are effective and that DABC has promising advantages in solving the considered UPMSP.

Scheduling an Energy-Aware Parallel Machine System with Deteriorating and Learning Effects Considering Multiple Optimization Objectives and Stochastic Processing Time

Currently,energy conservation draws wide attention in industrial manufacturing systems.In recent years,many studies have aimed at saving energy consumption in the process of manufacturing and scheduling is regarded as an effective approach.This paper puts forwards a multi-objective stochastic parallel machine scheduling problem with the consideration of deteriorating and learning effects.In it,the real processing time of jobs is calculated by using their processing speed and normal processing time.To describe this problem in a mathematical way,amultiobjective stochastic programming model aiming at realizing makespan and energy consumption minimization is formulated.Furthermore,we develop a multi-objective multi-verse optimization combined with a stochastic simulation method to deal with it.In this approach,the multi-verse optimization is adopted to find favorable solutions from the huge solution domain,while the stochastic simulation method is employed to assess them.By conducting comparison experiments on test problems,it can be verified that the developed approach has better performance in coping with the considered problem,compared to two classic multi-objective evolutionary algorithms.

Non-Cooperative Game of Coordinated Scheduling of Parallel Machine Production and Transportation in Shared Manufacturing

Given the challenges of manufacturing resource sharing and competition in the modern manufacturing industry,the coordinated scheduling problem of parallel machine production and transportation is investigated.The problem takes into account the coordination of production and transportation before production as well as the disparities in machine spatial position and performance.A non-cooperative game model is established,considering the competition and self-interest behavior of jobs from different customers for machine resources.The job from different customers is mapped to the players in the game model,the corresponding optional processing machine and location are mapped to the strategy set,and the makespan of the job is mapped to the payoff.Then the solution of the scheduling model is transformed into the Nash equilibrium of the non-cooperative game model.A Nash equilibrium solution algorithm based on the genetic algorithm(NEGA)is designed,and the effective solution of approximate Nash equilibrium for the game model is realized.The fitness function,single-point crossover operator,and mutation operator are derived from the non-cooperative game model’s characteristics and the definition of Nash equilibrium.Rules are also designed to avoid the generation of invalid offspring chromosomes.The effectiveness of the proposed algorithm is demonstrated through numerical experiments of various sizes.Compared with other algorithms such as heuristic algorithms(FCFS,SPT,and LPT),the simulated annealing algorithm(SA),and the particle swarm optimization algorithm(PSO),experimental results show that the proposed NE-GA algorithm has obvious performance advantages.

Two-Agent Makespan Minimization Problem on Parallel Machines

A two-agent scheduling problem on parallel machines is considered in this paper. Our objective is to minimize the makespan for agent A, subject to an upper bound on the makespan for agent B. In this paper, we provide a new approximation algorithm called CLPT. On the one hand, we compare the performance between the CLPT algorithm and the optimal solution and find that the solution obtained by the CLPT algorithm is very close to the optimal solution. On the other hand, we design different experimental frameworks to compare the CLPT algorithm and the A-LS algorithm for a comprehensive performance evaluation. A large number of numerical simulation results show that the CLPT algorithm outperformed the A-LS algorithm.

Simulation Study of the Workspace of the Parallel Machine Tool

A new three dimensional simulation method is introduced to study the workspace of a 6 PSS (P denotes a prismatic kinematic pair, S denotes a spherical kinematic pair) parallel machine tool. This algorithm adopts the method of numerical analysis to investigate the boundary points in a series of sections which form the surface of the workspace. That is, to study such points that have the largest polar radius on a certain section in a system of polar coordinates according to conditions of constraint. The constraint conditions considered in the article include the maximum and minimum displacements of each dieblock, the maximum and minimum angles of oscillation in each hinge. By converting the constraint inequalities into constraint equations, the largest polar radius corresponding to every constraint condition can be evaluated and the minimum one is used to decide the boundary point. This algorithm greatly simplifies the computational process and can be used to analyze any section of the workspace. It provides a theoretical basis for the structural design of such a machine tool.

STIFFNESS ANALYSIS OF THE MAIN MODULE FOR PARALLEL MACHINE TOOLS BY FINITE ELEMENT ANALYSIS

With the aid of commercial finite element analysis software package ANSYS,investigations are made on the contributions of main components to stiffness of the main module for parallel machine tools,and it is found that the frame is the main contributor.Then,influences of constraints,strut length and working ways of the main module have also been investigated.It can be concluded that when one of the main planes of the frame without linear drive unit is constrained,the largest whole stiffness can be acquired.And,the stiffness is much better when the main module is used in a vertical machine tool instead of a horizontal one.Finally,the principle of stiffness variation is summarized when the mobile platform reaches various positions within its working space and when various loads are applied.These achievements have provided critical instructions for the design of the main module for parallel machine tools.

Parallel Implementation of Global Illumination Using PVM

In this paper an attempt of employing network resources to solve a complex and time-consuming problem is presented. The global illumination problem is selected as the study objective. An improved density estimation algorithm is first developed, in which the more inherent concurrency is explored. Then its parallel implementation by using a PVM mechanism and the running performance analysis are provided. The analysis results show the expected speed-up obtained and demonstrate that the PVM has good application prospects for parallel computation in a distributed network.

Compliance Modeling and Analysis of a 3-RPS Parallel Kinematic Machine Module

The compliance modeling and rigidity performance evaluation for the lower mobility parallel manipulators are still to be remained as two overwhelming challenges in the stage of conceptual design due to their geometric complexities. By using the screw theory, this paper explores the compliance modeling and eigencompliance evaluation of a newly patented 1T2R spindle head whose topological architecture is a 3-RPS parallel mechanism. The kinematic definitions and inverse position analysis are briefly addressed in the first place to provide necessary information for compliance modeling. By considering the 3-RPS parallel kinematic machine（PKM） as a typical compliant parallel device, whose three limb assemblages have bending, extending and torsional deflections, an analytical compliance model for the spindle head is established with screw theory and the analytical stiffness matrix of the platform is formulated. Based on the eigenscrew decomposition, the eigencompliance and corresponding eigenscrews are analyzed and the platform＇s compliance properties are physically interpreted as the suspension of six screw springs. The distributions of stiffness constants of the six screw springs throughout the workspace are predicted in a quick manner with a piece-by-piece calculation algorithm. The numerical simulation reveals a strong dependency of platform＇s compliance on its configuration in that they are axially symmetric due to structural features. At the last stage, the effects of some design variables such as structural, configurational and dimensional parameters on system rigidity characteristics are investigated with the purpose of providing useful information for the structural design and performance improvement of the PKM. Compared with previous efforts in compliance analysis of PKMs, the present methodology is more intuitive and universal thus can be easily applied to evaluate the overall rigidity performance of other PKMs with high efficiency.

Kinetostatic Modeling and Analysis of an Exechon Parallel Kinematic Machine(PKM) Module

As a newly invented parallel kinematic machine（PKM）, Exechon has found its potential application in machining and assembling industries due to high rigidity and high dynamics. To guarantee the overall performance, the loading conditions and deflections of the key components must be revealed to provide basic mechanic data for component design. For this purpose, a kinetostatic model is proposed with substructure synthesis technique. The Exechon is divided into a platform subsystem, a fixed base subsystem and three limb subsystems according to its structure. By modeling the limb assemblage as a spatial beam constrained by two sets of lumped virtual springs representing the compliances of revolute joint, universal joint and spherical joint, the equilibrium equations of limb subsystems are derived with finite element method（FEM）. The equilibrium equations of the platform are derived with Newton＇s 2nd law. By introducing deformation compatibility conditions between the platform and limb, the governing equilibrium equations of the system are derived to formulate an analytical expression for system＇s deflections. The platform＇s elastic displacements and joint reactions caused by the gravity are investigated to show a strong position-dependency and axis-symmetry due to its kinematic and structure features. The proposed kinetostatic model is a trade-off between the accuracy of FEM and concision of analytical method, thus can predict the kinetostatics throughout the workspace in a quick and succinct manner. The proposed modeling methodology and kinetostatic analysis can be further expanded to other PKMs with necessary modifications, providing useful information for kinematic calibration as well as component strength calculations.

Separation of Comprehensive Geometrical Errors of a 3-DOF Parallel Manipulator Based on Jacobian Matrix and Its Sensitivity Analysis with Monte-Carlo Method

Parallel kinematic machines （PKMs） have the advantages of a compact structure,high stiffness,a low moving inertia,and a high load/weight ratio.PKMs have been intensively studied since the 1980s,and are still attracting much attention.Compared with extensive researches focus on their type/dimensional synthesis,kinematic/dynamic analyses,the error modeling and separation issues in PKMs are not studied adequately,which is one of the most important obstacles in its commercial applications widely.Taking a 3-PRS parallel manipulator as an example,this paper presents a separation method of source errors for 3-DOF parallel manipulator into the compensable and non-compensable errors effectively.The kinematic analysis of 3-PRS parallel manipulator leads to its six-dimension Jacobian matrix,which can be mapped into the Jacobian matrix of actuations and constraints,and then the compensable and non-compensable errors can be separated accordingly.The compensable errors can be compensated by the kinematic calibration,while the non-compensable errors may be adjusted by the manufacturing and assembling process.Followed by the influence of the latter,i.e.,the non-compensable errors,on the pose error of the moving platform through the sensitivity analysis with the aid of the Monte-Carlo method,meanwhile,the configurations of the manipulator are sought as the pose errors of the moving platform approaching their maximum.The compensable and non-compensable errors in limited-DOF parallel manipulators can be separated effectively by means of the Jacobian matrix of actuations and constraints,providing designers with an informative guideline to taking proper measures for enhancing the pose accuracy via component tolerancing and/or kinematic calibration,which can lay the foundation for the error distinguishment and compensation.

A Finite and Instantaneous Screw Based Approach for Topology Design and Kinematic Analysis of 5-Axis Parallel Kinematic Machines

Unifying the models for topology design and kinematic analysis has long been a desire for the research of parallel kinematic machines(PKMs). This requires that analytical description, formulation and operation for both finite and instantaneous motions are performed by the same mathematical tool. Based upon finite and instantaneous screw theory, a unified and systematic approach for topology design and kinematic analysis of PKMs is proposed in this paper. Using the derivative mapping between finite and instantaneous screws built in the authors’ previous work, the finite and instantaneous motions of PKMs are analytically described by the simple and non?redundant screws in quasi?vector and vector forms. And topological and parametric models of PKMs are algebraically formulated and related. These related topological and parametric models are ready to do type synthesis and kinematic analysis of PKMs under the unified framework of screw theory. In order to show the validity of the proposed approach, a kind of two?translational and three?rotational(2T3R)5?axis PKMs is taken as example. Numerous new structures of the 2T3R PKMs are synthe?sized as the results of topology design, and their Jacobian matrix is obtained easily for parameter optimization and performance evaluation. Some of the synthesized PKMs have outstanding capabilities in terms of large workspaces and flexible orientations, and have great potential for industrial applications of machining and manufacture. Among them, METROM PKM is a typical example which has attracted a lot of attention from global companies and already been developed as commercial products. The approach is a general and unified approach that can be used in the innovative design of different kinds of PKMs.

Comparison of Parallel Kinematic Machines with Three Translational Degrees of Freedom and Linear Actuation

The development of new robot structures, in particular of parallel kinematic machines（PKM）, is widely systematized by different structure synthesis methods. Recent research increasingly focuses on PKM with less than six degrees of freedom（DOF）. However, an overall comparison and evaluation of these structures is missing. In order to compare symmetrical PKM with three translational DOF, different evaluation criteria are used. Workspace, maximum actuation forces and velocities, power, actuator stiffness, accuracy and transmission behavior are taken into account to investigate strengths and weaknesses of the PKMs. A selection scheme based on possible configurations of translational PKM including different frame configurations is presented. Moreover, an optimization method based on a genetic algorithm is described to determine the geometric parameters of the selected PKM for an exemplary load case and a prescribed workspace. The values of the mentioned criteria are determined for all considered PKM with respect to certain boundary conditions. The distribution and spreading of these values within the prescribed workspace is presented by using box plots for each criterion. Thereby, the performance characteristics of the different structures can be compared directly. The results show that there is no ＂best＂ PKM. Further inquiries such as dynamic or stiffness analysis are necessary to extend the comparison and to finally select a PKM.

Self-adaptive large neighborhood search algorithm for parallel machine scheduling problems

A self-adaptive large neighborhood search method for scheduling n jobs on m non-identical parallel machines with mul- tiple time windows is presented. The problems＇ another feature lies in oversubscription, namely not all jobs can be scheduled within specified scheduling horizons due to the limited machine capacity. The objective is thus to maximize the overall profits of processed jobs while respecting machine constraints. A first-in- first-out heuristic is applied to find an initial solution, and then a large neighborhood search procedure is employed to relax and re- optimize cumbersome solutions. A machine learning mechanism is also introduced to converge on the most efficient neighborhoods for the problem. Extensive computational results are presented based on data from an application involving the daily observation scheduling of a fleet of earth observing satellites. The method rapidly solves most problem instances to optimal or near optimal and shows a robust performance in sensitive analysis.

KINEMATIC DESIGN OF A RECONFIGURABLE MINIATURE PARALLEL KINEMATIC MACHINE

The kinematic design of a reconfigurable miniature parallel kinematic machineis dealt with. It shows that the reconfigurability may be realized by packaging a tripod-basedparallel mechanism with fixed length struts into a compact and rigid frame with which the differentconfigurations can be formed. Utilizing a dual parameter model, the influences of the geometricalparameters on the dexterous performance and the workspace/machine volume ratio are investigated. Anovel global performance index for the dimensional synthesis is proposed and optimized, resulting ina set of dimensionless geometrical parameters.

Scheduling Step-Deteriorating Jobs on Parallel Machines by Mixed Integer Programming

Production scheduling has a major impact on the productivity of the manufacturing process. Recently, scheduling problems with deteriorating jobs have attracted increasing attentions from researchers. In many practical situations,it is found that some jobs fail to be processed prior to the pre-specified thresholds,and they often consume extra deteriorating time for successful accomplishment. Their processing times can be characterized by a step-wise function. Such kinds of jobs are called step-deteriorating jobs. In this paper,parallel machine scheduling problem with stepdeteriorating jobs( PMSD) is considered. Due to its intractability,four different mixed integer programming( MIP) models are formulated for solving the problem under consideration. The study aims to investigate the performance of these models and find promising optimization formulation to solve the largest possible problem instances. The proposed four models are solved by commercial software CPLEX. Moreover,the near-optimal solutions can be obtained by black-box local-search solver LocalS olver with the fourth one. The computational results show that the efficiencies of different MIP models depend on the distribution intervals of deteriorating thresholds, and the performance of LocalS olver is clearly better than that of CPLEX in terms of the quality of the solutions and the computational time.

Scheduling and Subcontracting under Parallel Machines

In this paper,we study a model on joint decisions of scheduling and subcontracting, in which jobs(orders) can be either processed by parallel machines at the manufacturer in-house or subcontracted to a subcontractor.The manufacturer needs to determine which jobs should be produced in-house and which jobs should be subcontracted.Furthermore,it needs to determine a production schedule for jobs to be produced in-house.We discuss five classical scheduling objectives as production costs.For each problem with different objective functions,we give optimality conditions and propose dynamic programming algorithms.

Performance analysis of active schedules in identical parallel machine

Active schedule is one of the most basic and popular concepts in production scheduling research. For identical parallel machine scheduling with jobs＇ dynamic arrivals, the tight performance bounds of active schedules under the measurement of four popular objectives are respectively given in this paper. Similar analysis method and conclusions can be generalized to static identical parallel machine and single machine scheduling problem.

Running Accuracy Analysis of a 3-RRR Parallel Kinematic Machine Considering the Deformations of the Links

Parallel kinematic machines have drawn considerable attention and have been widely used in some special fields.However,high precision is still one of the challenges when they are used for advanced machine tools.One of the main reasons is that the kinematic chains of parallel kinematic machines are composed of elongated links that can easily suffer deformations,especially at high speeds and under heavy loads.A 3-RRR parallel kinematic machine is taken as a study object for investigating its accuracy with the consideration of the deformations of its links during the motion process.Based on the dynamic model constructed by the Newton-Euler method,all the inertia loads and constraint forces of the links are computed and their deformations are derived.Then the kinematic errors of the machine are derived with the consideration of the deformations of the links.Through further derivation,the accuracy of the machine is given in a simple explicit expression,which will be helpful to increase the calculating speed.The accuracy of this machine when following a selected circle path is simulated.The influences of magnitude of the maximum acceleration and external loads on the running accuracy of the machine are investigated.The results show that the external loads will deteriorate the accuracy of the machine tremendously when their direction coincides with the direction of the worst stiffness of the machine.The proposed method provides a solution for predicting the running accuracy of the parallel kinematic machines and can also be used in their design optimization as well as selection of suitable running parameters.

Robustly stable model predictive control based on parallel support vector machines with linear kernel

Robustly stable multi-step-ahead model predictive control (MPC) based on parallel support vector machines (SVMs) with linear kernel was proposed. First, an analytical solution of optimal control laws of parallel SVMs based MPC was derived, and then the necessary and sufficient stability condition for MPC closed loop was given according to SVM model, and finally a method of judging the discrepancy between SVM model and the actual plant was presented, and consequently the constraint sets, which can guarantee that the stability condition is still robust for model/plant mismatch within some given bounds, were obtained by applying small-gain theorem. Simulation experiments show the proposed stability condition and robust constraint sets can provide a convenient way of adjusting controller parameters to ensure a closed-loop with larger stable margin.

A novel hybrid estimation of distribution algorithm for solving hybrid flowshop scheduling problem with unrelated parallel machine

The hybrid flow shop scheduling problem with unrelated parallel machine is a typical NP-hard combinatorial optimization problem, and it exists widely in chemical, manufacturing and pharmaceutical industry. In this work, a novel mathematic model for the hybrid flow shop scheduling problem with unrelated parallel machine(HFSPUPM) was proposed. Additionally, an effective hybrid estimation of distribution algorithm was proposed to solve the HFSPUPM, taking advantage of the features in the mathematic model. In the optimization algorithm, a new individual representation method was adopted. The(EDA) structure was used for global search while the teaching learning based optimization(TLBO) strategy was used for local search. Based on the structure of the HFSPUPM, this work presents a series of discrete operations. Simulation results show the effectiveness of the proposed hybrid algorithm compared with other algorithms.