Research on Flexible Job Shop Scheduling Based on Improved Two-Layer Optimization Algorithm

To improve the productivity,the resource utilization and reduce the production cost of flexible job shops,this paper designs an improved two-layer optimization algorithm for the dual-resource scheduling optimization problem of flexible job shop considering workpiece batching.Firstly,a mathematical model is established to minimize the maximum completion time.Secondly,an improved two-layer optimization algorithm is designed:the outer layer algorithm uses an improved PSO(Particle Swarm Optimization)to solve the workpiece batching problem,and the inner layer algorithm uses an improved GA(Genetic Algorithm)to solve the dual-resource scheduling problem.Then,a rescheduling method is designed to solve the task disturbance problem,represented by machine failures,occurring in the workshop production process.Finally,the superiority and effectiveness of the improved two-layer optimization algorithm are verified by two typical cases.The case results show that the improved two-layer optimization algorithm increases the average productivity by 7.44% compared to the ordinary two-layer optimization algorithm.By setting the different numbers of AGVs(Automated Guided Vehicles)and analyzing the impact on the production cycle of the whole order,this paper uses two indicators,the maximum completion time decreasing rate and the average AGV load time,to obtain the optimal number of AGVs,which saves the cost of production while ensuring the production efficiency.This research combines the solved problem with the real production process,which improves the productivity and reduces the production cost of the flexible job shop,and provides new ideas for the subsequent research.

Real-time high-speed train rescheduling based on a Human-Computer Interaction framework

During railway operations,trains normally run as scheduled,but the occurrence of unexpected events will disrupt traffic flow and cause train deviation from the original timetable.In order to assist dispatchers in rescheduling trains,this paper introduces an innovative Human-Computer Interaction framework.This framework enables train dispatchers to propose different timetable adjustment instructions to the original or adjusted timetable.These instructions will be processed,stored,analyzed,and digested by computer program,which finally lead to the modification and calculation of the embedded mathematical model,then a new adjusted timetable will be produced and provided to dispatchers for checking and modifying.This framework can iterate for unlimited times based on dispatchers'intentions,until the final results satisfy them.A demonstration system named RTARS(Real-time Timetable Automatic Rescheduling System)is developed based on this framework and it has been applied in Beijing Railway Administration,which shows its effectiveness in reality.

Transformer-Based Macroscopic Regulation for High-Speed Railway Timetable Rescheduling

Unexpected delays in train operations can cause a cascade of negative consequences in a high-speed railway system.In such cases,train timetables need to be rescheduled.However,timely and efficient train timetable rescheduling is still a challenging problem due to its modeling difficulties and low optimization efficiency.This paper presents a Transformer-based macroscopic regulation approach which consists of two stages including Transformer-based modeling and policy-based decisionmaking.Firstly,the relationship between various train schedules and operations is described by creating a macroscopic model with the Transformer,providing the better understanding of overall operation in the high-speed railway system.Then,a policy-based approach is used to solve a continuous decision problem after macro-modeling for fast convergence.Extensive experiments on various delay scenarios are conducted.The results demonstrate the effectiveness of the proposed method in comparison to other popular methods.

Dynamic constraint and objective generation approach for real-time train rescheduling model under human-computer interaction

Real-time train rescheduling plays a vital role in railway transportation as it is crucial for maintaining punctuality and reliability in rail operations.In this paper,we propose a rescheduling model that incorporates constraints and objectives generated through human-computer interaction.This approach ensures that the model is aligned with practical requirements and daily operational tasks while facilitating iterative train rescheduling.The dispatcher’s empirical knowledge is integrated into the train rescheduling process using a human-computer interaction framework.We introduce six interfaces to dynamically construct constraints and objectives that capture human intentions.By summarizing rescheduling rules,we devise a rule-based conflict detection-resolution heuristic algorithm to effectively solve the formulated model.A series of numerical experiments are presented,demonstrating strong performance across the entire system.Furthermore,theflexibility of rescheduling is enhanced through secondary analysis-driven solutions derived from the outcomes of humancomputer interactions in the previous step.This proposed interaction method complements existing literature on rescheduling methods involving human-computer interactions.It serves as a tool to aid dispatchers in identifying more feasible solutions in accordance with their empirical rescheduling strategies.

A train timetable rescheduling approach based on multi-train tracking optimization of high-speed railways

