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.

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.

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.

A Hybrid Estimation of Distribution Algorithm for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times

A hybrid estimation of distribution algorithm(EDA)with iterated greedy(IG) search(EDA-IG) is proposed for solving the unrelated parallel machine scheduling problem with sequence-dependent setup times(UPMSP-SDST). For makespan criterion, some properties about neighborhood search operators to avoid invalid search are derived. A probability model based on neighbor relations of jobs is built in the EDA-based exploration phase to generate new solutions by sampling the promising search region. Two types of deconstruction and reconstruction as well as an IG search are designed in the IG-based exploitation phase.Computational complexity of the algorithm is analyzed, and the effect of parameters is investigated by using the Taguchi method of design-of-experiment. Numerical tests on 1640 benchmark instances are carried out. The results and comparisons demonstrate the effectiveness of the EDA-IG. Especially, the bestknown solutions of 531 instances are updated. In addition, the effectiveness of the properties is also demonstrated by numerical comparisons.

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.

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.

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.

Homing Strategy for a 4RRR Parallel Kinematic Machine

Returning home is the most important process of a parallel kinematic machine （PKM） with incremental encoders.Currently,most corresponding articles focus on the accuracy of homing process,and there lacks the investigation of the operation＇s safety.For a 4RRR PKM,all servoaxes would be independently driven to their zero positions at the same time based on the traditional homing mode,and that can bring serious interfere of the kinematic chains.This paper systemically investigates this 4RRR PKM＇s safety of homing process.A homing strategy usually contains three parts which are the home switches＇ locations,the platform＇s initial moving space,and each links＇ homing direction,and all of them can influence the safety of homing operation.For the purpose of evaluating and describing the safety of the homing strategy,some important parameters are introduced as follows：Safely homing ratio （SHR） is used to evaluate the probability of a machine＇s successfully returning home from an initial moving space;Synchronal rotational angle （SRA） is the four links＇ largest synchronal rotational angle with given directions from a given pose.Whether a machine can safely return home from a given pose can be judged by comparing the SRA with all four home switches＇ mounting angles.By meshing the initial moving space and checking the safeties of returning home from all the initial poses on the nodes,the SHR of this initial moving space can be calculate.For the sake of convenience,the platform＇s initial moving space should be as large as possible,and in this 4RRR PKM,a square zone in the center of the workspace with a giving initial rotation range is selected as the platform＇s initial moving space.The forward direction is selected as each link＇s homing direction according to custom,and the platform＇s initial rotational angle is selected as larger than 0° based on this 4RRR PKM＇s kinematic characteristics.The platform＇s initial moving space can be defined only by the side length of the initial moving square.By setting a probable searching step and calculating the SHR of the initial moving square,an optimal procedure of searching for the largest side length of the platform＇s initial moving square is proposed.The homing strategy proposed is based on a systemic research on the safety of homing process for PKM,and the two new indexes SHR and SRA can clearly describe the safety of homing operation.The homing operation based on this strategy is fast and safe,and the method can also be used in other PKMs with the situation of serious components＇ interference.

Concise review of relaxations and approximation algorithms for nonidentical parallel-machine scheduling to minimize total weighted completion times

A class of nonidentical parallel machine scheduling problems are considered in which the goal is to minimize the total weighted completion time. Models and relaxations are collected. Most of these problems are NP-hard, in the strong sense, or open problems, therefore approximation algorithms are studied. The review reveals that there exist some potential areas worthy of further research.

Heuristic algorithms for scheduling on uniform parallel machines with heads and tails

This paper considers the uniform parallel machine scheduling problem with unequal release dates and delivery times to minimize the maximum completion time.For this NP-hard problem,the largest sum of release date,processing time and delivery time first rule is designed to determine a certain machine for each job,and the largest difference between delivery time and release date first rule is designed to sequence the jobs scheduled on the same machine,and then a novel algorithm for the scheduling problem is built.To evaluate the performance of the proposed algorithm,a lower bound for the problem is proposed.The accuracy of the proposed algorithm is tested based on the data with problem size varying from 200 jobs to 600 jobs.The computational results indicate that the average relative error between the proposed algorithm and the lower bound is only 0.667%,therefore the solutions obtained by the proposed algorithm are very accurate.

Generalized multiple time windows model based parallel machine scheduling for TDRSS

The scheduling efficiency of the tracking and data relay satellite system（TDRSS）is strictly limited by the scheduling degrees of freedom（DoF）,including time DoF defined by jobs＇ flexible time windows and spatial DoF brought by multiple servable tracking and data relay satellites（TDRSs）.In this paper,ageneralized multiple time windows（GMTW）model is proposed to fully exploit the time and spatial DoF.Then,the improvements of service capability and job-completion probability based on the GMTW are theoretically proved.Further,an asymmetric path-relinking（APR）based heuristic job scheduling framework is presented to maximize the usage of DoF provided by the GMTW.Simulation results show that by using our proposal 11%improvement of average jobcompletion probability can be obtained.Meanwhile,the computing time of the time-to-target can be shorten to 1/9 of the GRASP.

Parallel Molecular Dynamics on the Connection Machines

Abstract Abstract:We have demonstrated using vectorized parallel Lennard-Jones fluid program that vectorizing general-purpose parallel molecular package for simulating biomolecules which currently runs on the Connection Machine CM-5 using CMMD message passing would offer a significant improvement over 4 non-vectorized version. Our results indicate that the Lennard-Jones fluid program written in C*/CMNID is five times faster than the same program written in C/CMMD.

Parallel Machine Scheduling Models with Fuzzy Parameters and Precedence Constraints: A Credibility Approach

A method for modeling the parallel machine scheduling problems with fuzzy parameters and precedence constraints based on credibility measure is provided. For the given n jobs to be processed on m machines, it is assumed that the processing times and the due dates are nonnegative fuzzy numbers and all the weights are positive, crisp numbers. Based on credibility measure, three parallel machine scheduling problems and a goal-programming model are formulated. Feasible schedules are evaluated not only by their objective values but also by the credibility degree of satisfaction with their precedence constraints. The genetic algorithm is utilized to find the best solutions in a short period of time. An illustrative numerical example is also given. Simulation results show that the proposed models are effective, which can deal with the parallel machine scheduling problems with fuzzy parameters and precedence constraints based on credibility measure.

The Kinematic Analyses of the 3-DOF Parallel Machine Tools

A 3-degree-of-freedom （3-DOF） parallel machine tool based on a tripod mechanism is developed and studied. The kinematics analysis is performed, the workspace is derived, and an analysis on the number of conditions of the Jacobian matrix and manipulability is carried out. A method for error analysis and manipulability is introduced. Hence, the manipulability analysis of the parallel machine tool is accomplished.