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.展开更多
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.展开更多
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 i...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.展开更多
We study the single-machine scheduling with maintenance intervals under preemptive pattern and resumable pattern,respectively,to minimize the total weighted late work and the weighted number of tardy jobs,respectively...We study the single-machine scheduling with maintenance intervals under preemptive pattern and resumable pattern,respectively,to minimize the total weighted late work and the weighted number of tardy jobs,respectively,where each job has a release date and a due date.According to the different combinations of the two scheduling patterns and the two scheduling criteria,six scheduling problems(including two Pareto-scheduling problems)are studied in this paper.We show that by modifying the release dates and the due dates,the six problems can be reduced to their corresponding scheduling problems without maintenance intervals in quasi-linear time.As a consequence,complexity results of our problems can be directly obtained from the known results in the literature.In particular,for the problem under resumable pattern to minimize the total weighted late work with all the jobs being released at time O,an O(mn^(2)P)-time algorithm was presented in the literature,where m is the number of maintenance intervals,n is the number of jobs,and P is the total processing time of the jobs;and our research shows that the same problem is solvable in O(n^(2)p+m log m)time,improving this known result.展开更多
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 this paper, a single-machine scheduling model with a given common due date is considered. Job processing time is a linear decreasing function of its starting time. The objective function is to minimize the total we...In this paper, a single-machine scheduling model with a given common due date is considered. Job processing time is a linear decreasing function of its starting time. The objective function is to minimize the total weighted earliness award and tardiness penalty. Our aim is to find an optimal schedule so as to minimize the objective function. As the problem is NP-hard, some properties and polynomial time solvable cases of this problem are given. A dynamic programming algorithm for the general case of the problem is provided.展开更多
A new chaotic particle swarm algorithm is proposed in order to avoid the premature convergence of the particle swarm optimization and the shortcomings of the chaotic optimization, such as slow searching speed and low ...A new chaotic particle swarm algorithm is proposed in order to avoid the premature convergence of the particle swarm optimization and the shortcomings of the chaotic optimization, such as slow searching speed and low accuracy when used in the multivariable systems or in large search space. The new algorithm combines the particle swarm algorithm and the chaotic optimization, using randomness and ergodicity of chaos to overcome the premature convergence of the particle swarm optimization. At the same time, a new neural network feedback linearization control system is built to control the single-machine infinite-bus system. The network parameters are trained by the chaos particle swarm algorithm, which makes the control achieve optimization and the control law of prime mover output torque obtained. Finally, numerical simulation and practical application validate the effectiveness of the method.展开更多
In DC power systems dominated by power electronic devices,constant power loads(CPLs)and saturation components significantly impact large-signal stability.During the large-signal stability analysis process,the presence...In DC power systems dominated by power electronic devices,constant power loads(CPLs)and saturation components significantly impact large-signal stability.During the large-signal stability analysis process,the presence of multiple state variables and high-order system poses substantial challenges.To address this,considering the complete control dynamics,this paper proposes an equivalent single-machine(ESM)model of the droop-based DC power systems to reduce the complexity of the large-signal analysis.Building on the proposed ESM model,considering the dynamics of CPL and saturation constraints,a region of attraction(ROA)estimation algorithm based on sum of squares(SOS)programming is proposed,which significantly reduces the conservativeness compared with other existing methods.Furthermore,a control parameter optimization algorithm based on SOS programming is proposed with the aim of expanding the ROA.Furthermgre,with the aim of expanding the ROA,controller sythesis is conducted with proposed control parameter optimization algorithm based on SOS programming.Ultimately,simulation experiments validate the accuracy of the proposed ESM model and the proposed ROA estimation algorithm,as well as the effectiveness of the control parameter optimization algorithm.展开更多
基金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.
文摘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.
文摘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.
基金supported by the National Natural Science Foundation of China(Nos.12071442 and 12201186).
文摘We study the single-machine scheduling with maintenance intervals under preemptive pattern and resumable pattern,respectively,to minimize the total weighted late work and the weighted number of tardy jobs,respectively,where each job has a release date and a due date.According to the different combinations of the two scheduling patterns and the two scheduling criteria,six scheduling problems(including two Pareto-scheduling problems)are studied in this paper.We show that by modifying the release dates and the due dates,the six problems can be reduced to their corresponding scheduling problems without maintenance intervals in quasi-linear time.As a consequence,complexity results of our problems can be directly obtained from the known results in the literature.In particular,for the problem under resumable pattern to minimize the total weighted late work with all the jobs being released at time O,an O(mn^(2)P)-time algorithm was presented in the literature,where m is the number of maintenance intervals,n is the number of jobs,and P is the total processing time of the jobs;and our research shows that the same problem is solvable in O(n^(2)p+m log m)time,improving this known result.
基金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%.
文摘In this paper, a single-machine scheduling model with a given common due date is considered. Job processing time is a linear decreasing function of its starting time. The objective function is to minimize the total weighted earliness award and tardiness penalty. Our aim is to find an optimal schedule so as to minimize the objective function. As the problem is NP-hard, some properties and polynomial time solvable cases of this problem are given. A dynamic programming algorithm for the general case of the problem is provided.
基金This work is supported by National Natural Science Foundation of China （50776005）.
文摘A new chaotic particle swarm algorithm is proposed in order to avoid the premature convergence of the particle swarm optimization and the shortcomings of the chaotic optimization, such as slow searching speed and low accuracy when used in the multivariable systems or in large search space. The new algorithm combines the particle swarm algorithm and the chaotic optimization, using randomness and ergodicity of chaos to overcome the premature convergence of the particle swarm optimization. At the same time, a new neural network feedback linearization control system is built to control the single-machine infinite-bus system. The network parameters are trained by the chaos particle swarm algorithm, which makes the control achieve optimization and the control law of prime mover output torque obtained. Finally, numerical simulation and practical application validate the effectiveness of the method.
基金supported by National Natural Science Foundation of China(No.52077194).
文摘In DC power systems dominated by power electronic devices,constant power loads(CPLs)and saturation components significantly impact large-signal stability.During the large-signal stability analysis process,the presence of multiple state variables and high-order system poses substantial challenges.To address this,considering the complete control dynamics,this paper proposes an equivalent single-machine(ESM)model of the droop-based DC power systems to reduce the complexity of the large-signal analysis.Building on the proposed ESM model,considering the dynamics of CPL and saturation constraints,a region of attraction(ROA)estimation algorithm based on sum of squares(SOS)programming is proposed,which significantly reduces the conservativeness compared with other existing methods.Furthermore,a control parameter optimization algorithm based on SOS programming is proposed with the aim of expanding the ROA.Furthermgre,with the aim of expanding the ROA,controller sythesis is conducted with proposed control parameter optimization algorithm based on SOS programming.Ultimately,simulation experiments validate the accuracy of the proposed ESM model and the proposed ROA estimation algorithm,as well as the effectiveness of the control parameter optimization algorithm.