Purpose–This paper aims to propose a train timetable rescheduling(TTR)approach from the perspective of multi-train tracking optimization based on the mutual spatiotemporal information in the high-speed railway signaling system.Design/methodology/approach–Firstly,a single-train trajectory optimization(STTO)model is constructed based on train dynamics and operating conditions.The train kinematics parameters,including acceleration,speed and time at each position,are calculated to predict the arrival times in the train timetable.A STTO algorithm is developed to optimize a single-train time-efficient driving strategy.Then,a TTR approach based on multi-train tracking optimization(TTR-MTTO)is proposed with mutual information.The constraints of temporary speed restriction(TSR)and end of authority are decoupled to calculate the tracking trajectory of the backward tracking train.The multi-train trajectories at each position are optimized to generate a timeefficient train timetable.Findings–The numerical experiment is performed on the Beijing-Tianjin high-speed railway line and CR400AF.The STTO algorithm predicts the train’s planned arrival time to calculate the total train delay(TTD).As for the TSR scenario,the proposed TTR-MTTO can reduce TTD by 60.60%compared with the traditional TTR approach with dispatchers’experience.Moreover,TTR-MTTO can optimize a time-efficient train timetable to help dispatchers reschedule trains more reasonably.Originality/value–With the cooperative relationship and mutual information between train rescheduling and control,the proposed TTR-MTTO approach can automatically generate a time-efficient train timetable to reduce the total train delay and the work intensity of dispatchers.

RTTRS: Rule-based Train Traffic Rescheduling Simulator

Train traffic rescheduling is a complicated and large-scaled combinatorial problem. According to the characteristics of China railway system and from the point of practical use, this paper introduces a rule-based train traffic reschedule interactive simulator. It can be used as a powerful training tool to train the dispatcher and to carry out experimental analysis. The production rules are used as the basic for describing the processes to be simulated. With the increase of rule, users can easily upgrade the simulator by adding their own rules.

Rolling Partial Rescheduling with Dual Objectives for Single Machine Subject to Disruptions

This paper discusses the single-machine rescheduling problem with efficiency and stability as criteria, where more than one disruption arises in large-scale dynamic circumstances. Partial rescheduling (PR) strategy is adopted after each disruption and a rolling mechanism is driven by events in response to disruptions. Two kinds of objective functions are designed respectively for PR sub-problem involving in the interim and the terminal of unfinished jobs. The analytical result demonstrates that each local objective is consistent with the global one. Extensive computational experiment was performed and the computational results show that the rolling PR strategy with dual objectives can greatly improve schedule stability with little sacrifice in efficiency and provide a reasonable trade-off between solution quality and computational efforts.

Rule-and PSO Algorithm-based Dynamic Spatial Rescheduling Method for Hull Curved Block Construction

Due to no effective rescheduling method in hull curved block construction planning, existing scheduling planning can’t be applied in practical production effectively. Two-dimensional layout and dynamic attributes of block construction planning are considered to develop a spatial rescheduling method, which is based on the spatial points searching rule and the particle swarm optimization(PSO) algorithm. A dynamic spatial rescheduling method is proposed to solve the manufacturing problem of rush-order blocks. Through spatial rescheduling, the rescheduling start time, the current processing information set and rescheduling blocks set can be obtained automatically. By using and updating the data of these sets, the rescheduling method combines the PSO algorithm with the spatial points searching rule to determine the rescheduling start time and layout of the blocks. Three types of dynamic events, including rush-order block delay, existing block delay and existing block position changes, are used to address problems with different function goals by setting different function weights. Finally, simulations based on three types of rush-order block events are performed to validate this method, including single rush-order block, multi rush-order blocks at the same time and multi rush-order blocks at different times. The simulation results demonstrate that this method can solve the rush-order block problems in hull block construction and reduce the interference to the existing manufacturing schedule. The proposed research provides a new rescheduling method and helps instruct scheduler to make production planning in hull block construction.

Real-time online rescheduling for multiple agile satellites with emergent tasks

The emergent task is a kind of uncertain event that satellite systems often encounter in the application process.In this paper,the multi-satellite distributed coordinating and scheduling problem considering emergent tasks is studied.Due to the limitation of onboard computational resources and time,common online onboard rescheduling methods for such problems usually adopt simple greedy methods,sacrificing the solution quality to deliver timely solutions.To better solve the problem,a new multi-satellite onboard scheduling and coordinating framework based on multi-solution integration is proposed.This method uses high computational power on the ground and generates multiple solutions,changing the complex onboard rescheduling problem to a solution selection problem.With this method,it is possible that little time is used to generate a solution that is as good as the solutions on the ground.We further propose several multi-satellite coordination methods based on the multi-agent Markov decision process(MMDP)and mixed-integer programming(MIP).These methods enable the satellite to make independent decisions and produce high-quality solutions.Compared with the traditional centralized scheduling method,the proposed distributed method reduces the cost of satellite communication and increases the response speed for emergent tasks.Extensive experiments show that the proposed multi-solution integration framework and the distributed coordinating strategies are efficient and effective for onboard scheduling considering emergent tasks.

