To solve the sparse reward problem of job-shop scheduling by deep reinforcement learning,a deep reinforcement learning framework considering sparse reward problem is proposed.The job shop scheduling problem is transfo...To solve the sparse reward problem of job-shop scheduling by deep reinforcement learning,a deep reinforcement learning framework considering sparse reward problem is proposed.The job shop scheduling problem is transformed into Markov decision process,and six state features are designed to improve the state feature representation by using two-way scheduling method,including four state features that distinguish the optimal action and two state features that are related to the learning goal.An extended variant of graph isomorphic network GIN++is used to encode disjunction graphs to improve the performance and generalization ability of the model.Through iterative greedy algorithm,random strategy is generated as the initial strategy,and the action with the maximum information gain is selected to expand it to optimize the exploration ability of Actor-Critic algorithm.Through validation of the trained policy model on multiple public test data sets and comparison with other advanced DRL methods and scheduling rules,the proposed method reduces the minimum average gap by 3.49%,5.31%and 4.16%,respectively,compared with the priority rule-based method,and 5.34%compared with the learning-based method.11.97%and 5.02%,effectively improving the accuracy of DRL to solve the approximate solution of JSSP minimum completion time.展开更多
The meta-heuristic algorithm with local search is an excellent choice for the job-shop scheduling problem(JSP).However,due to the unique nature of the JSP,local search may generate infeasible neighbourhood solutions.I...The meta-heuristic algorithm with local search is an excellent choice for the job-shop scheduling problem(JSP).However,due to the unique nature of the JSP,local search may generate infeasible neighbourhood solutions.In the existing literature,although some domain knowledge of the JSP can be used to avoid infeasible solutions,the constraint conditions in this domain knowledge are sufficient but not necessary.It may lose many feasible solutions and make the local search inadequate.By analysing the causes of infeasible neighbourhood solutions,this paper further explores the domain knowledge contained in the JSP and proposes the sufficient and necessary constraint conditions to find all feasible neighbourhood solutions,allowing the local search to be carried out thoroughly.With the proposed conditions,a new neighbourhood structure is designed in this paper.Then,a fast calculation method for all feasible neighbourhood solutions is provided,significantly reducing the calculation time compared with ordinary methods.A set of standard benchmark instances is used to evaluate the performance of the proposed neighbourhood structure and calculation method.The experimental results show that the calculation method is effective,and the new neighbourhood structure has more reliability and superiority than the other famous and influential neighbourhood structures,where 90%of the results are the best compared with three other well-known neighbourhood structures.Finally,the result from a tabu search algorithm with the new neighbourhood structure is compared with the current best results,demonstrating the superiority of the proposed neighbourhood structure.展开更多
The fuzzy goal flexible job-shop scheduling problem (FGFJSP) is the extension of FJSP. Compared with the convention JSP, it can solve the fuzzy goal problem and meet suit requirements of the key job. The multi-objec...The fuzzy goal flexible job-shop scheduling problem (FGFJSP) is the extension of FJSP. Compared with the convention JSP, it can solve the fuzzy goal problem and meet suit requirements of the key job. The multi-object problem, such as the fuzzy cost, the fuzzy due-date, and the fuzzy makespan, etc, can be solved by FGFJSP. To optimize FGFJSP, an individual optimization and colony diversity genetic algorithm (IOCDGA) is presented to accelerate the convergence speed and to avoid the earliness. In IOCDGA, the colony average distance and the colony entropy are defined after the definition of the encoding model. The colony diversity is expressed by the colony average distance and the colony entropy. The crossover probability and the mutation probability are controlled by the colony diversity. The evolution emphasizes that sigle individual or a few individuals evolve into the best in IOCDGA, but not the all in classical GA. Computational results show that the algorithm is applicable and the number of iterations is less.展开更多
In the flexible job-shop scheduling problem (FJSP), each operation has to be assigned to a machine from a set of capable machines before alocating the assigned operations on all machines. To solve the multi-objectiv...In the flexible job-shop scheduling problem (FJSP), each operation has to be assigned to a machine from a set of capable machines before alocating the assigned operations on all machines. To solve the multi-objective FJSP, the Grantt graph oriented string representation (GOSR) and the basic manipulation of the genetic algorithm operator are presented. An integrated operator genetic algorithm (IOGA) and its process are described. Comparison between computational results and the latest research shows that the proposed algorithm is effective in reducing the total workload of all machines, the makespan and the critical machine workload.展开更多
An improved adaptive particle swarm optimization(IAPSO)algorithm is presented for solving the minimum makespan problem of job shop scheduling problem(JSP).Inspired by hormone modulation mechanism,an adaptive hormonal ...An improved adaptive particle swarm optimization(IAPSO)algorithm is presented for solving the minimum makespan problem of job shop scheduling problem(JSP).Inspired by hormone modulation mechanism,an adaptive hormonal factor(HF),composed of an adaptive local hormonal factor(H l)and an adaptive global hormonal factor(H g),is devised to strengthen the information connection between particles.Using HF,each particle of the swarm can adjust its position self-adaptively to avoid premature phenomena and reach better solution.The computational results validate the effectiveness and stability of the proposed IAPSO,which can not only find optimal or close-to-optimal solutions but also obtain both better and more stability results than the existing particle swarm optimization(PSO)algorithms.展开更多
This paper presents a new genetic algorithm for job-shop scheduling problem. Based on schema theorem and building block hypothesis, a new crossover is proposed. By selecting short, low-order, highly fit schemas for ge...This paper presents a new genetic algorithm for job-shop scheduling problem. Based on schema theorem and building block hypothesis, a new crossover is proposed. By selecting short, low-order, highly fit schemas for genetic operator, the crossover can maintain a diversity of population without disrupting the characteristics and search the global optimization. Simulation results on famous benchmark problems MT06, MT10 and MT20 coded by Matlab show that our genetic operators are suitable to job-shop scheduling problems and outperform the previous GA-based approaches.展开更多
In this paper, we propose a new genetic algorithm for job-shop scheduling problems (JSP). The proposed method uses the operation-based representation, based on schema theorem and building block hypothesis, a new cro...In this paper, we propose a new genetic algorithm for job-shop scheduling problems (JSP). The proposed method uses the operation-based representation, based on schema theorem and building block hypothesis, a new crossover is proposed : By selecting short, low order highly fit schemas to genetic operator, the crossover can exchange meaningful ordering information of parents effectively and can search the global optimization. Simulation results on MT benchmark problem coded by C + + show that our genetic operators are very powerful and suitable to job-shop scheduling problems and our method outperforms the previous GA-based approaches.展开更多
The traditional production planning and scheduling problems consider performance indicators like time, cost and quality as optimization objectives in manufacturing processes. However, environmentally-friendly factors ...The traditional production planning and scheduling problems consider performance indicators like time, cost and quality as optimization objectives in manufacturing processes. However, environmentally-friendly factors like energy consumption of production have not been completely taken into consideration. Against this background, this paper addresses an approach to modify a given schedule generated by a production plarming and scheduling system in a job shop floor, where machine tools can work at different cutting speeds. It can adjust the cutting speeds of the operations while keeping the original assignment and processing sequence of operations of each job fixed in order to obtain energy savings. First, the proposed approach, based on a mixed integer programming mathematical model, changes the total idle time of the given schedule to minimize energy consumption in the job shop floor while accepting the optimal solution of the scheduling objective, makespan. Then, a genetic-simulated annealing algorithm is used to explore the optimal solution due to the fact that the problem is strongly NP-hard. Finally, the effectiveness of the approach is performed small- and large-size instances, respectively. The experimental results show that the approach can save 5%-10% of the average energy consumption while accepting the optimal solution of the makespan in small-size instances. In addition, the average maximum energy saving ratio can reach to 13%. And it can save approximately 1%-4% of the average energy consumption and approximately 2.4% of the average maximum energy while accepting the near-optimal solution of the makespan in large-size instances. The proposed research provides an interesting point to explore an energy-aware schedule optimization for a traditional production planning and scheduling problem.展开更多
The issue of reducing energy consumption for the job-shop scheduling problem in machining systems is addressed, whose dual objectives are to minimize both the energy consumption and the makespan. First, the bi- object...The issue of reducing energy consumption for the job-shop scheduling problem in machining systems is addressed, whose dual objectives are to minimize both the energy consumption and the makespan. First, the bi- objective model for the job-shop scheduling problem is proposed. The objective function value of the model represents synthesized optimization of energy consumption and makespan. Then, a heuristic algorithm is developed to locate the optimal or near optimal solutions of the model based on the Tabu search mechanism. Finally, the experimental case is presented to demonstrate the effectiveness of the proposed model and the algorithm.展开更多
A modified bottleneck-based (MB) heuristic for large-scale job-shop scheduling problems with a welldefined bottleneck is suggested, which is simpler but more tailored than the shifting bottleneck (SB) procedure. I...A modified bottleneck-based (MB) heuristic for large-scale job-shop scheduling problems with a welldefined bottleneck is suggested, which is simpler but more tailored than the shifting bottleneck (SB) procedure. In this algorithm, the bottleneck is first scheduled optimally while the non-bottleneck machines are subordinated around the solutions of the bottleneck schedule by some effective dispatching rules. Computational results indicate that the MB heuristic can achieve a better tradeoff between solution quality and computational time compared to SB procedure for medium-size problems. Furthermore, it can obtain a good solution in a short time for large-scale jobshop scheduling problems.展开更多
The technology of production planning and scheduling is one of the critical technologies that decide whether the automated manufacturing systems can get the expected economy. Job shop scheduling belongs to the special...The technology of production planning and scheduling is one of the critical technologies that decide whether the automated manufacturing systems can get the expected economy. Job shop scheduling belongs to the special class of NP-hard problems. Most of the algorithms used to optimize this class of problems have an exponential time; that is, the computation time increases exponentially with problem size. In scheduling study, makespan is often considered as the main objective. In this paper, makespan, the due date request of the key jobs, the availability of the key machine, the average wait-time of the jobs, and the similarities between the jobs and so on are taken into account based on the application of mechanical engineering. The job shop scheduling problem with multi-objectives is analyzed and studied by using genetic algorithms based on the mechanics of genetics and natural selection. In this research, the tactics of the coding and decoding and the design of the genetic operators, along with the description of the mathematic model of the multi-objective functions, are presented. Finally an illu-strative example is given to testify the validity of this algorithm.展开更多
Time-Sensitive Network(TSN)with deterministic transmission capability is increasingly used in many emerging fields.It mainly guarantees the Quality of Service(QoS)of applications with strict requirements on time and s...Time-Sensitive Network(TSN)with deterministic transmission capability is increasingly used in many emerging fields.It mainly guarantees the Quality of Service(QoS)of applications with strict requirements on time and security.One of the core features of TSN is traffic scheduling with bounded low delay in the network.However,traffic scheduling schemes in TSN are usually synthesized offline and lack dynamism.To implement incremental scheduling of newly arrived traffic in TSN,we propose a Dynamic Response Incremental Scheduling(DR-IS)method for time-sensitive traffic and deploy it on a software-defined time-sensitive network architecture.Under the premise of meeting the traffic scheduling requirements,we adopt two modes,traffic shift and traffic exchange,to dynamically adjust the time slot injection position of the traffic in the original scheme,and determine the sending offset time of the new timesensitive traffic to minimize the global traffic transmission jitter.The evaluation results show that DRIS method can effectively control the large increase of traffic transmission jitter in incremental scheduling without affecting the transmission delay,thus realizing the dynamic incremental scheduling of time-sensitive traffic in TSN.展开更多
The distributed flexible job shop scheduling problem(DFJSP)has attracted great attention with the growth of the global manufacturing industry.General DFJSP research only considers machine constraints and ignores worke...The distributed flexible job shop scheduling problem(DFJSP)has attracted great attention with the growth of the global manufacturing industry.General DFJSP research only considers machine constraints and ignores worker constraints.As one critical factor of production,effective utilization of worker resources can increase productivity.Meanwhile,energy consumption is a growing concern due to the increasingly serious environmental issues.Therefore,the distributed flexible job shop scheduling problem with dual resource constraints(DFJSP-DRC)for minimizing makespan and total energy consumption is studied in this paper.To solve the problem,we present a multi-objective mathematical model for DFJSP-DRC and propose a Q-learning-based multi-objective grey wolf optimizer(Q-MOGWO).In Q-MOGWO,high-quality initial solutions are generated by a hybrid initialization strategy,and an improved active decoding strategy is designed to obtain the scheduling schemes.To further enhance the local search capability and expand the solution space,two wolf predation strategies and three critical factory neighborhood structures based on Q-learning are proposed.These strategies and structures enable Q-MOGWO to explore the solution space more efficiently and thus find better Pareto solutions.The effectiveness of Q-MOGWO in addressing DFJSP-DRC is verified through comparison with four algorithms using 45 instances.The results reveal that Q-MOGWO outperforms comparison algorithms in terms of solution quality.展开更多
In recent years, target tracking has been considered one of the most important applications of wireless sensornetwork (WSN). Optimizing target tracking performance and prolonging network lifetime are two equally criti...In recent years, target tracking has been considered one of the most important applications of wireless sensornetwork (WSN). Optimizing target tracking performance and prolonging network lifetime are two equally criticalobjectives in this scenario. The existing mechanisms still have weaknesses in balancing the two demands. Theproposed heuristic multi-node collaborative scheduling mechanism (HMNCS) comprises cluster head (CH)election, pre-selection, and task set selectionmechanisms, where the latter two kinds of selections forma two-layerselection mechanism. The CH election innovatively introduces the movement trend of the target and establishesa scoring mechanism to determine the optimal CH, which can delay the CH rotation and thus reduce energyconsumption. The pre-selection mechanism adaptively filters out suitable nodes as the candidate task set to applyfor tracking tasks, which can reduce the application consumption and the overhead of the following task setselection. Finally, the task node selection is mathematically transformed into an optimization problem and thegenetic algorithm is adopted to form a final task set in the task set selection mechanism. Simulation results showthat HMNCS outperforms other compared mechanisms in the tracking accuracy and the network lifetime.展开更多
As cloud quantum computing gains broader acceptance,a growing quantity of researchers are directing their focus towards this domain.Nevertheless,the rapid surge in demand for cloud-based quantum computing resources ha...As cloud quantum computing gains broader acceptance,a growing quantity of researchers are directing their focus towards this domain.Nevertheless,the rapid surge in demand for cloud-based quantum computing resources has led to a scarcity,which in turn hampers users from achieving optimal satisfaction.Therefore,cloud quantum computing service providers require a unified analysis and scheduling framework for their quantumresources and user jobs to meet the ever-growing usage demands.This paper introduces a new multi-programming scheduling framework for quantum computing in a cloud environment.The framework addresses the issue of limited quantum computing resources in cloud environments and ensures a satisfactory user experience.It introduces three innovative designs:1)Our framework automatically allocates tasks to different quantum backends while ensuring fairness among users by considering both the cloud-based quantum resources and the user-submitted tasks.2)Multi-programming mechanism is employed across different quantum backends to enhance the overall throughput of the quantum cloud.In comparison to conventional task schedulers,our proposed framework achieves a throughput improvement of more than two-fold in the quantum cloud.3)The framework can balance fidelity and user waiting time by adaptively adjusting scheduling parameters.展开更多
In current research on task offloading and resource scheduling in vehicular networks,vehicles are commonly assumed to maintain constant speed or relatively stationary states,and the impact of speed variations on task ...In current research on task offloading and resource scheduling in vehicular networks,vehicles are commonly assumed to maintain constant speed or relatively stationary states,and the impact of speed variations on task offloading is often overlooked.It is frequently assumed that vehicles can be accurately modeled during actual motion processes.However,in vehicular dynamic environments,both the tasks generated by the vehicles and the vehicles’surroundings are constantly changing,making it difficult to achieve real-time modeling for actual dynamic vehicular network scenarios.Taking into account the actual dynamic vehicular scenarios,this paper considers the real-time non-uniform movement of vehicles and proposes a vehicular task dynamic offloading and scheduling algorithm for single-task multi-vehicle vehicular network scenarios,attempting to solve the dynamic decision-making problem in task offloading process.The optimization objective is to minimize the average task completion time,which is formulated as a multi-constrained non-linear programming problem.Due to the mobility of vehicles,a constraint model is applied in the decision-making process to dynamically determine whether the communication range is sufficient for task offloading and transmission.Finally,the proposed vehicular task dynamic offloading and scheduling algorithm based on muti-agent deep deterministic policy gradient(MADDPG)is applied to solve the optimal solution of the optimization problem.Simulation results show that the algorithm proposed in this paper is able to achieve lower latency task computation offloading.Meanwhile,the average task completion time of the proposed algorithm in this paper can be improved by 7.6%compared to the performance of the MADDPG scheme and 51.1%compared to the performance of deep deterministic policy gradient(DDPG).展开更多
Currently,applications accessing remote computing resources through cloud data centers is the main mode of operation,but this mode of operation greatly increases communication latency and reduces overall quality of se...Currently,applications accessing remote computing resources through cloud data centers is the main mode of operation,but this mode of operation greatly increases communication latency and reduces overall quality of service(QoS)and quality of experience(QoE).Edge computing technology extends cloud service functionality to the edge of the mobile network,closer to the task execution end,and can effectivelymitigate the communication latency problem.However,the massive and heterogeneous nature of servers in edge computing systems brings new challenges to task scheduling and resource management,and the booming development of artificial neural networks provides us withmore powerfulmethods to alleviate this limitation.Therefore,in this paper,we proposed a time series forecasting model incorporating Conv1D,LSTM and GRU for edge computing device resource scheduling,trained and tested the forecasting model using a small self-built dataset,and achieved competitive experimental results.展开更多
Cloud service providers generally co-locate online services and batch jobs onto the same computer cluster,where the resources can be pooled in order to maximize data center resource utilization.Due to resource competi...Cloud service providers generally co-locate online services and batch jobs onto the same computer cluster,where the resources can be pooled in order to maximize data center resource utilization.Due to resource competition between batch jobs and online services,co-location frequently impairs the performance of online services.This study presents a quality of service(QoS)prediction-based schedulingmodel(QPSM)for co-locatedworkloads.The performance prediction of QPSM consists of two parts:the prediction of an online service’s QoS anomaly based on XGBoost and the prediction of the completion time of an offline batch job based on randomforest.On-line service QoS anomaly prediction is used to evaluate the influence of batch jobmix on on-line service performance,and batch job completion time prediction is utilized to reduce the total waiting time of batch jobs.When the same number of batch jobs are scheduled in experiments using typical test sets such as CloudSuite,the scheduling time required by QPSM is reduced by about 6 h on average compared with the first-come,first-served strategy and by about 11 h compared with the random scheduling strategy.Compared with the non-co-located situation,QPSM can improve CPU resource utilization by 12.15% and memory resource utilization by 5.7% on average.Experiments show that the QPSM scheduling strategy proposed in this study can effectively guarantee the quality of online services and further improve cluster resource utilization.展开更多
基金Shaanxi Provincial Key Research and Development Project(2023YBGY095)and Shaanxi Provincial Qin Chuangyuan"Scientist+Engineer"project(2023KXJ247)Fund support.
文摘To solve the sparse reward problem of job-shop scheduling by deep reinforcement learning,a deep reinforcement learning framework considering sparse reward problem is proposed.The job shop scheduling problem is transformed into Markov decision process,and six state features are designed to improve the state feature representation by using two-way scheduling method,including four state features that distinguish the optimal action and two state features that are related to the learning goal.An extended variant of graph isomorphic network GIN++is used to encode disjunction graphs to improve the performance and generalization ability of the model.Through iterative greedy algorithm,random strategy is generated as the initial strategy,and the action with the maximum information gain is selected to expand it to optimize the exploration ability of Actor-Critic algorithm.Through validation of the trained policy model on multiple public test data sets and comparison with other advanced DRL methods and scheduling rules,the proposed method reduces the minimum average gap by 3.49%,5.31%and 4.16%,respectively,compared with the priority rule-based method,and 5.34%compared with the learning-based method.11.97%and 5.02%,effectively improving the accuracy of DRL to solve the approximate solution of JSSP minimum completion time.
基金Supported by National Natural Science Foundation of China(Grant Nos.U21B2029 and 51825502).
文摘The meta-heuristic algorithm with local search is an excellent choice for the job-shop scheduling problem(JSP).However,due to the unique nature of the JSP,local search may generate infeasible neighbourhood solutions.In the existing literature,although some domain knowledge of the JSP can be used to avoid infeasible solutions,the constraint conditions in this domain knowledge are sufficient but not necessary.It may lose many feasible solutions and make the local search inadequate.By analysing the causes of infeasible neighbourhood solutions,this paper further explores the domain knowledge contained in the JSP and proposes the sufficient and necessary constraint conditions to find all feasible neighbourhood solutions,allowing the local search to be carried out thoroughly.With the proposed conditions,a new neighbourhood structure is designed in this paper.Then,a fast calculation method for all feasible neighbourhood solutions is provided,significantly reducing the calculation time compared with ordinary methods.A set of standard benchmark instances is used to evaluate the performance of the proposed neighbourhood structure and calculation method.The experimental results show that the calculation method is effective,and the new neighbourhood structure has more reliability and superiority than the other famous and influential neighbourhood structures,where 90%of the results are the best compared with three other well-known neighbourhood structures.Finally,the result from a tabu search algorithm with the new neighbourhood structure is compared with the current best results,demonstrating the superiority of the proposed neighbourhood structure.
文摘The fuzzy goal flexible job-shop scheduling problem (FGFJSP) is the extension of FJSP. Compared with the convention JSP, it can solve the fuzzy goal problem and meet suit requirements of the key job. The multi-object problem, such as the fuzzy cost, the fuzzy due-date, and the fuzzy makespan, etc, can be solved by FGFJSP. To optimize FGFJSP, an individual optimization and colony diversity genetic algorithm (IOCDGA) is presented to accelerate the convergence speed and to avoid the earliness. In IOCDGA, the colony average distance and the colony entropy are defined after the definition of the encoding model. The colony diversity is expressed by the colony average distance and the colony entropy. The crossover probability and the mutation probability are controlled by the colony diversity. The evolution emphasizes that sigle individual or a few individuals evolve into the best in IOCDGA, but not the all in classical GA. Computational results show that the algorithm is applicable and the number of iterations is less.
文摘In the flexible job-shop scheduling problem (FJSP), each operation has to be assigned to a machine from a set of capable machines before alocating the assigned operations on all machines. To solve the multi-objective FJSP, the Grantt graph oriented string representation (GOSR) and the basic manipulation of the genetic algorithm operator are presented. An integrated operator genetic algorithm (IOGA) and its process are described. Comparison between computational results and the latest research shows that the proposed algorithm is effective in reducing the total workload of all machines, the makespan and the critical machine workload.
基金Supported by the National Natural Science Foundation of China(51175262)the Research Fund for Doctoral Program of Higher Education of China(20093218110020)+2 种基金the Jiangsu Province Science Foundation for Excellent Youths(BK201210111)the Jiangsu Province Industry-Academy-Research Grant(BY201220116)the Innovative and Excellent Foundation for Doctoral Dissertation of Nanjing University of Aeronautics and Astronautics(BCXJ10-09)
文摘An improved adaptive particle swarm optimization(IAPSO)algorithm is presented for solving the minimum makespan problem of job shop scheduling problem(JSP).Inspired by hormone modulation mechanism,an adaptive hormonal factor(HF),composed of an adaptive local hormonal factor(H l)and an adaptive global hormonal factor(H g),is devised to strengthen the information connection between particles.Using HF,each particle of the swarm can adjust its position self-adaptively to avoid premature phenomena and reach better solution.The computational results validate the effectiveness and stability of the proposed IAPSO,which can not only find optimal or close-to-optimal solutions but also obtain both better and more stability results than the existing particle swarm optimization(PSO)algorithms.
文摘This paper presents a new genetic algorithm for job-shop scheduling problem. Based on schema theorem and building block hypothesis, a new crossover is proposed. By selecting short, low-order, highly fit schemas for genetic operator, the crossover can maintain a diversity of population without disrupting the characteristics and search the global optimization. Simulation results on famous benchmark problems MT06, MT10 and MT20 coded by Matlab show that our genetic operators are suitable to job-shop scheduling problems and outperform the previous GA-based approaches.
文摘In this paper, we propose a new genetic algorithm for job-shop scheduling problems (JSP). The proposed method uses the operation-based representation, based on schema theorem and building block hypothesis, a new crossover is proposed : By selecting short, low order highly fit schemas to genetic operator, the crossover can exchange meaningful ordering information of parents effectively and can search the global optimization. Simulation results on MT benchmark problem coded by C + + show that our genetic operators are very powerful and suitable to job-shop scheduling problems and our method outperforms the previous GA-based approaches.
基金Supported by a Marie Curie International Research Staff Exchange Scheme Fellowship within the 7th European Community Framework Program(Grant No.294931)National Science Foundation of China(Grant No.51175262)+1 种基金Jiangsu Provincial Science Foundation for Excellent Youths of China(Grant No.BK2012032)Jiangsu Provincial Industry-Academy-Research Grant of China(Grant No.BY201220116)
文摘The traditional production planning and scheduling problems consider performance indicators like time, cost and quality as optimization objectives in manufacturing processes. However, environmentally-friendly factors like energy consumption of production have not been completely taken into consideration. Against this background, this paper addresses an approach to modify a given schedule generated by a production plarming and scheduling system in a job shop floor, where machine tools can work at different cutting speeds. It can adjust the cutting speeds of the operations while keeping the original assignment and processing sequence of operations of each job fixed in order to obtain energy savings. First, the proposed approach, based on a mixed integer programming mathematical model, changes the total idle time of the given schedule to minimize energy consumption in the job shop floor while accepting the optimal solution of the scheduling objective, makespan. Then, a genetic-simulated annealing algorithm is used to explore the optimal solution due to the fact that the problem is strongly NP-hard. Finally, the effectiveness of the approach is performed small- and large-size instances, respectively. The experimental results show that the approach can save 5%-10% of the average energy consumption while accepting the optimal solution of the makespan in small-size instances. In addition, the average maximum energy saving ratio can reach to 13%. And it can save approximately 1%-4% of the average energy consumption and approximately 2.4% of the average maximum energy while accepting the near-optimal solution of the makespan in large-size instances. The proposed research provides an interesting point to explore an energy-aware schedule optimization for a traditional production planning and scheduling problem.
文摘The issue of reducing energy consumption for the job-shop scheduling problem in machining systems is addressed, whose dual objectives are to minimize both the energy consumption and the makespan. First, the bi- objective model for the job-shop scheduling problem is proposed. The objective function value of the model represents synthesized optimization of energy consumption and makespan. Then, a heuristic algorithm is developed to locate the optimal or near optimal solutions of the model based on the Tabu search mechanism. Finally, the experimental case is presented to demonstrate the effectiveness of the proposed model and the algorithm.
基金the National Natural Science Foundation of China (6027401360474002)Shanghai Development Found for Science and Technology (04DZ11008).
文摘A modified bottleneck-based (MB) heuristic for large-scale job-shop scheduling problems with a welldefined bottleneck is suggested, which is simpler but more tailored than the shifting bottleneck (SB) procedure. In this algorithm, the bottleneck is first scheduled optimally while the non-bottleneck machines are subordinated around the solutions of the bottleneck schedule by some effective dispatching rules. Computational results indicate that the MB heuristic can achieve a better tradeoff between solution quality and computational time compared to SB procedure for medium-size problems. Furthermore, it can obtain a good solution in a short time for large-scale jobshop scheduling problems.
基金Supported by National Information Industry Department (01XK310020)Shanghai Natural Science Foundation (No. 01ZF14004)
文摘The technology of production planning and scheduling is one of the critical technologies that decide whether the automated manufacturing systems can get the expected economy. Job shop scheduling belongs to the special class of NP-hard problems. Most of the algorithms used to optimize this class of problems have an exponential time; that is, the computation time increases exponentially with problem size. In scheduling study, makespan is often considered as the main objective. In this paper, makespan, the due date request of the key jobs, the availability of the key machine, the average wait-time of the jobs, and the similarities between the jobs and so on are taken into account based on the application of mechanical engineering. The job shop scheduling problem with multi-objectives is analyzed and studied by using genetic algorithms based on the mechanics of genetics and natural selection. In this research, the tactics of the coding and decoding and the design of the genetic operators, along with the description of the mathematic model of the multi-objective functions, are presented. Finally an illu-strative example is given to testify the validity of this algorithm.
基金supported by the Innovation Scientists and Technicians Troop Construction Projects of Henan Province(224000510002)。
文摘Time-Sensitive Network(TSN)with deterministic transmission capability is increasingly used in many emerging fields.It mainly guarantees the Quality of Service(QoS)of applications with strict requirements on time and security.One of the core features of TSN is traffic scheduling with bounded low delay in the network.However,traffic scheduling schemes in TSN are usually synthesized offline and lack dynamism.To implement incremental scheduling of newly arrived traffic in TSN,we propose a Dynamic Response Incremental Scheduling(DR-IS)method for time-sensitive traffic and deploy it on a software-defined time-sensitive network architecture.Under the premise of meeting the traffic scheduling requirements,we adopt two modes,traffic shift and traffic exchange,to dynamically adjust the time slot injection position of the traffic in the original scheme,and determine the sending offset time of the new timesensitive traffic to minimize the global traffic transmission jitter.The evaluation results show that DRIS method can effectively control the large increase of traffic transmission jitter in incremental scheduling without affecting the transmission delay,thus realizing the dynamic incremental scheduling of time-sensitive traffic in TSN.
基金supported by the Natural Science Foundation of Anhui Province(Grant Number 2208085MG181)the Science Research Project of Higher Education Institutions in Anhui Province,Philosophy and Social Sciences(Grant Number 2023AH051063)the Open Fund of Key Laboratory of Anhui Higher Education Institutes(Grant Number CS2021-ZD01).
文摘The distributed flexible job shop scheduling problem(DFJSP)has attracted great attention with the growth of the global manufacturing industry.General DFJSP research only considers machine constraints and ignores worker constraints.As one critical factor of production,effective utilization of worker resources can increase productivity.Meanwhile,energy consumption is a growing concern due to the increasingly serious environmental issues.Therefore,the distributed flexible job shop scheduling problem with dual resource constraints(DFJSP-DRC)for minimizing makespan and total energy consumption is studied in this paper.To solve the problem,we present a multi-objective mathematical model for DFJSP-DRC and propose a Q-learning-based multi-objective grey wolf optimizer(Q-MOGWO).In Q-MOGWO,high-quality initial solutions are generated by a hybrid initialization strategy,and an improved active decoding strategy is designed to obtain the scheduling schemes.To further enhance the local search capability and expand the solution space,two wolf predation strategies and three critical factory neighborhood structures based on Q-learning are proposed.These strategies and structures enable Q-MOGWO to explore the solution space more efficiently and thus find better Pareto solutions.The effectiveness of Q-MOGWO in addressing DFJSP-DRC is verified through comparison with four algorithms using 45 instances.The results reveal that Q-MOGWO outperforms comparison algorithms in terms of solution quality.
基金the Project Program of Science and Technology on Micro-System Laboratory,No.6142804220101.
文摘In recent years, target tracking has been considered one of the most important applications of wireless sensornetwork (WSN). Optimizing target tracking performance and prolonging network lifetime are two equally criticalobjectives in this scenario. The existing mechanisms still have weaknesses in balancing the two demands. Theproposed heuristic multi-node collaborative scheduling mechanism (HMNCS) comprises cluster head (CH)election, pre-selection, and task set selectionmechanisms, where the latter two kinds of selections forma two-layerselection mechanism. The CH election innovatively introduces the movement trend of the target and establishesa scoring mechanism to determine the optimal CH, which can delay the CH rotation and thus reduce energyconsumption. The pre-selection mechanism adaptively filters out suitable nodes as the candidate task set to applyfor tracking tasks, which can reduce the application consumption and the overhead of the following task setselection. Finally, the task node selection is mathematically transformed into an optimization problem and thegenetic algorithm is adopted to form a final task set in the task set selection mechanism. Simulation results showthat HMNCS outperforms other compared mechanisms in the tracking accuracy and the network lifetime.
文摘As cloud quantum computing gains broader acceptance,a growing quantity of researchers are directing their focus towards this domain.Nevertheless,the rapid surge in demand for cloud-based quantum computing resources has led to a scarcity,which in turn hampers users from achieving optimal satisfaction.Therefore,cloud quantum computing service providers require a unified analysis and scheduling framework for their quantumresources and user jobs to meet the ever-growing usage demands.This paper introduces a new multi-programming scheduling framework for quantum computing in a cloud environment.The framework addresses the issue of limited quantum computing resources in cloud environments and ensures a satisfactory user experience.It introduces three innovative designs:1)Our framework automatically allocates tasks to different quantum backends while ensuring fairness among users by considering both the cloud-based quantum resources and the user-submitted tasks.2)Multi-programming mechanism is employed across different quantum backends to enhance the overall throughput of the quantum cloud.In comparison to conventional task schedulers,our proposed framework achieves a throughput improvement of more than two-fold in the quantum cloud.3)The framework can balance fidelity and user waiting time by adaptively adjusting scheduling parameters.
文摘In current research on task offloading and resource scheduling in vehicular networks,vehicles are commonly assumed to maintain constant speed or relatively stationary states,and the impact of speed variations on task offloading is often overlooked.It is frequently assumed that vehicles can be accurately modeled during actual motion processes.However,in vehicular dynamic environments,both the tasks generated by the vehicles and the vehicles’surroundings are constantly changing,making it difficult to achieve real-time modeling for actual dynamic vehicular network scenarios.Taking into account the actual dynamic vehicular scenarios,this paper considers the real-time non-uniform movement of vehicles and proposes a vehicular task dynamic offloading and scheduling algorithm for single-task multi-vehicle vehicular network scenarios,attempting to solve the dynamic decision-making problem in task offloading process.The optimization objective is to minimize the average task completion time,which is formulated as a multi-constrained non-linear programming problem.Due to the mobility of vehicles,a constraint model is applied in the decision-making process to dynamically determine whether the communication range is sufficient for task offloading and transmission.Finally,the proposed vehicular task dynamic offloading and scheduling algorithm based on muti-agent deep deterministic policy gradient(MADDPG)is applied to solve the optimal solution of the optimization problem.Simulation results show that the algorithm proposed in this paper is able to achieve lower latency task computation offloading.Meanwhile,the average task completion time of the proposed algorithm in this paper can be improved by 7.6%compared to the performance of the MADDPG scheme and 51.1%compared to the performance of deep deterministic policy gradient(DDPG).
基金supported in part by the National Natural Science Foundation of China under Grant 62172192,U20A20228,and 62171203in part by the Science and Technology Demonstration Project of Social Development of Jiangsu Province under Grant BE2019631。
文摘Currently,applications accessing remote computing resources through cloud data centers is the main mode of operation,but this mode of operation greatly increases communication latency and reduces overall quality of service(QoS)and quality of experience(QoE).Edge computing technology extends cloud service functionality to the edge of the mobile network,closer to the task execution end,and can effectivelymitigate the communication latency problem.However,the massive and heterogeneous nature of servers in edge computing systems brings new challenges to task scheduling and resource management,and the booming development of artificial neural networks provides us withmore powerfulmethods to alleviate this limitation.Therefore,in this paper,we proposed a time series forecasting model incorporating Conv1D,LSTM and GRU for edge computing device resource scheduling,trained and tested the forecasting model using a small self-built dataset,and achieved competitive experimental results.
基金supported by the NationalNatural Science Foundation of China(No.61972118)the Key R&D Program of Zhejiang Province(No.2023C01028).
文摘Cloud service providers generally co-locate online services and batch jobs onto the same computer cluster,where the resources can be pooled in order to maximize data center resource utilization.Due to resource competition between batch jobs and online services,co-location frequently impairs the performance of online services.This study presents a quality of service(QoS)prediction-based schedulingmodel(QPSM)for co-locatedworkloads.The performance prediction of QPSM consists of two parts:the prediction of an online service’s QoS anomaly based on XGBoost and the prediction of the completion time of an offline batch job based on randomforest.On-line service QoS anomaly prediction is used to evaluate the influence of batch jobmix on on-line service performance,and batch job completion time prediction is utilized to reduce the total waiting time of batch jobs.When the same number of batch jobs are scheduled in experiments using typical test sets such as CloudSuite,the scheduling time required by QPSM is reduced by about 6 h on average compared with the first-come,first-served strategy and by about 11 h compared with the random scheduling strategy.Compared with the non-co-located situation,QPSM can improve CPU resource utilization by 12.15% and memory resource utilization by 5.7% on average.Experiments show that the QPSM scheduling strategy proposed in this study can effectively guarantee the quality of online services and further improve cluster resource utilization.