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.

Parallel Inference for Real-Time Machine Learning Applications

Hyperparameter tuning is a key step in developing high-performing machine learning models, but searching large hyperparameter spaces requires extensive computation using standard sequential methods. This work analyzes the performance gains from parallel versus sequential hyperparameter optimization. Using scikit-learn’s Randomized SearchCV, this project tuned a Random Forest classifier for fake news detection via randomized grid search. Setting n_jobs to -1 enabled full parallelization across CPU cores. Results show the parallel implementation achieved over 5× faster CPU times and 3× faster total run times compared to sequential tuning. However, test accuracy slightly dropped from 99.26% sequentially to 99.15% with parallelism, indicating a trade-off between evaluation efficiency and model performance. Still, the significant computational gains allow more extensive hyperparameter exploration within reasonable timeframes, outweighing the small accuracy decrease. Further analysis could better quantify this trade-off across different models, tuning techniques, tasks, and hardware.

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.

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.

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.

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.

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.

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.

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.

Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines

This paper presents a survey of single machine scheduling problem with uniform parallel machines. The single machine scheduling problem with uniform parallel machines consists of n jobs, each with single operation, which are to be scheduled on m parallel machines with different speeds. These parallel machines are also called proportional machines or related machines. There are several measures of performance which are to be optimized in uniform parallel machines scheduling. Since, this scheduling problem is a combinatorial problem;usage of a heuristic is inevitable to obtain solution in polynomial time. This paper gives a classification of the literatures of this scheduling problem in three major categories, viz. offline scheduling, online scheduling and miscellaneous scheduling. In total, the available literatures are classified into 17 subgroups. Under each of the first two categories, the available literatures are discussed under different groups based on different measures of performance and non-preemptive/preemptive nature of the jobs. In the last category, the literatures are discussed under three subgroups, namely non-preemptive jobs, preemptive jobs and periodic jobs.

Simulated Annealing Algorithm to Minimize Makespanin Single Machine Scheduling Problem withUniform Parallel Machines

This paper presents a simulated annealing algorithm to minimize makespan of single machine scheduling problem with uniform parallel machines. The single machine scheduling problem with uniform parallel machines consists of n jobs, each with single operation, which are to be scheduled on m parallel machines with different speeds. Since, this scheduling problem is a combinatorial problem;usage of a heuristic is inevitable to obtain the solution in polynomial time. In this paper, simulated annealing algorithm is presented. In the first phase, a seed generation algorithm is given. Then, it is followed by three variations of the simulated annealing algorithms and their comparison using ANOVA in terms of their solutions on makespan.

Design and Comparison of Simulated Annealing Algorithm and GRASP to Minimize Makespan in Single Machine Scheduling with Unrelated Parallel Machines

This paper discusses design and comparison of Simulated Annealing Algorithm and Greedy Randomized Adaptive Search Procedure (GRASP) to minimize the makespan in scheduling n single operation independent jobs on m unrelated parallel machines. This problem of minimizing the makespan in single machine scheduling problem with uniform parallel machines is NP hard. Hence, heuristic development for such problem is highly inevitable. In this paper, two different Meta-heuristics to minimize the makespan of the assumed problem are designed and they are compared in terms of their solutions. In the first phase, the simulated annealing algorithm is presented and then GRASP (Greedy Randomized Adaptive Search procedure) is presented to minimize the makespan in the single machine scheduling problem with unrelated parallel machines. It is found that the simulated annealing algorithm performs better than GRASP.

A two-stage flexible flow-shop scheduling problem with m identical parallel machines on one stage and a batch processor on the other stage