Rescheduling to Minimize Total Completion Time Under a Limit Time Disruption for the Parallel Batch

In the rescheduling on a single machine, a set of the original jobs has already been scheduled, in order to make a given objective function is optimal. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. A batching machine is a machine that can handle up to some jobs simultaneously. In this paper,we consider the total completion time under a limit on the sequence disruptions for parallel batching based on rescheduling. For the parallel batching problem based on rescheduling, we research the properties of feasible schedules and optimal schedules on the total completion time under a limit on the maximum time disruptions or total time disruptions, in which the jobs are sequenced in SPT order, and give out the pseudo-polynomial time algorithms on the number of jobs and the processing time of jobs by applying the dynamic programming method.

Closing the loop between data mining and fast decision support for intelligent train scheduling and traffic control

The existing Big Data of transport flows and railway operations can be mined through advanced statistical analysis and machine learning methods in order to describe and predict well the train speed, punctuality, track capacity and energy consumption. The accurate modelling of the real spatial and temporal distribution of line and network transport, traffic and performance stimulates a faster construction and implementation of robust and resilient timetables, as well as the development of efficient decision support tools for real-time rescheduling of train schedules. In combination with advanced train control and safety systems even (semi-.) automatic piloting of trains on main and regional railway lines will become feasible in near future.

Research on Key Issues of Scheduling in FMS

Scheduling is one of the key factors of affecting the flexibility of an FMS. In this paper, scheduling problems in FMS, including description, solving and rescheduling, are discussed in detail.

A hybrid data-mining framework for train rescheduling strategy pattern discovery

This study presents a hybrid data-mining framework based on feature selection algorithms and clustering methods to perform the pattern discovery of high-speed railway train rescheduling strategies(RSs).The proposed model is composed of two states.In the first state,decision tree,random forest,gradient boosting decision tree(GBDT)and extreme gradient boosting(XGBoost)models are used to investigate the importance of features.The features that have a high influence on RSs are first selected.In the second state,a K-means clustering method is used to uncover the interdependences between RSs and the influencing features,based on the results in the first state.The proposed method can determine the quantitative relationships between RSs and influencing factors.The results clearly show the influences of the factors on RSs,the possibilities of different train operation RSs under different situations,as well as some key time periods and key trains that the controllers should pay more attention to.The research in this paper can help train traffic controllers better understand the train operation patterns and provides direction for optimizing rail traffic RSs.

Urban rail transit disruption management: Research progress and future directions

Urban rail transit (URT) disruptions present considerable challenges due to several factors: i) a high probability of occurrence, arising from facility failures, disasters, and vandalism;ii) substantial negative effects, notably the delay of numerous passengers;iii) an escalating frequency, attributable to the gradual aging of facilities;and iv) severe penalties, including substantial fines for abnormal operation. This article systematically reviews URT disruption management literature from the past decade, categorizing it into pre-disruption and post-disruption measures. The pre-disruption research focuses on reducing the effects of disruptions through network analysis, passenger behavior analysis, resource allocation for protection and backup, and enhancing system resilience. Conversely, post-disruption research concentrates on restoring normal operations through train rescheduling and bus bridging services. The review reveals that while post-disruption strategies are thoroughly explored, pre-disruption research is predominantly analytical, with a scarcity of practical pre-emptive solutions. Moreover, future research should focus more on increasing the interchangeability of transport modes, reinforcing redundancy relationships between URT lines, and innovating post-disruption strategies.

FIDER: A Force-Balance-Based Interconnect Delay Driven Re-Synthesis Algorithm for Data-Path Optimization After Floorplan

As the feature size of integrated circuits is reduced to the deep sub-micron level or the nanometer level, the interconnect delay is becoming more and more important in determining the total delay of a circuit. Re-synthesis after floorplan is expected to be very helpful for reducing the interconnect delay of a circuit. In this paper, a force-balance-based re-synthesis algorithm for interconnect delay optimization after floorplan is proposed. The algorithm optimizes the interconnect delay by changing the operation scheduling and the functional unit allocation and binding. With this method the number and positions of all functional units are not changed, but some operations are allocated or bound to different units. Preliminary experimental results show that the interconnect wire delays are reduced efficiently without destroying the floorplan performance.

