Licai Qin, Xiaojun Liu (2024). Feasibility evaluation method for scheduling schemes based on auxiliary elapsed time. In: Human Aspects of Advanced Manufacturing, Production Management and Process Control. AHFE Open Access, vol. 146, pp. 140–151. https://doi.org/10.54941/ahfe1005160
In flexible manufacturing workshops, workshop production scheduling belongs to a typical NP-complete problem, and its optimal solution is difficult to find, in order to simplify the construction of the model, nowadays, most of the related studies on scheduling problems usually simplify the logistic time in order to ignore the influence of logistics on workshop scheduling, in this paper, in order to verify the feasibility of this kind of scheduling plan which does not separate the logistics as a separate process in the case of joining infinite transport resources, the original scheduling plan using the created TLPU model for process splitting. A Gantt chart information storage structure is designed to facilitate the constraints of the split processes in the final generated scheduling plan with traffic resources. Then a method for differentially calculating the running time of each equipment is proposed based on the different characteristics and parameters of different equipment to complete the splitting process of a processing process with traffic resources in the original scheduling plan. After traversing all the original processing processes and performing the splitting process for them considering infinite traffic resources, the creation of the transport equipment time window is completed. Finally, a validation of the feasibility of the shop floor scheduling scheme based on the calculation of the derived transport equipment running time and transport equipment time window is proposed.
Shop-floor production scheduling is a typical NP-complete problem, whose optimal solution is difficult to find. Due to the complexity of this type of prob- lem, most of the related studies on scheduling problems nowadays make a large number of simplifications to shop-floor production for the convenience of research, such as assuming that logistics time is negligible with respect to machining time, using a fixed time lag as the logistics time consumed, or combining the logistics time by a factor in the processing time. However, the optimal production scheduling solution obtained from the shop floor scheduling problem after using these simplifications may not be feasible in actual production.
Feasibility Evaluation Method for Scheduling Schemes Based on Auxiliary Elapsed Time 141
Considering the lead time as a class of complex and pervasive shop floor scheduling problems, Lin et al. (2004) proposed heuristic rules for prioritising the allocation of auxiliary resources. Wang et al. (2015) proposed the adop- tion of a Knowledge-based Multi-agent Evolutionary Algorithm (KMEA) to solve the workshop scheduling problem considering preparation time. Zhang et al. (2020) consider the constraints on the preparation time and transporta- tion time during the machining process of the flexible job shop and propose an improved genetic algorithm with three objectives, namely, to minimize the fabrication time, the total setup time, the total transportation time, and the total setup time. Cao et al. (2019) proposed to use a cuckoo search algorithm based on reinforcement learning and agent modelling to solve the workshop scheduling problem considering lead time. Liou et al. (2015) proposed a multi-stage flow shop scheduling problem, which includes the inter-machine of job transport time and dependency sequence establishment time between groups, proposed a new coding scheme and developed a new hybrid algo- rithm to solve the proposed problem by a reasonable combination of particle swarm algorithm and genetic algorithm. Wu et al. (2020) consider the flex- ible job shop scheduling problem with dual resource constraints under the constraints of mounting and dismounting on fixtures during the workpiece machining process, and use NSGA-II to solve the problem, which effec- tively reduces the mounting and dismounting time of the fixtures. Zhang et al. (2019) established a flexible job shop scheduling model with transport time by considering transport time and processing time as independent times to minimise the maximum completion time and solved the problem with a genetic algorithm.
In the scheduling scheme for optimising logistic time, the process time for the production of a workpiece is divided into PT (Process Time), RLT (Reserve Logistic Time) and BT (Blocking Time) according to the schedul- ing plan. PT, RLT and BT to describe the production process of a workpiece can be shown in Figure 1, where BT to the production of Gantt chart time shall prevail, BT can be 0, n for the number of workpiece processing proce- dures. In the actual production, due to the combination of logistics equipment operation status, so the fixed time interval does not represent the real oper- ating hours of logistics equipment, the need for various types of logistics equipment operating hours to calculate the actual logistics time (ALT, Actual Logistic Time). Since ALT cannot be obtained directly in the scheduling plan, the relationship between ALT and RLT, BT is not clear, resulting in the origi- nal scheduling plan can not directly judge whether it is feasible in the actual production. In a section of the production process, the actual logistics time ALT is greater than the sum of RLT and BT, which means that the actual logistics equipment can not complete the transport of the workpiece in the specified time, resulting in the scheduling programme is not feasible in the actual production, as shown in Figure 2(a); on the contrary, it means that the logistics equipment can be given to the workpiece processing equipment for processing in a specified period of time, so that the section of the production process can be run in accordance with the scheduling programme. operation, as shown in Figure 2(b) and Figure 2(c).
142 Qin and Liu
Figure 1: Time composition of the scheduling programme.
Figure available in the original PDF paper.
Figure 2: Relationship between actual logistics time and scheduling feasibility.
Figure available in the original PDF paper.
In order to express the scheduling scheme structurally, this chapter firstly establishes a scheduling scheme description method based on directed acyclic graph, and defines the workshop scheduling scheme as a directed acyclic graph structure composed of a set of multiple workpiece machining pro- cess nodes in a certain order structure, in which the workpiece machining process nodes are the basic constituent units of the workshop scheduling scheme. After obtaining the directed acyclic graph description of the work- shop scheduling scheme, this chapter first preprocesses different types of scheduling schemes, and then constructs a logistics information process- ing module and adds different logistics equipment processes to the original scheduling scheme by splitting the workpiece processing processes using the TLPU (Transport-Load-Process-Unload) model, and eventually Generate a scheduling plan that includes the operating time window of the transport equipment and initially judge the feasibility of the original optimal schedul- ing plan under the situation of unlimited transport resources. The specific workflow is shown in Figure 3.
Figure 3: Overall flow of the feasibility evaluation method for scheduling options for joining logistics.
Feasibility Evaluation Method for Scheduling Schemes Based on Auxiliary Elapsed Time 143
Workshop Scheduling Programme Pre-Processing and Constructing a TLPU Model The shop floor scheduling scheme is composed of a set of machining pro- cess units arranged in a certain spatio-temporal order, while the process units themselves can be described by a structure, so in this chapter the directed acyclic graph data structure is chosen to model the shop floor scheduling scheme, which can be described by the description given in (1).
Equations and mathematical formulas are available in the original paper PDF.
Where G is the set of directed acyclic graphs, a directed acyclic graph repre- sents the processing flow planning of a workpiece in the scheduling scheme, and m is the number of workpieces to be processed in the scheduling scheme; Vp is the set of nodes of a process unit, a node of a process unit corre- sponds to a process in the scheduling scheme; E is the set of directed edges, where n is the number of nodes of a process unit; Fea is the set of cat- egorical features of a process unit, i.e., each node can be described by a dimensional feature vector node can be described by an s-dimensional feature vector.
The original shop floor scheduling programme is presented through a Gantt chart. The information of Gantt chart mainly contains two aspects of process and inter-process relationship information. Process is the basic unit of the production process, each process corresponds to a continuous work process on a certain device. The inter-process relationship includes: one-to-one relationship, one-to-many relationship, many-to-one relationship and assembly relationship.
The relationship between processes is represented by directed graphs, while the information within processes is represented by s-dimensional feature vectors of a. The process nodes in the logistic processing module can be described by five-dimensional feature vectors as shown in Eq. According to the requirements of the input information of the logistics processing module, the process nodes in Vp can be described by five-dimensional feature vec- tors, as shown in (5), where proName represents the process name, equipID represents the identification of the operating equipment, partID represents the identification of the workpiece interacting with the equipment, startTime represents the time when the equipment of this process starts running, end- Time represents the time when the equipment of this process ends running, and addit represents the additional information of the process. Thus, any process node can be expressed as a vector, and then the process nodes in the scheduling plan can be modified, added, or deleted by the logistics processing module.
144 Qin and Liu
[Equation or mathematical symbol available in the original paper PDF]
[Equation or mathematical symbol available in the original paper PDF] proNamei equipIDi
partIDi startTimei endTimei
Equations and mathematical formulas are available in the original paper PDF.
Among the above three types of scheduling schemes, the scheduling scheme in Figure 4(a) does not meet the conditions for the operation of the logistics equipment because it does not take into account the logistics time and the pro- cess time only includes the processing time of the processing equipment, and the processing equipment starts processing at the time 0, so when this type of scheduling scheme is encountered, the system will directly return the result that the scheduling scheme does not meet the requirements when the logistics is taken into account; In Figure 4 (b), the scheduling scheme takes the fixed time lag as the reserved logistics time RLT and the process time only includes the processing time of the processing equipment, in this type of scheduling scheme, the processing time of the equipment is the real time of the process- ing equipment operation, so the scheduling scheme is directly expressed as a directed acyclic graph group which does not need to process the process nodes, and is directly used as the input of the subsequent logistics processing module; In Figure 4(c), the scheduling scheme combines the reserved logistics time RLT with a coefficient a in the processing time of the equipment, and when dealing with this type of scheduling scheme, the scheduling scheme is first represented by a directed acyclic graph group, and then based on the coefficient a provided by the scheduling scheme of the logistics time as a per- centage of the current overall process, the actual processing time is calculated and stored in the additional information of the corresponding process node of the directed acyclic graph in addit, which serves as an input to the sub- sequent logistics processing module as the input of the subsequent logistics processing module.
Figure 4: Types of scheduling solutions.
In modern manufacturing, the production process in the production plant is the key to ensuring product quality and improving production efficiency. Each section of the production process can generally be divided into four main stages: the workpiece transport stage, the machine loading process, processing equipment processing process and machine unloading process. In this paper, this mode of subdividing a production process into work- piece transport, loading, machining and unloading processes is called TLPU
Feasibility Evaluation Method for Scheduling Schemes Based on Auxiliary Elapsed Time 145
(Transport-Load-Process-Unload) mode, as shown in Figure 5, which is used for modifying and inserting process nodes into the preprocessed directed acyclic graph set.
Figure 5: TLPU model.
(1) Production process breakdown with fixed logistics time scheduling scheme In the scheduling scheme with fixed logistics time, the processing process of the processing equipment is the actual processing process because the method of fixed logistics time lag simplifies the logistics process. Therefore, the pro- cessing process of the processing equipment can be matched with the TLPU segmentation mode as a definite time point in the production process, and the end time of the operation of the discharging equipment can be deter- mined by the end time of the operation of the processing equipment and the operation time of the discharging equipment as shown in (6), whereby the node Vp of the discharging process is created and inserted after the node V of the actual processing process; and the start time of the operation of the processing equipment and the operation time of the loading equipment can be determined by the start time of the operation of the processing equipment and the operation time of the loading equipment. Determine the start time of the operation of the loading equipment, as shown in (7), thereby creating the node V of the discharging process and inserting it before the node V of the actual processing node; Determine the start time of the operation of the transport equipment by the calculated start time of the operation of the load- ing equipment and the operation length of the transport equipment, as shown in (8), thereby creating the node V of the transport process and inserting it before the node V of the loading process, and the specific subdividing process is as shown in Figure 6.
Figure 6: Schematic diagram of the production process breakdown with a fixed logistics time scheduling scheme. (2) Breakdown of production processes with logistics time factor schedul- ing programme
In the scheduling scheme with logistics time coefficients, since the logis- tics time is simplified and directly calculated into the processing time, the processing process in this scheduling scheme actually represents the actual production process and the actual running time of the processing equipment has been obtained by the pre-processing process. Therefore, the overall pro- duction process can match the TLPU segmentation mode according to the time point of the production process to the end of the production process and the running time of the discharging equipment to determine the start time of the discharging equipment, as shown in (9); discharging equipment running time and the actual length of the processing time to determine the start time of the processing equipment running, as shown in (10); to the start time of the running of the processing equipment and the loading equipment running time to determine the loading equipment running time and the length of the processing equipment running time and the length of the processing equipment running time. The operation start time of the feeding equipment is determined by the operation start time of the processing equipment and the running time of the feeding equipment, as shown in (11); the operation start time of the transport equipment is determined by the calculated opera- tion start time of the feeding equipment and the running time of the transport equipment, as shown in (8), and the specific breakdown process is shown in Figure 7.
Figure 7: Schematic diagram of the production process breakdown with a logistic time factor scheduling scheme.
Feasibility Evaluation Method for Scheduling Schemes Based on Auxiliary Elapsed Time 147
Logistics Processing Module Construction (1) Calculation of running time of loading and unloading equipment
The loading and unloading equipment refers to the equipment used to automatically complete the material loading and unloading process in the automated production line, the main role is to reduce the intensity of manual labour. They can accurately locate and place materials to meet the require- ments of high-precision production. The structure and control system of the loading and unloading equipment are optimised to maintain stable operation and improve the stability and reliability of the production line. Automated loading and unloading equipment mainly includes robotic arms, conveyor belts and lifting platforms adapted to various fixtures.
Conveyor belt loading and unloading of the operating hours of the main factors affecting the rated power of the conveyor equipment, operating speed, handling distance, and the weight of the material, etc., once these factors have been determined can be used in (12) to calculate the length of time that the conveyor belt loading and unloading equipment work.
Where RDTime denotes the running time of the loading and unloading equipment when the workpiece labelled partIDi is machined on the machine labelled equipIDi, Dism-c denotes the distance between the part from the waiting area and the machining machine, and RVequip denotes the speed of movement of the loading and unloading equipment accompanying the machining machine labelled equipIDi.
(2) Calculation of running time of transport equipment with unlimited transport resources In a fully automated production plant, transport equipment can be divided into the following categories: Automated Guided Vehicles (AGVs) achieve autonomous movement and material handling by means of built-in nav- igation systems and sensors, which can move autonomously around the workshop and transport materials from one location to another according to pre-set paths and tasks. The use of these devices allows for efficient material handling and automated production processes in fully automated production plants.
Also since AGVs can transport workpieces continuously without addi- tional waiting when using infinite traffic resources, the running time of AGV transport is only related to the transport distance and the transport speed of the AGV, so the calculation of losing AGV transport time is shown in (13).
TDTimepartIDi,equipIDi = dis(LocpartIDi,equipIDi, LocpartIDi,equipIDi−1) AVpartIDi where TDTime denotes the running time of the transport equipment, dis denotes a function that calculates the distance between two points, LocpartID,equipID denotes the positional coordinates, and AVpartID denotes the transport speed of the AGV.
148 Qin and Liu
Methodology for Calculating Time Windows for Transport Equipment and Evaluating Scheduling Options Because processing time and loading/unloading time can be accurately calcu- lated in actual production, it is judged that when considering the feasibility of the scheduling plan for logistics equipment, the main comparison is between the actual transport equipment working time and the transport equipment time window (TW, Time Window), which refers to the maximum time left after subtracting the actual processing time and loading/unloading time from the total time of a process. time that can be made available for the transport equipment to operate.
By using the TLPU task splitting model and the process running time of each loading and unloading equipment calculated above, the start and end times of the loading and unloading and machining process nodes can be accurately obtained, and the whole process of the machining process from workpiece loading to workpiece machining to workpiece unloading is obtained. Also, as mentioned in the problem description, in a certain produc- tion process of the workpiece, the total production time can be composed of PT, RLT and BT. Therefore, it is possible to obtain the duration and start-end time of TW from the scheduling scheme, as shown in Figure 8.
Figure 8: Creation of working time windows for transport equipment.
To determine the feasibility of the scheduling programme for the opera- tion of equipment with logistics is mainly to determine whether there is any interference between the calculated operating hours of the transport equip- ment and the actual operating time window of the transport equipment in the scheduling programme, and to determine whether the original schedul- ing programme is infeasible if there is any time interference and vice versa, and to determine whether the generated scheduling programme is feasible under unlimited traffic resources.
CASE STUDY The effectiveness of the evaluation method proposed in the article is verified by taking the scheduling scheme in a flexible manufacturing shop with three machining devices as an example. Table 1 shows the process and processing time of the workpieces to be processed, Figure 9 shows the input original workshop scheduling scheme, where the time set aside for logistics is 20s in figure a and 30s in figure b. Figure 10 shows the layout of the flexible man- ufacturing workshop, Table 2 gives the distance between each device in the actual workshop, and Table 3 shows the running speed of the actual devices.
Feasibility Evaluation Method for Scheduling Schemes Based on Auxiliary Elapsed Time 149
After the pre-processing of the original scheduling scheme and the process- ing of the logistics information processing module, then TW, loading time, machining time and unloading time for each process of each machined part for two scheduling scenarios with different set-aside times are obtained in Table 4, and each TW is marked in Figure 11. Finally, the feasibility eval- uation of each stage is obtained by comparing the transport time of each TW and the actual transport equipment in Table 5 in scenarios a and b, respectively, and the evaluation of the overall original scheduling plan can be feasible only if all stages can be carried out. The result that option a is not feasible and option b is feasible is obtained.
Table 1. Workpiece machining process and machining time.
The shop floor scheduling problem is very complex, and the logistics time is generally simplified in the current research, but due to the constraints of the actual shop floor equipment operation, the optimal shop floor scheduling
Feasibility Evaluation Method for Scheduling Schemes Based on Auxiliary Elapsed Time 151
scheme obtained after simplifying the logistics time is not necessarily feasi- ble in the actual shop floor operation. In this paper, we propose a workshop scheduling scheme using the process splitting mode of the TLPU model, and at the same time, we use the logistics processing module to calculate the load- ing and unloading equipment and transport equipment time, create the TW of each process, and then compare the TW with the calculated transport equip- ment operation time to complete the feasibility evaluation of the original scheduling scheme under unlimited transport resources. We chose a flexi- ble machining shop as an example to verify the effectiveness of the proposed method.
REFERENCES
Cao Z C. Lin C R, Zhou M C, et al. Scheduling Semiconductor Testing Facility by Using Cuckoo Search Algorithm With Reinforcement Learning and Surrogate Modeling[J]. IEEE Transactions on Automation Science and Engineering, 2019, 16(2): 825–837. Cao Z C, Lin C R, Zhou M C, et al. An Improved Cuckoo Search Algorithm for
Semiconductor Final Testing Scheduling[C]. In: IEEE International Conference on Automation Science and Engineering. New York: IEEE, 2017: 1040–1045. Guohui Zhang, Jinghe Sun, Xixi Lu and Haijun Zhang. “An improved memetic algorithm for the flexible job shop scheduling problem with transportation times.” Measurement and Control 53.7–8 (2020): 1518–1528. Guohui Zhang, Jinghe Sun, Xing Liu, Guodong Wang and Yangyang Yang. “Solv-
ing flexible job shop scheduling problems with transportation time based on improved genetic algorithm.” Mathematical biosciences and engineering: MBE 16.3 (2019): 1334. Liou Cheng-Dar, and Yi-Chih Hsieh. “A hybrid algorithm for the multi-stage flow shop group scheduling with sequence-dependent setup and transportation times.” International Journal of Production Economics 170 (2015): 258–267. Lin J T, Wang F K, Lee W T. Capacity-Constrained Scheduling for a Logic IC Final
Test Facility[J]. International Journal of Production Research, 2004, 42(1): 79–99. Xiuli Wu, Junjian Peng, Xiao Xiao Shaomin Wu. An effective approach for the dualresource flexible job shop scheduling problem considering loading and unloading[J]. Journal of Intelligent Manufacturing, 2020, 2020: 1–22. Uzsoy R, Martin L A, Lee C Y, et al. Production Scheduling Algorithms for a Semi-
conductor Test Facility[J]. IEEE Transactions on Semiconductor Manufacturing, 1991, 4(4): 270–280. Wang S Y, Wang L. A Knowledge-Based Multi-Agent Evolutionary Algorithm for Semiconductor Final Testing Scheduling Problem[J]. Knowledge-Based Systems, 2015, 84: 1–9.
LISTED IN THE AHFE DIGITAL BOOKSTORE CATALOGUE
Explore the complete digital volume
Human Aspects of Advanced Manufacturing, Production Management and Process Control
Read this individual research paper free through the original publisher, or explore the full digital proceedings book.
ISBN 978-1-964867-22-9
Explore this ISBN in the AHFE Bookstore ↗Listed in the July 2026 bookstore catalogue; search by ISBN to confirm current availability · Digital book purchase optional