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.

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.

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.

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.

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 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.

An approximation algorithm for parallel machine scheduling with simple linear deterioration

In this paper, a parallel machine scheduling problem was considered , where the processing time of a job is a simple linear function of its starting time. The objective is to minimize makespan. A fully polynomial time approximation scheme for the problem of scheduling n deteriorating jobs on two identical machines was worked out. Furthermore, the result was generalized to the case of a fixed number of machines.

Improved Estimation of Distribution Algorithm for Solving Unrelated Parallel Machine Scheduling Problem

Scheduling problem is a well-known combinatorial optimization problem.An effective improved estimation of distribution algorithm(IEDA) was proposed for minimizing the makespan of the unrelated parallel machine scheduling problem(UPMSP).Mathematical description was given for the UPMSP.The IEDA which was combined with variable neighborhood search(IEDA_VNS) was proposed to solve the UPMSP in order to improve local search ability.A new encoding method was designed for representing the feasible solutions of the UPMSP.More knowledge of the UPMSP were taken consideration in IEDA_ VNS for probability matrix which was based the processing time matrix.The simulation results show that the proposed IEDA_VNS can solve the problem effectively.

A New Inertial Sensing System for Dynamic Measurement of Parallel Machines

One way to solve the problem of measurement precision caused by deformity for thermal expansion, friction and load etc is to use an inertial sensor to measure a change in the length of the rod on a parallel machine. However, the characteristic of dynamic measurement in the inertial sensing system and the effects of the machine＇s working environment, bias error, misalignment and wide band random noise in inertial measurement data results in the in-accuracy of system measurement. Therefore, on the basis of the measurement system a new inertial sensing system is proposed; the drifting of error is restrained with a method of inertial error correction and the system＇s position and the velocity state variables are predicted by the data fusion. After measuring the whole 300mm movement in an experiment, the analyses of the experimental result showed that the application of the new inertial sensing system can improve the positional accuracy about 61% and the movement precision more than 20%. Measurement results also showed that the application of the new inertial sensing system for dynamic measurement was a feasible method to improve the machine＇s dynamic positioning precision. And with the further improvement of the low-cost solid-stateacceleramenter technology, the application of the machine can take a higher position and make the speed dynamic accuracy possible.

Dimensional Synthesis Design of Novel Parallel Machine Tool

This paper presents dimensional synthesis design theory for a novel planar 3-DOF (degrees of freedom) parallel machine tool. Closed-form solutions are developed for both the inverse and direct kinematics. The formulation of the dexterity and the definitions of the theoretical workspace and the valid workspace are used to analyze the effects of the design parameters on the dexterity and workspace. The analysis results are used to propose an approach to satisfy the platform motion requirement while realizing orientation capability, dexterity and valid workspace. A design example is given to illustrate the effectiveness of this approach.

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.

Parallel Machine Scheduling with Special Jobs

This paper considers parallel machine scheduling with special jobs. Normal jobs can be processed on any of the parallel machines, while the special jobs can only be processed on one machine. The problem is analyzed for various manufacturing conditions and service requirements. The off-line scheduling problem is transformed into a classical parallel machine scheduling problem. The on-line scheduling uses the FCFS （first come, first served）, SWSC （special window for special customers）, and FFFS （first fit, first served） algorithms to satisfy the various requirements. Furthermore, this paper proves that FCFS has a competitive ratio of m, where m is the number of parallel machines, and this bound is asymptotically tight, SWSC has a competitive ratio of 2 and FFFS has a competitive ratio of 3- 2/m, and these bounds are tight.

An Optimal Online Algorithm for Scheduling on Two Parallel Machines with GoS Eligibility Constraints

We consider the online scheduling problem on two parallel machines with the Grade of Service(GoS)eligibility constraints.The jobs arrive over time,and the objective is to minimize the makespan.We develop a(1+α)-competitive optimal algorithm,whereα≈0.555 is a solution ofα^(3)−2α^(2)−α+1=0.

Unrelated Parallel-Machine Scheduling Problems with General Truncated Job-Dependent Learning Effect

In this paper, we consider scheduling problems with general truncated job-dependent learning effect on unrelated parallel-machine. The objective functions are to minimize total machine load, total completion (waiting) time, total absolute differences in completion (waiting) times respectively. If the number of machines is fixed, these problems can be solved in time respectively, where m is the number of machines and n is the number of jobs.

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.