Rescheduling of observing spacecraft using fuzzy neural network and ant colony algorithm

This paper aims at rescheduling of observing spacecraft imaging plans under uncertainties. Firstly, uncertainties in spacecraft observation scheduling are analyzed. Then, considering the uncertainties with fuzzy features, this paper proposes a fuzzy neural network and a hybrid rescheduling policy to deal with them. It then establishes a mathematical model and manages to solve the rescheduling problem by proposing an ant colony algorithm, which introduces an adaptive control mechanism and takes advantage of the information in an existing schedule. Finally, the above method is applied to solve the rescheduling problem of a certain type of earth-observing satellite. The computation of the example shows that the approach is feasible and effective in dealing with uncertainties in spacecraft observation scheduling. The approach designed here can be useful in solving the problem that the original schedule is contaminated by disturbances.

A Rescheduling Method for Operation Time Delay Disturbance in Steelmaking and Continuous Casting Production Process

In the steelmaking and continuous casting （SMCC） production process, operation time delay may lead to casting break or processing conflict so that the initial scheduling plan becomes unrealizable. Existing research meth- ods are difficult to guarantee the accuracy of the model and successful application to actual applications. The resched- uling problem in response to operation time delay is firstly analyzed. This is then followed by the establishment of a novel multi-obiective nonlinear programming model （MONPM）. In specifications, a three-stage rescheduling method is proposed including the batches splitting （BS）, forward scheduling method （FSM） and backward scheduling meth- od （BSM）. As a result, the real-time application shows that the proposed rescheduling method efficiently ensures the continuous casting and dramatically shortens the redundant waiting time for molten steel in very short rescheduling time.

Metro train rescheduling by adding backup trains under disrupted scenarios

In large cities with heavily congested metro lines, unexpected disturbances often occur, which may cause severe delay of multiple trains, blockage of partial lines, and reduction of passenger service. Metro dispatchers have taken a practical strategy of rescheduling the timetable and adding several backup trains in storage tracks to alleviate waiting passengers from crowding the platforms and recover from such disruptions. In this study,we first develop a mixed integer programming model to determine the optimal train rescheduling plan with considerations of in-service and backup trains. The aim of train rescheduling is to frequently dispatch trains to evacuate delayed passengers after the disruption. Given the nonlinearity of the model, several linearization techniques are adapted to reformulate the model into an equivalent linear model that can be easily handled by the optimization software. Numerical experiments are implemented to verify the effectiveness of the proposed train rescheduling approach.

A robust scheduling algorithm for space telescopes with unpredictable tasks

The original preset schedule of space telescopes can be disrupted when they receive ultra-high-priority unpredictable tasks.The main objective of this study is to observe such unpredictable tasks,the instability of which leads to failures in delivering the promises made.This paper proposes a method for retaining the robustness of the original plan.We use space-based multi-band variable objects monitor(SVOM)mission as an example to introduce the proposed method.First,the reasons for instability are discussed in detail.Two proactive strategies are proposed to promote the robustness of the schedule.The proactive strategies use the available windows of a given list of jobs.However,the realistic problem of SVOM is analysed using a rescheduling algorithm based on NSGA-II experiments with SVOM scenarios showing that the two proposed strategies are effective in reducing the instability caused by unpredictable interruption.

Predictive-reactive Strategy for Flowshop Rescheduling Problem:Minimizing the Total Weighted Waiting Times and Instability

Due to the fourth revolution experiencing,referred to as Industry 4.0,many production firms are devoted to integrating new technological tools to their manufacturing process.One of them,is rescheduling the tasks on the machines responding to disruptions.While,for static scheduling,the efficiency criteria measure the performance of scheduling systems,in dynamic environments,the stability criteria are also used to assess the impact of jobs deviation.In this paper,a new performance measure is investigated for a flowshop rescheduling problem.This one considers simultaneously the total weighted waiting time as the efficiency criterion,and the total weighted completion time deviation as the stability criterion.This fusion could be a very helpful and significant measure for real life industrial systems.Two disruption types are considered:jobs arrival and jobs cancellation.Thus,a Mixed Integer Linear Programming(MILP)model is developed,as well as an iterative predictive-reactive strategy for dealing with the online part.At last,two heuristic methods are proposed and discussed,in terms of solution quality and computing time.