A single-machine scheduling with preventive periodic maintenance activities in a remanufacturing system including resumable and non-resumable jobs is studied.The objective is to find a schedule to minimize the makespa...A single-machine scheduling with preventive periodic maintenance activities in a remanufacturing system including resumable and non-resumable jobs is studied.The objective is to find a schedule to minimize the makespan and an LPT-LS algorithm is proposed.Non-resumable jobs are first scheduled in a machine by the longest processing time（LPT） rule,and then resumable jobs are scheduled by the list scheduling（LS） rule.And the worst-case ratios of this algorithm in three different cases in terms of the value of the total processing time of the resumable jobs（denoted as S2） are discussed.When S2 is longer than the spare time of the machine after the non-resumable jobs are assigned by the LPT rule,it is equal to 1.When S2 falls in between the spare time of the machine by the LPT rule and the optimal schedule rule,it is less than 2.When S2 is less than the spare time of the machine by the optimal schedule rule,it is less than 2.Finally,numerical examples are presented for verification.展开更多
Motivated by industrial applications we study a single-machine scheduling problem in which all the jobs are mutu-ally independent and available at time zero.The machine processes the jobs sequentially and it is not id...Motivated by industrial applications we study a single-machine scheduling problem in which all the jobs are mutu-ally independent and available at time zero.The machine processes the jobs sequentially and it is not idle if there is any job to be pro-cessed.The operation of each job cannot be interrupted.The machine cannot process more than one job at a time.A setup time is needed if the machine switches from one type of job to another.The objective is to find an optimal schedule with the minimal total jobs’completion time.While the sum of jobs’processing time is always a constant,the objective is to minimize the sum of setup times.Ant colony optimization(ACO)is a meta-heuristic that has recently been applied to scheduling problem.In this paper we propose an improved ACO-Branching Ant Colony with Dynamic Perturbation(DPBAC)algorithm for the single-machine schedul-ing problem.DPBAC improves traditional ACO in following aspects:introducing Branching Method to choose starting points;im-proving state transition rules;introducing Mutation Method to shorten tours;improving pheromone updating rules and introduc-ing Conditional Dynamic Perturbation Strategy.Computational results show that DPBAC algorithm is superior to the traditional ACO algorithm.展开更多
In this paper we consider a single-machine scheduling model with deteriorating jobs and simultaneous learning, and we introduce polynomial solutions for single machine makespan minimization, total flow times minimizat...In this paper we consider a single-machine scheduling model with deteriorating jobs and simultaneous learning, and we introduce polynomial solutions for single machine makespan minimization, total flow times minimization and maximum lateness minimization corresponding to the first and second special cases of our model under some agreeable conditions. However, corresponding to the third special case of our model, we show that the optimal schedules may be different from those of the classical version for the above objective functions.展开更多
In a CPM network, the longest path problem is one of the most important subjects. According to the intrinsic principle of CPM network, the length of the paths between arbitrary two nodes is presented. Furthermore, the...In a CPM network, the longest path problem is one of the most important subjects. According to the intrinsic principle of CPM network, the length of the paths between arbitrary two nodes is presented. Furthermore, the length of the longest path from start node to arbitrary node and from arbitrary node to end node is proposed. In view of a scheduling problem of two activities with float in the CPM scheduling, we put forward Barycenter Theory and prove this theory based on the algorithm of the length of the longest path. By this theory, we know which activity should be done firstly. At last, we show our theory by an example.展开更多
Additive manufacturing(AM)has attracted significant attention in recent years based on its wide range of applications and growing demand.AM offers the advantages of production flexibility and design freedom.In this st...Additive manufacturing(AM)has attracted significant attention in recent years based on its wide range of applications and growing demand.AM offers the advantages of production flexibility and design freedom.In this study,we considered a practical variant of the batch-processing-machine(BPM)scheduling problem that arises in AM industries,where an AM machine can process multiple parts simultaneously,as long as the twodimensional rectangular packing constraint is not violated.Based on the set-partitioning formulation of our mixed-integer programming(MIP)model,a branch-and-price(B&P)algorithm was developed by embedding a column-generation technique into a branchand-bound framework.Additionally,a novel labelling algorithm was developed to accelerate the column-generation process.Ours is the first study to provide a B&P algorithm to solve the BPM scheduling problem in the AM industry.We tested the performance of our algorithm using a modern MIP solver(Gurobi)and real data from a 3D printing factory.The results demonstrate that for most instances tested,our algorithm produces results similar or identical to those of Gurobi with reasonable computation time and outperforms Gurobi in terms of solution quality and running time on some large instances.展开更多
In a local search algorithm,one of its most important features is the definition of its neighborhood which is crucial to the algorithm's performance.In this paper,we present an analysis of neighborhood combination...In a local search algorithm,one of its most important features is the definition of its neighborhood which is crucial to the algorithm's performance.In this paper,we present an analysis of neighborhood combination search for solv-ing the single-machine scheduling problem with sequence-dependent setup time with the objective of minimizing total weighted tardiness(SMSWT).First,We propose a new neighborhood structure named Block Swap(B1)which can be con-sidered as an extension of the previously widely used Block Move(B2)neighborhood,and a fast incremental evaluation technique to enhance its evaluation efficiency.Second,based on the Block Swap and Block Move neighborhoods,we present two kinds of neighborhood structures:neighborhood union(denoted by B1UB2)and token-ring search(denoted by B1→B2),both of which are combinations of B1 and B2.Third,we incorporate the neighborhood union and token-ring search into two representative metaheuristic algorithms:the Iterated Local Search Algorithm(ILSnew)and the Hybrid Evolutionary Algorithm(HEA_(new))to investigate the performance of the neighborhood union and token-ring search.Exten-sive experiments show the competitiveness of the token-ring search combination mechanism of the two neighborhoods.Tested on the 120 public benchmark instances,our HEA_(new)has a highly competitive performance in solution quality and computational time compared with both the exact algorithms and recent metaheuristics.We have also tested the HEA,new algorithm with the selected neighborhood combination search to deal with the 64 public benchmark instances of the single-machine scheduling problem with sequence-dependent setup time.HEAnew is able to match the optimal or the best known results for all the 64 instances.In particular,the computational time for reaching the best well-known results for five chal-lenging instances is reduced by at least 61.25%.展开更多
In response to the challenges faced by unmanned swarms in mountain obstacle-breaching missions within complex terrains,such as poor task-resource coupling,lengthy solution generation times,and poor inter-platform coll...In response to the challenges faced by unmanned swarms in mountain obstacle-breaching missions within complex terrains,such as poor task-resource coupling,lengthy solution generation times,and poor inter-platform collaboration,an unmanned swarm scheduling strategy tailored is proposed for mountain obstacle-breaching missions.Initially,by formalizing the descriptions of obstacle breaching operations,the swarm,and obstacle targets,an optimization model is constructed with the objectives of expected global benefit,timeliness,and task completion degree.A meta-task decomposition and reassembly strategy is then introduced to more precisely match the capabilities of unmanned platforms with task requirements.Additionally,a meta-task decomposition optimization model and a meta-task allocation operator are incorporated to achieve efficient allocation of swarm resources and collaborative scheduling.Simulation results demonstrate that the model can accurately generate reasonable and feasible obstacle breaching execution plans for unmanned swarms based on specific task requirements and environmental conditions.Moreover,compared to conventional strategies,the proposed strategy enhances task completion degree and expected returns while reducing the execution time of the plans.展开更多
Task scheduling in cloud computing is a multi-objective optimization problem,often involving conflicting objectives such as minimizing execution time,reducing operational cost,and maximizing resource utilization.Howev...Task scheduling in cloud computing is a multi-objective optimization problem,often involving conflicting objectives such as minimizing execution time,reducing operational cost,and maximizing resource utilization.However,traditional approaches frequently rely on single-objective optimization methods which are insufficient for capturing the complexity of such problems.To address this limitation,we introduce MDMOSA(Multi-objective Dwarf Mongoose Optimization with Simulated Annealing),a hybrid that integrates multi-objective optimization for efficient task scheduling in Infrastructure-as-a-Service(IaaS)cloud environments.MDMOSA harmonizes the exploration capabilities of the biologically inspired Dwarf Mongoose Optimization(DMO)with the exploitation strengths of Simulated Annealing(SA),achieving a balanced search process.The algorithm aims to optimize task allocation by reducing makespan and financial cost while improving system resource utilization.We evaluate MDMOSA through extensive simulations using the real-world Google Cloud Jobs(GoCJ)dataset within the CloudSim environment.Comparative analysis against benchmarked algorithms such as SMOACO,MOTSGWO,and MFPAGWO reveals that MDMOSA consistently achieves superior performance in terms of scheduling efficiency,cost-effectiveness,and scalability.These results confirm the potential of MDMOSA as a robust and adaptable solution for resource scheduling in dynamic and heterogeneous cloud computing infrastructures.展开更多
The proliferation of carrier aircraft and the integration of unmanned aerial vehicles(UAVs)on aircraft carriers present new challenges to the automation of launch and recovery operations.This paper investigates a coll...The proliferation of carrier aircraft and the integration of unmanned aerial vehicles(UAVs)on aircraft carriers present new challenges to the automation of launch and recovery operations.This paper investigates a collaborative scheduling problem inherent to the operational processes of carrier aircraft,where launch and recovery tasks are conducted concurrently on the flight deck.The objective is to minimize the cumulative weighted waiting time in the air for recovering aircraft and the cumulative weighted delay time for launching aircraft.To tackle this challenge,a multiple population self-adaptive differential evolution(MPSADE)algorithm is proposed.This method features a self-adaptive parameter updating mechanism that is contingent upon population diversity,an asynchronous updating scheme,an individual migration operator,and a global crossover mechanism.Additionally,comprehensive experiments are conducted to validate the effectiveness of the proposed model and algorithm.Ultimately,a comparative analysis with existing operation modes confirms the enhanced efficiency of the collaborative operation mode.展开更多
Aircraft assembly is characterized by stringent precedence constraints,limited resource availability,spatial restrictions,and a high degree of manual intervention.These factors lead to considerable variability in oper...Aircraft assembly is characterized by stringent precedence constraints,limited resource availability,spatial restrictions,and a high degree of manual intervention.These factors lead to considerable variability in operator workloads and significantly increase the complexity of scheduling.To address this challenge,this study investigates the Aircraft Pulsating Assembly Line Scheduling Problem(APALSP)under skilled operator allocation,with the objective of minimizing assembly completion time.A mathematical model considering skilled operator allocation is developed,and a Q-Learning improved Particle Swarm Optimization algorithm(QLPSO)is proposed.In the algorithm design,a reverse scheduling strategy is adopted to effectively manage large-scale precedence constraints.Moreover,a reverse sequence encoding method is introduced to generate operation sequences,while a time decoding mechanism is employed to determine completion times.The problem is further reformulated as a Markov Decision Process(MDP)with explicitly defined state and action spaces.Within QLPSO,the Q-learning mechanism adaptively adjusts inertia weights and learning factors,thereby achieving a balance between exploration capability and convergence performance.To validate the effectiveness of the proposed approach,extensive computational experiments are conducted on benchmark instances of different scales,including small,medium,large,and ultra-large cases.The results demonstrate that QLPSO consistently delivers stable and high-quality solutions across all scenarios.In ultra-large-scale instances,it improves the best solution by 25.2%compared with the Genetic Algorithm(GA)and enhances the average solution by 16.9%over the Q-learning algorithm,showing clear advantages over the comparative methods.These findings not only confirm the effectiveness of the proposed algorithm but also provide valuable theoretical references and practical guidance for the intelligent scheduling optimization of aircraft pulsating assembly lines.展开更多
In this paper,we propose a new privacy-aware transmission scheduling algorithm for 6G ad hoc networks.This system enables end nodes to select the optimum time and scheme to transmit private data safely.In 6G dynamic h...In this paper,we propose a new privacy-aware transmission scheduling algorithm for 6G ad hoc networks.This system enables end nodes to select the optimum time and scheme to transmit private data safely.In 6G dynamic heterogeneous infrastructures,unstable links and non-uniform hardware capabilities create critical issues regarding security and privacy.Traditional protocols are often too computationally heavy to allow 6G services to achieve their expected Quality-of-Service(QoS).As the transport network is built of ad hoc nodes,there is no guarantee about their trustworthiness or behavior,and transversal functionalities are delegated to the extreme nodes.However,while security can be guaranteed in extreme-to-extreme solutions,privacy cannot,as all intermediate nodes still have to handle the data packets they are transporting.Besides,traditional schemes for private anonymous ad hoc communications are vulnerable against modern intelligent attacks based on learning models.The proposed scheme fulfills this gap.Findings show the probability of a successful intelligent attack reduces by up to 65%compared to ad hoc networks with no privacy protection strategy when used the proposed technology.While congestion probability can remain below 0.001%,as required in 6G services.展开更多
To address the issue that hybrid flow shop production struggles to handle order disturbance events,a dynamic scheduling model was constructed.The model takes minimizing the maximum makespan,delivery time deviation,and...To address the issue that hybrid flow shop production struggles to handle order disturbance events,a dynamic scheduling model was constructed.The model takes minimizing the maximum makespan,delivery time deviation,and scheme deviation degree as the optimization objectives.An adaptive dynamic scheduling strategy based on the degree of order disturbance is proposed.An improved multi-objective Grey Wolf(IMOGWO)optimization algorithm is designed by combining the“job-machine”two-layer encoding strategy,the timing-driven two-stage decoding strategy,the opposition-based learning initialization population strategy,the POX crossover strategy,the dualoperation dynamic mutation strategy,and the variable neighborhood search strategy for problem solving.A variety of test cases with different scales were designed,and ablation experiments were conducted to verify the effectiveness of the improved strategies.The results show that each improved strategy can effectively enhance the performance of the IMOGWO.Additionally,performance analysis was conducted by comparing the proposed algorithm with three mature and classical algorithms.The results demonstrate that the proposed algorithm exhibits superior performance in solving the hybrid flow-shop scheduling problem(HFSP).Case validations were conducted for different types of order disturbance scenarios.The results demonstrate that the proposed adaptive dynamic scheduling strategy and the IMOGWO algorithm can effectively address order disturbance events.They enable rapid response to order disturbance while ensuring the stability of the production system.展开更多
The cloud-fog computing paradigm has emerged as a novel hybrid computing model that integrates computational resources at both fog nodes and cloud servers to address the challenges posed by dynamic and heterogeneous c...The cloud-fog computing paradigm has emerged as a novel hybrid computing model that integrates computational resources at both fog nodes and cloud servers to address the challenges posed by dynamic and heterogeneous computing networks.Finding an optimal computational resource for task offloading and then executing efficiently is a critical issue to achieve a trade-off between energy consumption and transmission delay.In this network,the task processed at fog nodes reduces transmission delay.Still,it increases energy consumption,while routing tasks to the cloud server saves energy at the cost of higher communication delay.Moreover,the order in which offloaded tasks are executed affects the system’s efficiency.For instance,executing lower-priority tasks before higher-priority jobs can disturb the reliability and stability of the system.Therefore,an efficient strategy of optimal computation offloading and task scheduling is required for operational efficacy.In this paper,we introduced a multi-objective and enhanced version of Cheeta Optimizer(CO),namely(MoECO),to jointly optimize the computation offloading and task scheduling in cloud-fog networks to minimize two competing objectives,i.e.,energy consumption and communication delay.MoECO first assigns tasks to the optimal computational nodes and then the allocated tasks are scheduled for processing based on the task priority.The mathematical modelling of CO needs improvement in computation time and convergence speed.Therefore,MoECO is proposed to increase the search capability of agents by controlling the search strategy based on a leader’s location.The adaptive step length operator is adjusted to diversify the solution and thus improves the exploration phase,i.e.,global search strategy.Consequently,this prevents the algorithm from getting trapped in the local optimal solution.Moreover,the interaction factor during the exploitation phase is also adjusted based on the location of the prey instead of the adjacent Cheetah.This increases the exploitation capability of agents,i.e.,local search capability.Furthermore,MoECO employs a multi-objective Pareto-optimal front to simultaneously minimize designated objectives.Comprehensive simulations in MATLAB demonstrate that the proposed algorithm obtains multiple solutions via a Pareto-optimal front and achieves an efficient trade-off between optimization objectives compared to baseline methods.展开更多
With the increasing number of geosynchronous orbit satellites with expiring lifetime,spacecraft refueling is crucial in enhancing the economic benefits of on-orbit services.The existing studies tend to be based on pre...With the increasing number of geosynchronous orbit satellites with expiring lifetime,spacecraft refueling is crucial in enhancing the economic benefits of on-orbit services.The existing studies tend to be based on predetermined refueling duration;however,the precise mission scheduling solution will be difficult to apply due to uncertain refueling duration caused by orbital transfer deviations and stochastic actuator faults during actual on-orbit service.Therefore,this paper proposes a robust mission scheduling strategy for geosynchronous orbit spacecraft on-orbit refueling missions with uncertain refueling duration.Firstly,a robust mission scheduling model is constructed by introducing the budget uncertainty set to describe the uncertain refueling duration.Secondly,a hybrid harris hawks optimization algorithm is designed to explore the optimal mission allocation and refueling sequences,which combines cubic chaotic mapping to initialize the population,and the crossover in the genetic algorithm is introduced to enhance global convergence.Finally,the typical simulation examples are constructed with real-mission scenarios in three aspects to analyze:performance comparisons with various algorithms;robustness analyses via comparisons of different on-orbit refueling durations;investigations into the impacts of different initial population strategies on algorithm performance,demonstrating the proposed mission scheduling framework's robustness and effectiveness by comparing it with the exact mission scheduling.展开更多
We study single-machine scheduling problems with a single maintenance activity(MA)of length p0 under three types of assumptions:(A)the MA is required in a fixed time interval[T−p0,T]with T≥p0 and the job processing i...We study single-machine scheduling problems with a single maintenance activity(MA)of length p0 under three types of assumptions:(A)the MA is required in a fixed time interval[T−p0,T]with T≥p0 and the job processing is of preemptive and resumable;(B)the MA is required in a relaxed time interval[0,T]with T≥p0 and the job processing is of nonpreemptive;(C)the MA is required in a relaxed time interval[T0,T]with 0≤T0≤T−p0 and the job processing is of nonpreemptive.We show in this paper that,up to the time complexity for solving scheduling problems,assumptions(A)and(B)are equivalent,and moreover,if T−(T0+p0)is greater than or equal to the maximum processing time of all jobs,the assumption(C)is also equivalent to(A)and(B).As an application,we study the scheduling for minimizing the weighted number of tardy jobs under the above three assumptions,respectively,and present corresponding time-complexity results.展开更多
The single-machine lot scheduling problem with splittable jobs to minimize the number of tardy jobs has been showed to be weakly NP-hard in the literature.In this paper,we show that a generalized version of this probl...The single-machine lot scheduling problem with splittable jobs to minimize the number of tardy jobs has been showed to be weakly NP-hard in the literature.In this paper,we show that a generalized version of this problem in which jobs have deadlines is strongly NP-hard,and also present the results of some related scheduling problems.展开更多
In this paper,we consider the single-machine scheduling with step-deteriorating jobs and rejection.Each job is either rejected by paying a rejection penalty,or accepted and processed on the single machine,and the actu...In this paper,we consider the single-machine scheduling with step-deteriorating jobs and rejection.Each job is either rejected by paying a rejection penalty,or accepted and processed on the single machine,and the actual processing time of each accepted job is a step function of its starting time and the common deteriorating date.The objective is to minimize the makespan of the accepted jobs plus the total penalty of the rejected jobs.For the case of common deteriorating penalty,we first show that the problem is NP-hard in the ordinary sense.Then we present two pseudo-polynomial algorithms and a 2-approximation algorithm.Furthermore,we propose a fully polynomial time approximation scheme.For the case of common normal processing time,we present two pseudo-polynomial time algorithms,a 2-approximation algorithm and a fully polynomial time approximation scheme.展开更多
In this paper,a bilevel optimization model of an integrated energy operator(IEO)–load aggregator(LA)is constructed to address the coordinate optimization challenge of multiple stakeholder island integrated energy sys...In this paper,a bilevel optimization model of an integrated energy operator(IEO)–load aggregator(LA)is constructed to address the coordinate optimization challenge of multiple stakeholder island integrated energy system(IIES).The upper level represents the integrated energy operator,and the lower level is the electricity-heatgas load aggregator.Owing to the benefit conflict between the upper and lower levels of the IIES,a dynamic pricing mechanism for coordinating the interests of the upper and lower levels is proposed,combined with factors such as the carbon emissions of the IIES,as well as the lower load interruption power.The price of selling energy can be dynamically adjusted to the lower LA in the mechanism,according to the information on carbon emissions and load interruption power.Mutual benefits and win-win situations are achieved between the upper and lower multistakeholders.Finally,CPLEX is used to iteratively solve the bilevel optimization model.The optimal solution is selected according to the joint optimal discrimination mechanism.Thesimulation results indicate that the sourceload coordinate operation can reduce the upper and lower operation costs.Using the proposed pricingmechanism,the carbon emissions and load interruption power of IEO-LA are reduced by 9.78%and 70.19%,respectively,and the capture power of the carbon capture equipment is improved by 36.24%.The validity of the proposed model and method is verified.展开更多
Safe and efficient sortie scheduling on the confined flight deck is crucial for maintaining high combat effectiveness of the aircraft carrier.The primary difficulty exactly lies in the spatiotemporal coordination,i.e....Safe and efficient sortie scheduling on the confined flight deck is crucial for maintaining high combat effectiveness of the aircraft carrier.The primary difficulty exactly lies in the spatiotemporal coordination,i.e.,allocation of limited supporting resources and collision-avoidance between heterogeneous dispatch entities.In this paper,the problem is investigated in the perspective of hybrid flow-shop scheduling problem by synthesizing the precedence,space and resource constraints.Specifically,eight processing procedures are abstracted,where tractors,preparing spots,catapults,and launching are virtualized as machines.By analyzing the constraints in sortie scheduling,a mixed-integer planning model is constructed.In particular,the constraint on preparing spot occupancy is improved to further enhance the sortie efficiency.The basic trajectory library for each dispatch entity is generated and a delayed strategy is integrated to address the collision-avoidance issue.To efficiently solve the formulated HFSP,which is essentially a combinatorial problem with tightly coupled constraints,a chaos-initialized genetic algorithm is developed.The solution framework is validated by the simulation environment referring to the Fort-class carrier,exhibiting higher sortie efficiency when compared to existing strategies.And animation of the simulation results is available at www.bilibili.com/video/BV14t421A7Tt/.The study presents a promising supporting technique for autonomous flight deck operation in the foreseeable future,and can be easily extended to other supporting scenarios,e.g.,ammunition delivery and aircraft maintenance.展开更多
The rapid advancement of Industry 4.0 has revolutionized manufacturing,shifting production from centralized control to decentralized,intelligent systems.Smart factories are now expected to achieve high adaptability an...The rapid advancement of Industry 4.0 has revolutionized manufacturing,shifting production from centralized control to decentralized,intelligent systems.Smart factories are now expected to achieve high adaptability and resource efficiency,particularly in mass customization scenarios where production schedules must accommodate dynamic and personalized demands.To address the challenges of dynamic task allocation,uncertainty,and realtime decision-making,this paper proposes Pathfinder,a deep reinforcement learning-based scheduling framework.Pathfinder models scheduling data through three key matrices:execution time(the time required for a job to complete),completion time(the actual time at which a job is finished),and efficiency(the performance of executing a single job).By leveraging neural networks,Pathfinder extracts essential features from these matrices,enabling intelligent decision-making in dynamic production environments.Unlike traditional approaches with fixed scheduling rules,Pathfinder dynamically selects from ten diverse scheduling rules,optimizing decisions based on real-time environmental conditions.To further enhance scheduling efficiency,a specialized reward function is designed to support dynamic task allocation and real-time adjustments.This function helps Pathfinder continuously refine its scheduling strategy,improving machine utilization and minimizing job completion times.Through reinforcement learning,Pathfinder adapts to evolving production demands,ensuring robust performance in real-world applications.Experimental results demonstrate that Pathfinder outperforms traditional scheduling approaches,offering improved coordination and efficiency in smart factories.By integrating deep reinforcement learning,adaptable scheduling strategies,and an innovative reward function,Pathfinder provides an effective solution to the growing challenges of multi-robot job scheduling in mass customization environments.展开更多
基金The National Natural Science Foundation of China (No.70971022,71271054)the Scientific Research Innovation Project for College Graduates in Jiangsu Province(No.CXLX_0157)the Scientific Research Foundation of the Education Department of Anhui Province(No.2011sk123)
文摘A single-machine scheduling with preventive periodic maintenance activities in a remanufacturing system including resumable and non-resumable jobs is studied.The objective is to find a schedule to minimize the makespan and an LPT-LS algorithm is proposed.Non-resumable jobs are first scheduled in a machine by the longest processing time（LPT） rule,and then resumable jobs are scheduled by the list scheduling（LS） rule.And the worst-case ratios of this algorithm in three different cases in terms of the value of the total processing time of the resumable jobs（denoted as S2） are discussed.When S2 is longer than the spare time of the machine after the non-resumable jobs are assigned by the LPT rule,it is equal to 1.When S2 falls in between the spare time of the machine by the LPT rule and the optimal schedule rule,it is less than 2.When S2 is less than the spare time of the machine by the optimal schedule rule,it is less than 2.Finally,numerical examples are presented for verification.
基金supported by National Natural Science Foundation of CHINA(No.70540024)Re-search Foundation of Ministry of Education of China(No.104107).
文摘Motivated by industrial applications we study a single-machine scheduling problem in which all the jobs are mutu-ally independent and available at time zero.The machine processes the jobs sequentially and it is not idle if there is any job to be pro-cessed.The operation of each job cannot be interrupted.The machine cannot process more than one job at a time.A setup time is needed if the machine switches from one type of job to another.The objective is to find an optimal schedule with the minimal total jobs’completion time.While the sum of jobs’processing time is always a constant,the objective is to minimize the sum of setup times.Ant colony optimization(ACO)is a meta-heuristic that has recently been applied to scheduling problem.In this paper we propose an improved ACO-Branching Ant Colony with Dynamic Perturbation(DPBAC)algorithm for the single-machine schedul-ing problem.DPBAC improves traditional ACO in following aspects:introducing Branching Method to choose starting points;im-proving state transition rules;introducing Mutation Method to shorten tours;improving pheromone updating rules and introduc-ing Conditional Dynamic Perturbation Strategy.Computational results show that DPBAC algorithm is superior to the traditional ACO algorithm.
文摘In this paper we consider a single-machine scheduling model with deteriorating jobs and simultaneous learning, and we introduce polynomial solutions for single machine makespan minimization, total flow times minimization and maximum lateness minimization corresponding to the first and second special cases of our model under some agreeable conditions. However, corresponding to the third special case of our model, we show that the optimal schedules may be different from those of the classical version for the above objective functions.
基金Sponsored by the National Natural Science Foundation of China(Grant No.70671040)and Specialized Research Fund for the Doctoral Program of High Education(Grant No.20050079008).
文摘In a CPM network, the longest path problem is one of the most important subjects. According to the intrinsic principle of CPM network, the length of the paths between arbitrary two nodes is presented. Furthermore, the length of the longest path from start node to arbitrary node and from arbitrary node to end node is proposed. In view of a scheduling problem of two activities with float in the CPM scheduling, we put forward Barycenter Theory and prove this theory based on the algorithm of the length of the longest path. By this theory, we know which activity should be done firstly. At last, we show our theory by an example.
基金supported by the National Nature Science Foundation of China(NSFC)with grant Nos:72091215/72091210,71921001 and 72022018,and Youth Innovation Promotion Association(Grant No.2021454).
文摘Additive manufacturing(AM)has attracted significant attention in recent years based on its wide range of applications and growing demand.AM offers the advantages of production flexibility and design freedom.In this study,we considered a practical variant of the batch-processing-machine(BPM)scheduling problem that arises in AM industries,where an AM machine can process multiple parts simultaneously,as long as the twodimensional rectangular packing constraint is not violated.Based on the set-partitioning formulation of our mixed-integer programming(MIP)model,a branch-and-price(B&P)algorithm was developed by embedding a column-generation technique into a branchand-bound framework.Additionally,a novel labelling algorithm was developed to accelerate the column-generation process.Ours is the first study to provide a B&P algorithm to solve the BPM scheduling problem in the AM industry.We tested the performance of our algorithm using a modern MIP solver(Gurobi)and real data from a 3D printing factory.The results demonstrate that for most instances tested,our algorithm produces results similar or identical to those of Gurobi with reasonable computation time and outperforms Gurobi in terms of solution quality and running time on some large instances.
基金supported by the National Natural Science Foundation of China under Grant Nos.62202192,71801218,and 72101094.
文摘In a local search algorithm,one of its most important features is the definition of its neighborhood which is crucial to the algorithm's performance.In this paper,we present an analysis of neighborhood combination search for solv-ing the single-machine scheduling problem with sequence-dependent setup time with the objective of minimizing total weighted tardiness(SMSWT).First,We propose a new neighborhood structure named Block Swap(B1)which can be con-sidered as an extension of the previously widely used Block Move(B2)neighborhood,and a fast incremental evaluation technique to enhance its evaluation efficiency.Second,based on the Block Swap and Block Move neighborhoods,we present two kinds of neighborhood structures:neighborhood union(denoted by B1UB2)and token-ring search(denoted by B1→B2),both of which are combinations of B1 and B2.Third,we incorporate the neighborhood union and token-ring search into two representative metaheuristic algorithms:the Iterated Local Search Algorithm(ILSnew)and the Hybrid Evolutionary Algorithm(HEA_(new))to investigate the performance of the neighborhood union and token-ring search.Exten-sive experiments show the competitiveness of the token-ring search combination mechanism of the two neighborhoods.Tested on the 120 public benchmark instances,our HEA_(new)has a highly competitive performance in solution quality and computational time compared with both the exact algorithms and recent metaheuristics.We have also tested the HEA,new algorithm with the selected neighborhood combination search to deal with the 64 public benchmark instances of the single-machine scheduling problem with sequence-dependent setup time.HEAnew is able to match the optimal or the best known results for all the 64 instances.In particular,the computational time for reaching the best well-known results for five chal-lenging instances is reduced by at least 61.25%.
基金supported by the National Natural Science Foundation of China(61374186)。
文摘In response to the challenges faced by unmanned swarms in mountain obstacle-breaching missions within complex terrains,such as poor task-resource coupling,lengthy solution generation times,and poor inter-platform collaboration,an unmanned swarm scheduling strategy tailored is proposed for mountain obstacle-breaching missions.Initially,by formalizing the descriptions of obstacle breaching operations,the swarm,and obstacle targets,an optimization model is constructed with the objectives of expected global benefit,timeliness,and task completion degree.A meta-task decomposition and reassembly strategy is then introduced to more precisely match the capabilities of unmanned platforms with task requirements.Additionally,a meta-task decomposition optimization model and a meta-task allocation operator are incorporated to achieve efficient allocation of swarm resources and collaborative scheduling.Simulation results demonstrate that the model can accurately generate reasonable and feasible obstacle breaching execution plans for unmanned swarms based on specific task requirements and environmental conditions.Moreover,compared to conventional strategies,the proposed strategy enhances task completion degree and expected returns while reducing the execution time of the plans.
文摘Task scheduling in cloud computing is a multi-objective optimization problem,often involving conflicting objectives such as minimizing execution time,reducing operational cost,and maximizing resource utilization.However,traditional approaches frequently rely on single-objective optimization methods which are insufficient for capturing the complexity of such problems.To address this limitation,we introduce MDMOSA(Multi-objective Dwarf Mongoose Optimization with Simulated Annealing),a hybrid that integrates multi-objective optimization for efficient task scheduling in Infrastructure-as-a-Service(IaaS)cloud environments.MDMOSA harmonizes the exploration capabilities of the biologically inspired Dwarf Mongoose Optimization(DMO)with the exploitation strengths of Simulated Annealing(SA),achieving a balanced search process.The algorithm aims to optimize task allocation by reducing makespan and financial cost while improving system resource utilization.We evaluate MDMOSA through extensive simulations using the real-world Google Cloud Jobs(GoCJ)dataset within the CloudSim environment.Comparative analysis against benchmarked algorithms such as SMOACO,MOTSGWO,and MFPAGWO reveals that MDMOSA consistently achieves superior performance in terms of scheduling efficiency,cost-effectiveness,and scalability.These results confirm the potential of MDMOSA as a robust and adaptable solution for resource scheduling in dynamic and heterogeneous cloud computing infrastructures.
文摘The proliferation of carrier aircraft and the integration of unmanned aerial vehicles(UAVs)on aircraft carriers present new challenges to the automation of launch and recovery operations.This paper investigates a collaborative scheduling problem inherent to the operational processes of carrier aircraft,where launch and recovery tasks are conducted concurrently on the flight deck.The objective is to minimize the cumulative weighted waiting time in the air for recovering aircraft and the cumulative weighted delay time for launching aircraft.To tackle this challenge,a multiple population self-adaptive differential evolution(MPSADE)algorithm is proposed.This method features a self-adaptive parameter updating mechanism that is contingent upon population diversity,an asynchronous updating scheme,an individual migration operator,and a global crossover mechanism.Additionally,comprehensive experiments are conducted to validate the effectiveness of the proposed model and algorithm.Ultimately,a comparative analysis with existing operation modes confirms the enhanced efficiency of the collaborative operation mode.
基金supported by the National Natural Science Foundation of China(Grant No.52475543)Natural Science Foundation of Henan(Grant No.252300421101)+1 种基金Henan Province University Science and Technology Innovation Talent Support Plan(Grant No.24HASTIT048)Science and Technology Innovation Team Project of Zhengzhou University of Light Industry(Grant No.23XNKJTD0101).
文摘Aircraft assembly is characterized by stringent precedence constraints,limited resource availability,spatial restrictions,and a high degree of manual intervention.These factors lead to considerable variability in operator workloads and significantly increase the complexity of scheduling.To address this challenge,this study investigates the Aircraft Pulsating Assembly Line Scheduling Problem(APALSP)under skilled operator allocation,with the objective of minimizing assembly completion time.A mathematical model considering skilled operator allocation is developed,and a Q-Learning improved Particle Swarm Optimization algorithm(QLPSO)is proposed.In the algorithm design,a reverse scheduling strategy is adopted to effectively manage large-scale precedence constraints.Moreover,a reverse sequence encoding method is introduced to generate operation sequences,while a time decoding mechanism is employed to determine completion times.The problem is further reformulated as a Markov Decision Process(MDP)with explicitly defined state and action spaces.Within QLPSO,the Q-learning mechanism adaptively adjusts inertia weights and learning factors,thereby achieving a balance between exploration capability and convergence performance.To validate the effectiveness of the proposed approach,extensive computational experiments are conducted on benchmark instances of different scales,including small,medium,large,and ultra-large cases.The results demonstrate that QLPSO consistently delivers stable and high-quality solutions across all scenarios.In ultra-large-scale instances,it improves the best solution by 25.2%compared with the Genetic Algorithm(GA)and enhances the average solution by 16.9%over the Q-learning algorithm,showing clear advantages over the comparative methods.These findings not only confirm the effectiveness of the proposed algorithm but also provide valuable theoretical references and practical guidance for the intelligent scheduling optimization of aircraft pulsating assembly lines.
基金funding from the European Commission by the Ruralities project(grant agreement no.101060876).
文摘In this paper,we propose a new privacy-aware transmission scheduling algorithm for 6G ad hoc networks.This system enables end nodes to select the optimum time and scheme to transmit private data safely.In 6G dynamic heterogeneous infrastructures,unstable links and non-uniform hardware capabilities create critical issues regarding security and privacy.Traditional protocols are often too computationally heavy to allow 6G services to achieve their expected Quality-of-Service(QoS).As the transport network is built of ad hoc nodes,there is no guarantee about their trustworthiness or behavior,and transversal functionalities are delegated to the extreme nodes.However,while security can be guaranteed in extreme-to-extreme solutions,privacy cannot,as all intermediate nodes still have to handle the data packets they are transporting.Besides,traditional schemes for private anonymous ad hoc communications are vulnerable against modern intelligent attacks based on learning models.The proposed scheme fulfills this gap.Findings show the probability of a successful intelligent attack reduces by up to 65%compared to ad hoc networks with no privacy protection strategy when used the proposed technology.While congestion probability can remain below 0.001%,as required in 6G services.
基金funded by National Key Research and Development Program Projects of China under Grant No.2020YFB1713500.
文摘To address the issue that hybrid flow shop production struggles to handle order disturbance events,a dynamic scheduling model was constructed.The model takes minimizing the maximum makespan,delivery time deviation,and scheme deviation degree as the optimization objectives.An adaptive dynamic scheduling strategy based on the degree of order disturbance is proposed.An improved multi-objective Grey Wolf(IMOGWO)optimization algorithm is designed by combining the“job-machine”two-layer encoding strategy,the timing-driven two-stage decoding strategy,the opposition-based learning initialization population strategy,the POX crossover strategy,the dualoperation dynamic mutation strategy,and the variable neighborhood search strategy for problem solving.A variety of test cases with different scales were designed,and ablation experiments were conducted to verify the effectiveness of the improved strategies.The results show that each improved strategy can effectively enhance the performance of the IMOGWO.Additionally,performance analysis was conducted by comparing the proposed algorithm with three mature and classical algorithms.The results demonstrate that the proposed algorithm exhibits superior performance in solving the hybrid flow-shop scheduling problem(HFSP).Case validations were conducted for different types of order disturbance scenarios.The results demonstrate that the proposed adaptive dynamic scheduling strategy and the IMOGWO algorithm can effectively address order disturbance events.They enable rapid response to order disturbance while ensuring the stability of the production system.
基金appreciation to the Princess Nourah bint Abdulrahman University Researchers Supporting Project number(PNURSP2025R384)Princess Nourah bint Abdulrahman University,Riyadh,Saudi Arabia.
文摘The cloud-fog computing paradigm has emerged as a novel hybrid computing model that integrates computational resources at both fog nodes and cloud servers to address the challenges posed by dynamic and heterogeneous computing networks.Finding an optimal computational resource for task offloading and then executing efficiently is a critical issue to achieve a trade-off between energy consumption and transmission delay.In this network,the task processed at fog nodes reduces transmission delay.Still,it increases energy consumption,while routing tasks to the cloud server saves energy at the cost of higher communication delay.Moreover,the order in which offloaded tasks are executed affects the system’s efficiency.For instance,executing lower-priority tasks before higher-priority jobs can disturb the reliability and stability of the system.Therefore,an efficient strategy of optimal computation offloading and task scheduling is required for operational efficacy.In this paper,we introduced a multi-objective and enhanced version of Cheeta Optimizer(CO),namely(MoECO),to jointly optimize the computation offloading and task scheduling in cloud-fog networks to minimize two competing objectives,i.e.,energy consumption and communication delay.MoECO first assigns tasks to the optimal computational nodes and then the allocated tasks are scheduled for processing based on the task priority.The mathematical modelling of CO needs improvement in computation time and convergence speed.Therefore,MoECO is proposed to increase the search capability of agents by controlling the search strategy based on a leader’s location.The adaptive step length operator is adjusted to diversify the solution and thus improves the exploration phase,i.e.,global search strategy.Consequently,this prevents the algorithm from getting trapped in the local optimal solution.Moreover,the interaction factor during the exploitation phase is also adjusted based on the location of the prey instead of the adjacent Cheetah.This increases the exploitation capability of agents,i.e.,local search capability.Furthermore,MoECO employs a multi-objective Pareto-optimal front to simultaneously minimize designated objectives.Comprehensive simulations in MATLAB demonstrate that the proposed algorithm obtains multiple solutions via a Pareto-optimal front and achieves an efficient trade-off between optimization objectives compared to baseline methods.
基金co-supported by the National Natural Science Foundation of China(Nos.62473110,62403166)the Fundamental Research Funds for the Central Universities,China(No.2023FRFK02043)+1 种基金the Natural Science Foundation of Heilongjiang Province,China(No.LH2022F023)the National Key Laboratory of Space Intelligent Control Foundation,China(No.2023-JCJQ-LB-006-19)。
文摘With the increasing number of geosynchronous orbit satellites with expiring lifetime,spacecraft refueling is crucial in enhancing the economic benefits of on-orbit services.The existing studies tend to be based on predetermined refueling duration;however,the precise mission scheduling solution will be difficult to apply due to uncertain refueling duration caused by orbital transfer deviations and stochastic actuator faults during actual on-orbit service.Therefore,this paper proposes a robust mission scheduling strategy for geosynchronous orbit spacecraft on-orbit refueling missions with uncertain refueling duration.Firstly,a robust mission scheduling model is constructed by introducing the budget uncertainty set to describe the uncertain refueling duration.Secondly,a hybrid harris hawks optimization algorithm is designed to explore the optimal mission allocation and refueling sequences,which combines cubic chaotic mapping to initialize the population,and the crossover in the genetic algorithm is introduced to enhance global convergence.Finally,the typical simulation examples are constructed with real-mission scenarios in three aspects to analyze:performance comparisons with various algorithms;robustness analyses via comparisons of different on-orbit refueling durations;investigations into the impacts of different initial population strategies on algorithm performance,demonstrating the proposed mission scheduling framework's robustness and effectiveness by comparing it with the exact mission scheduling.
基金This research was supported by the National Natural Science Foundation of China(No.11671368)the National Natural Science Foundation of Henan Province(No.15IRTSTHN006)The first author was also supported by the National Natural Science Foundation of Shandong Province(NZR2017MA031).
文摘We study single-machine scheduling problems with a single maintenance activity(MA)of length p0 under three types of assumptions:(A)the MA is required in a fixed time interval[T−p0,T]with T≥p0 and the job processing is of preemptive and resumable;(B)the MA is required in a relaxed time interval[0,T]with T≥p0 and the job processing is of nonpreemptive;(C)the MA is required in a relaxed time interval[T0,T]with 0≤T0≤T−p0 and the job processing is of nonpreemptive.We show in this paper that,up to the time complexity for solving scheduling problems,assumptions(A)and(B)are equivalent,and moreover,if T−(T0+p0)is greater than or equal to the maximum processing time of all jobs,the assumption(C)is also equivalent to(A)and(B).As an application,we study the scheduling for minimizing the weighted number of tardy jobs under the above three assumptions,respectively,and present corresponding time-complexity results.
基金Supported by National Natural Science Foundation of China(Grant Nos.12071442,11971443,12271491)。
文摘The single-machine lot scheduling problem with splittable jobs to minimize the number of tardy jobs has been showed to be weakly NP-hard in the literature.In this paper,we show that a generalized version of this problem in which jobs have deadlines is strongly NP-hard,and also present the results of some related scheduling problems.
基金supported by the National Natural Science Foundation of China(Nos.12271295 and 12001313)the Provincial Natural Science Foundation of Shandong(No.ZR2022MA019).
文摘In this paper,we consider the single-machine scheduling with step-deteriorating jobs and rejection.Each job is either rejected by paying a rejection penalty,or accepted and processed on the single machine,and the actual processing time of each accepted job is a step function of its starting time and the common deteriorating date.The objective is to minimize the makespan of the accepted jobs plus the total penalty of the rejected jobs.For the case of common deteriorating penalty,we first show that the problem is NP-hard in the ordinary sense.Then we present two pseudo-polynomial algorithms and a 2-approximation algorithm.Furthermore,we propose a fully polynomial time approximation scheme.For the case of common normal processing time,we present two pseudo-polynomial time algorithms,a 2-approximation algorithm and a fully polynomial time approximation scheme.
基金supported by the Central Government Guides Local Science and Technology Development Fund Project(2023ZY0020)Key R&D and Achievement Transformation Project in InnerMongolia Autonomous Region(2022YFHH0019)+3 种基金the Fundamental Research Funds for Inner Mongolia University of Science&Technology(2022053)Natural Science Foundation of Inner Mongolia(2022LHQN05002)National Natural Science Foundation of China(52067018)Metallurgical Engineering First-Class Discipline Construction Project in Inner Mongolia University of Science and Technology,Control Science and Engineering Quality Improvement and Cultivation Discipline Project in Inner Mongolia University of Science and Technology。
文摘In this paper,a bilevel optimization model of an integrated energy operator(IEO)–load aggregator(LA)is constructed to address the coordinate optimization challenge of multiple stakeholder island integrated energy system(IIES).The upper level represents the integrated energy operator,and the lower level is the electricity-heatgas load aggregator.Owing to the benefit conflict between the upper and lower levels of the IIES,a dynamic pricing mechanism for coordinating the interests of the upper and lower levels is proposed,combined with factors such as the carbon emissions of the IIES,as well as the lower load interruption power.The price of selling energy can be dynamically adjusted to the lower LA in the mechanism,according to the information on carbon emissions and load interruption power.Mutual benefits and win-win situations are achieved between the upper and lower multistakeholders.Finally,CPLEX is used to iteratively solve the bilevel optimization model.The optimal solution is selected according to the joint optimal discrimination mechanism.Thesimulation results indicate that the sourceload coordinate operation can reduce the upper and lower operation costs.Using the proposed pricingmechanism,the carbon emissions and load interruption power of IEO-LA are reduced by 9.78%and 70.19%,respectively,and the capture power of the carbon capture equipment is improved by 36.24%.The validity of the proposed model and method is verified.
基金the financial support of the National Key Research and Development Plan(2021YFB3302501)the financial support of the National Natural Science Foundation of China(12102077)。
文摘Safe and efficient sortie scheduling on the confined flight deck is crucial for maintaining high combat effectiveness of the aircraft carrier.The primary difficulty exactly lies in the spatiotemporal coordination,i.e.,allocation of limited supporting resources and collision-avoidance between heterogeneous dispatch entities.In this paper,the problem is investigated in the perspective of hybrid flow-shop scheduling problem by synthesizing the precedence,space and resource constraints.Specifically,eight processing procedures are abstracted,where tractors,preparing spots,catapults,and launching are virtualized as machines.By analyzing the constraints in sortie scheduling,a mixed-integer planning model is constructed.In particular,the constraint on preparing spot occupancy is improved to further enhance the sortie efficiency.The basic trajectory library for each dispatch entity is generated and a delayed strategy is integrated to address the collision-avoidance issue.To efficiently solve the formulated HFSP,which is essentially a combinatorial problem with tightly coupled constraints,a chaos-initialized genetic algorithm is developed.The solution framework is validated by the simulation environment referring to the Fort-class carrier,exhibiting higher sortie efficiency when compared to existing strategies.And animation of the simulation results is available at www.bilibili.com/video/BV14t421A7Tt/.The study presents a promising supporting technique for autonomous flight deck operation in the foreseeable future,and can be easily extended to other supporting scenarios,e.g.,ammunition delivery and aircraft maintenance.
基金supported by National Natural Science Foundation of China under Grant No.62372110Fujian Provincial Natural Science of Foundation under Grants 2023J02008,2024H0009.
文摘The rapid advancement of Industry 4.0 has revolutionized manufacturing,shifting production from centralized control to decentralized,intelligent systems.Smart factories are now expected to achieve high adaptability and resource efficiency,particularly in mass customization scenarios where production schedules must accommodate dynamic and personalized demands.To address the challenges of dynamic task allocation,uncertainty,and realtime decision-making,this paper proposes Pathfinder,a deep reinforcement learning-based scheduling framework.Pathfinder models scheduling data through three key matrices:execution time(the time required for a job to complete),completion time(the actual time at which a job is finished),and efficiency(the performance of executing a single job).By leveraging neural networks,Pathfinder extracts essential features from these matrices,enabling intelligent decision-making in dynamic production environments.Unlike traditional approaches with fixed scheduling rules,Pathfinder dynamically selects from ten diverse scheduling rules,optimizing decisions based on real-time environmental conditions.To further enhance scheduling efficiency,a specialized reward function is designed to support dynamic task allocation and real-time adjustments.This function helps Pathfinder continuously refine its scheduling strategy,improving machine utilization and minimizing job completion times.Through reinforcement learning,Pathfinder adapts to evolving production demands,ensuring robust performance in real-world applications.Experimental results demonstrate that Pathfinder outperforms traditional scheduling approaches,offering improved coordination and efficiency in smart factories.By integrating deep reinforcement learning,adaptable scheduling strategies,and an innovative reward function,Pathfinder provides an effective solution to the growing challenges of multi-robot job scheduling in mass customization environments.
