Domain Knowledge Used in Meta-Heuristic Algorithms for the Job-Shop Scheduling Problem:Review and Analysis

Meta-heuristic algorithms search the problem solution space to obtain a satisfactory solution within a reasonable timeframe.By combining domain knowledge of the specific optimization problem,the search efficiency and quality of meta-heuristic algorithms can be significantly improved,making it crucial to identify and summarize domain knowledge within the problem.In this paper,we summarize and analyze domain knowledge that can be applied to meta-heuristic algorithms in the job-shop scheduling problem(JSP).Firstly,this paper delves into the importance of domain knowledge in optimization algorithm design.After that,the development of different methods for the JSP are reviewed,and the domain knowledge in it for meta-heuristic algorithms is summarized and classified.Applications of this domain knowledge are analyzed,showing it is indispensable in ensuring the optimization performance of meta-heuristic algorithms.Finally,this paper analyzes the relationship among domain knowledge,optimization problems,and optimization algorithms,and points out the shortcomings of the existing research and puts forward research prospects.This paper comprehensively summarizes the domain knowledge in the JSP,and discusses the relationship between the optimization problems,optimization algorithms and domain knowledge,which provides a research direction for the metaheuristic algorithm design for solving the JSP in the future.

Deep Reinforcement Learning Solves Job-shop Scheduling Problems

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.

Necessary and Sufficient Conditions for Feasible Neighbourhood Solutions in the Local Search of the Job-Shop Scheduling Problem

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.

FLEXIBLE JOB-SHOP SCHEDULING WITH FUZZY GOAL THROUGH IOCDGA

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.

INTEGRATED OPERATOR GENETIC ALGORITHM FOR SOLVING MULTI-OBJECTIVE FLEXIBLE JOB-SHOP SCHEDULING

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.

Solving Job-Shop Scheduling Problem Based on Improved Adaptive Particle Swarm Optimization Algorithm

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.

Improved Genetic Algorithm for Job-Shop Scheduling

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.

Job-Shop Scheduling问题的一个快速算法

Job-Shop Scheduling问题是优化组合中一个著名的难题,即使规模不大的算例在计算上也是很棘手的。文章给出了一个性能很好的算法,该算法找到了所计算的16个算例中12个算例的最优解,而且每个算例在一台个人计算机(CPU为赛扬633)上所花的计算时间不超过1分钟。

Solving Job-Shop Scheduling Problems by Genetic Algorithms Based on Building Block Hypothesis

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.

具有模糊加工时间的Flexible Job-Shop Scheduling问题的研究

采用梯形模糊数来表征柔性生产系统中的时间参数,并在此基础上对具有模糊加工时间的柔性作业车间最小化制造跨度调度问题进行了描述。然后给出了基于粒子群优化的柔性作业车间调度模型。最后通过实例验证了模型的有效性。

Energy-efficient Approach to Minimizing the Energy Consumption in An Extended Job-shop Scheduling Problem

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.

A bi-objective model for job-shop scheduling problem to minimize both energy consumption and makespan

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.

Modified bottleneck-based heuristic for large-scale job-shop scheduling problems with a single bottleneck

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.

Job-shop Scheduling with Multi-objectives Based on Genetic Algorithms

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.

MCWOA Scheduler:Modified Chimp-Whale Optimization Algorithm for Task Scheduling in Cloud Computing

Cloud computing provides a diverse and adaptable resource pool over the internet,allowing users to tap into various resources as needed.It has been seen as a robust solution to relevant challenges.A significant delay can hamper the performance of IoT-enabled cloud platforms.However,efficient task scheduling can lower the cloud infrastructure’s energy consumption,thus maximizing the service provider’s revenue by decreasing user job processing times.The proposed Modified Chimp-Whale Optimization Algorithm called Modified Chimp-Whale Optimization Algorithm(MCWOA),combines elements of the Chimp Optimization Algorithm(COA)and the Whale Optimization Algorithm(WOA).To enhance MCWOA’s identification precision,the Sobol sequence is used in the population initialization phase,ensuring an even distribution of the population across the solution space.Moreover,the traditional MCWOA’s local search capabilities are augmented by incorporating the whale optimization algorithm’s bubble-net hunting and random search mechanisms into MCWOA’s position-updating process.This study demonstrates the effectiveness of the proposed approach using a two-story rigid frame and a simply supported beam model.Simulated outcomes reveal that the new method outperforms the original MCWOA,especially in multi-damage detection scenarios.MCWOA excels in avoiding false positives and enhancing computational speed,making it an optimal choice for structural damage detection.The efficiency of the proposed MCWOA is assessed against metrics such as energy usage,computational expense,task duration,and delay.The simulated data indicates that the new MCWOA outpaces other methods across all metrics.The study also references the Whale Optimization Algorithm(WOA),Chimp Algorithm(CA),Ant Lion Optimizer(ALO),Genetic Algorithm(GA)and Grey Wolf Optimizer(GWO).

DR-IS:Dynamic Response Incremental Scheduling in Time-Sensitive Network

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.

Energy-Saving Distributed Flexible Job Shop Scheduling Optimization with Dual Resource Constraints Based on Integrated Q-Learning Multi-Objective Grey Wolf Optimizer

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.

A Layered Energy-Efficient Multi-Node Scheduling Mechanism for Large-Scale WSN

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.

A Novel Scheduling Framework for Multi-Programming Quantum Computing in Cloud Environment

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.

Dynamic Offloading and Scheduling Strategy for Telematics Tasks Based on Latency Minimization

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