This paper considers a hybrid two-stage flow-shop scheduling problem with m identical parallel machines on one stage and a batch processor on the other stage. The processing time of job Jj on any of m identical parallel machines is aj≡a （j∈N）, and the processing time of job Jj is bj（j∈N） on a batch processorM. We take makespan （Cmax） as our minimization objective. In this paper, for the problem of FSMP-BI （m identical parallel machines on the first stage and a batch processor on the second stage）, based on the algorithm given by Sung and Choung for the problem of 1 ｜ri, BI｜Cmax under the constraint of the given processing sequence, we develop an optimal dynamic programming Algorithm H1 for it in max {O（nlogn）, O（nB）} time. A max {O（nlogn） , O（nB）}time symmetric Algorithm H2 is given then for the problem of BI-FSMP （a batch processor on the first stage and m identical parallel machines on the second stage）.

Scheduling Multiple Orders per Job with Multiple Constraints on Identical Parallel Machines

With a comprehensive consideration of multiple product types, past-sequence-dependent （ p-s-d ） setup times, and deterioration effects constraints in processes of wafer fabrication systems, a novel scheduling model of multiple orders per job（MOJ） on identical parallel machines was developed and an immune genetic algorithm（IGA） was applied to solving the scheduling problem. A scheduling problem domain was described. A non-linear mathematical programming model was also set up with an objective function of minimizing total weighted earliness-tardlness penalties of the system. On the basis of the mathematical model, IGA was put forward. Based on the genetic algorithm （GA）, the proposed algorithm （IGA） can generate feasible solutions and ensure the diversity of antibodies. In the process of immunization programming, to guarantee the algorithm＇s convergence performance, the modified rule of apparent tardiness cost with setups （ATCS） was presented. Finally, simulation experiments were designed, and the results indicated that the algorithm had good adaptability when the values of the constraints＇ characteristic parameters were changed and it verified the validity of the algorithm.

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.

Genetic Algorithm for Scheduling Reentrant Jobs on Parallel Machines with a Remote Server

This paper considers a reentrant scheduling problem on parallel primary machines with a remote server machine, which is required to carry out the setup operation. In this problem, each job has three operations. The first and last operations are performed by the same primary machine, implying the reentrance, and the second operation is processed on the single server machine. The order of jobs is predetermined in our context. The challenge is to assign jobs to the primary machines to minimize the makespan. We develop a genetic algorithm(GA) to solve this problem. Based on a simple strategy of assigning jobs in batches on the parallel primary machines, the standardized random key vector representation is employed to split the jobs into batches. Comparisons among the proposed algorithm, the branch and bound(BB) algorithm and the heuristic algorithm, coordinated scheduling(CS), which is only one heuristic algorithm to solve this problem in the literature, are made on the benchmark data. The computational experiments show that the proposed genetic algorithm outperforms the heuristic CS and the maximum relative improvement rate in the makespan is 1.66%.

Ordinal Semi On-Line Scheduling for Jobs with Arbitrary Release Times on Identical Parallel Machines

In this paper, we investigate the problem of semi-on-line scheduling n jobs on m identical parallel machines under the assumption that the ordering of the jobs by processing time is known and the jobs have arbitrary release times. Our aim is to minimize the maximum completion time. An ordinal algorithm is investigated and its worst case ratio is analyzed.

Efficient Heuristic to Minimize Makespan in Single Machine Scheduling Problem with Unrelated Parallel Machines

This paper discusses an efficient heuristic to minimize the makespan of scheduling n independent jobs on m unrelated parallel machines. The problem of scheduling the jobs on the unrelated parallel machines is combinatorial in nature. Hence, the heuristic approach is inevitable for quicker solution. In this paper, a simple and efficient heuristic is designed to minimize the makespan of scheduling n independent jobs on m unrelated parallel machines. A mathematical model is also presented for this problem. A factorial experiment is used to compare the results of the proposed heuristic with that of a mathematical model by taking “Method” (Heuristic and Model) as the first factor and “Problem Size” (No. of machines X No. of Jobs: 2X5, 2X6, ……, 2X9, 3X5, 3X6, ……, 3X9, ……., 5X5, 5X6, …5X9) as the second factor. It is found that there is no significant difference between the results of the proposed heuristic and that of the mathematical model. Further, the mean percent error of the results obtained by the heuristic from the optimal results obtained by the model is 2.336 %. The heuristic gives optimal solution for 76.67 % of the problems.