Search

Given the existing integrated scheduling algorithms, all processes are ordered and scheduled overall, and these algorithms ignore the influence of the vertical and horizontal characteristics of the product process tree on the product scheduling effect. This paper presents an integrated scheduling algorithm for the same equipment process sequencing based on the Root-Subtree horizontal and vertical pre-scheduling to solve the above problem. Firstly, the tree decomposition method is used to extract the root node to split the process tree into several Root-Subtrees, and the Root-Subtree priority is set from large to small through the optimal completion time of vertical and horizontal pre-scheduling. All Root-Subtree processes on the same equipment are sorted into the stack according to the equipment process pre-start time, and the stack-top processes are combined with the schedulable process set to schedule and dispatch the stack. The start processing time of each process is determined according to the dynamic start processing time strategy of the equipment process, to complete the fusion operation of the Root-Subtree processes under the constraints of the vertical process tree and the horizontal equipment. Then, the root node is retrieved to form a substantial scheduling scheme, which realizes scheduling optimization by mining the vertical and horizontal characteristics of the process tree. Verification by examples shows that, compared with the traditional integrated scheduling algorithms that sort the scheduling processes as an overall, the integrated scheduling algorithmin this paper is better. The proposed algorithmenhances the process scheduling compactness, reduces the length of the idle time of the processing equipment, and optimizes the production scheduling target, which is of universal significance to solve the integrated scheduling problem. [ABSTRACT FROM AUTHOR]

For the scheduling problem of complex products in multi-workshop production, this paper studied the BOM (Bill of Materials) structure of complex products and the characteristics of the process route and developed the construction method of a multi-level process network diagram. Based on this, a comprehensive mathematical model for scheduling on multi-workshop production was proposed. An improved particle swarm algorithm (PSO) was proposed to solve the problem. By constructing the network subgraph, the invalid search path of the algorithm was avoided, and the efficiency of the algorithm was improved. In addition, for the scheduling problem with product time constraints, this paper presented a path search rescheduling strategy to ensure that the algorithm could obtain an effective search path. Finally, the model and algorithm were verified through a case study. This paper optimized the parameters of the algorithm by different tests and obtained the optimal range of the parameters. At the same time, through the analysis of the scheduling of complex products in a multi-workshop environment, the effectiveness and practicability of the above methods were verified. [ABSTRACT FROM AUTHOR]

This paper investigates an integrated batching and scheduling problem of electrolysis and caster in aluminium industry. The problem is to determine the assignment and scheduling of orders considering sequence-dependent setup times caused by technological and operational constraints of electrolysis cells, and determine the batching and scheduling of orders in the following casters. A novel unit-specific event-based continuous-time mixed integer linear programming model (MILP) is proposed to describe the problem. In this model, the event point is stage specific, and lower bounds are specified to tighten the model. A hybrid pointer-based differential evolution algorithm with new individual representation scheme is designed to solve the problem of industrial scale. An improved hybrid pointer-based mutation operator and a new point-cross crossover operator are proposed to enhance the performance of the algorithm. Computational experiments show that the proposed algorithm is more efficient when compared with CPLEX for medium and large size instances. Comparisons with the lower bound demonstrate that the algorithm is effective. [ABSTRACT FROM AUTHOR]

Copyright of Ordnance Industry Automation is the property of Editorial Board for Ordnance Industry Automation and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

After the occurrence of major sudden disasters, the dispatching and distribution of disaster relief materials are particularly important, but in the process of distribution, there may be excessive distribution of similar emergency materials, unbalanced distribution volume of relief materials in different disaster-affected points, high distribution cost, and low effective distribution rate. In order to solve the above problems, based on the application of big data, this paper proposes a three-level network postdisaster material scheduling and distribution model and an improved NSGA-II algorithm. The model takes the loss degree of the disaster area and the dynamic change rate of the demand for postdisaster relief materials as the constraints, takes the demand prediction of postdisaster relief materials, the optimization of distribution path, distribution nodes, and the satisfaction of victims as the objectives, and designs the sample average approximation method and the improved NSGA-II algorithm. In order to verify the effectiveness of the proposed model and strategy, through the comparative experiment of NSGA and PSO, it can be seen from the experimental results that the three-level network allocation model and the improved NSGA-II algorithm (nondominated sorting genetic algorithm II) proposed in this paper can not only solve the existing postdisaster relief material allocation and scheduling problem but also reduce the space-time complexity of the problem. [ABSTRACT FROM AUTHOR]

The university course scheduling problem (UCSP) aims at optimally arranging courses to corresponding rooms, faculties, students, and timeslots with constraints. Previously, the university staff solved this thorny problem by hand, which is very time-consuming and makes it easy to fall into chaos. Even some meta-heuristic algorithms are proposed to solve UCSP automatically, while most only utilize one single algorithm, so the scheduling results still need improvement. Besides, they lack an in-depth analysis of the inner algorithms. Therefore, this paper presents a novel and practical approach based on Tabu search and simulated annealing algorithms for solving USCP. Firstly, the initial solution of the UCSP instance is generated by one construction heuristic algorithm, the first fit algorithm. Secondly, we defined one union move selector to control the moves and provide diverse solutions from initial solutions, consisting of two changing move selectors. Thirdly, Tabu search and simulated annealing (SA) are combined to filter out unacceptable moves in a parallel mode. Then, the acceptable moves are selected by one adaptive decision algorithm, which is used as the next step to construct the final solving path. Benefits from the excellent design of the union move selector, parallel tabu search and SA, and adaptive decision algorithm, the proposed method could effectively solve UCSP since it fully uses Tabu and SA. We designed and tested the proposed algorithm in one real-world (PKNU-UCSP) and ten random UCSP instances. The experimental results confirmed its effectiveness. Besides, the in-depth analysis confirmed each component's effectiveness for solving UCSP. [ABSTRACT FROM AUTHOR]

This paper studies the problem of scheduling n jobs on a single machine to minimize total completion time and maximum cost, simultaneously. Each job is associated with a positional deadline that indicates the largest ordinal number of this job in any feasible schedule. The jobs have agreeable release and processing times, meaning that jobs with larger release times also have larger processing times. The agreeability assumption is reasonable since both the single-criterion problems (without positional deadline constraints) of minimizing total completion time and maximum lateness on a single machine with arbitrary release and processing times are strongly NP-hard. An O (n 3) -time Pareto optimal algorithm is presented. The previously known algorithms only solve two special cases of the agreeability assumption: either the case of equal release times in O (n 4) time, or the case of equal processing times (without positional deadline constraints) in O (n 3) time. [ABSTRACT FROM AUTHOR]

Purpose: The cross-docking strategy has a significant influence on supply chain and logistics efficiency. This paper aims to investigate the most suitable and efficient way to schedule the transfer of logistics activities and present a meta-heuristic method of the truck scheduling problem in cross-docking logistics. A truck scheduling problem with products time window is investigated with objectives of minimizing the total product transshipment time and earliness and tardiness cost of outbound trucks. Design/methodology/approach: This research proposed a meta-heuristic method for the truck scheduling problem with products time window. To solve the problem, a lower bound of the problem is built through a novel two-stage Lagrangian relaxation problem and on account of the NP-hard nature of the truck scheduling problem, the novel red deer algorithm with the mechanism of the heuristic oscillating local search algorithm, as well as adaptive memory programming was proposed to overcome the inferior capability of the original red deer algorithm in the aspect of local search and run time. Findings: Theory analysis and simulation experiments on an industrial case of a cross-docking center with a product's time window are conducted in this paper. Satisfactory results show that the performance of the red deer algorithm is enhanced due to the mechanism of heuristic oscillating local search algorithm and adaptive memory programming and the proposed method efficiently solves the real-world size case of truck scheduling problems in cross-docking with product time window. Research limitations/implications: The consideration of products time window has very realistic significance in different logistics applications such as cold-chain logistics and pharmaceutical supply chain. Furthermore, the novel adaptive memory red deer algorithm could be modified and applied to other complex optimization scheduling problems such as scheduling problems considering energy-efficiency or other logistics strategies. Originality/value: For the first time in the truck scheduling problem with the cross-docking strategy, the product's time window is considered. Furthermore, a mathematical model with objectives of minimizing the total product transshipment time and earliness and tardiness cost of outbound trucks is developed. To solve the proposed problem, a novel adaptive memory red deer algorithm with the mechanism of heuristic oscillating local search algorithm was proposed to overcome the inferior capability of genetic algorithm in the aspect of local search and run time. [ABSTRACT FROM AUTHOR]

Fitness landscape analysis is a tool that can help us gain insight into a problem, determine how hard it is to solve a problem using a given algorithm, choose an algorithm for solving a given problem, or choose good algorithm parameters for solving the problem. In this paper, fitness landscape analysis of hyperheuristics is used for clustering instances of three scheduling problems. After that, good parameters for tree-based genetic programming that can solve a given scheduling problem are calculated automatically for every cluster. Additionally, we introduce tree editing operators which help in the calculation of fitness landscape features in tree based genetic programming. A heuristic is proposed based on introduced operators, and it calculates the distance between any two trees. The results show that the proposed approach can obtain parameters that offer better performance compared to manual parameter selection. [ABSTRACT FROM AUTHOR]

Summary: Shared transportation is a new way of traveling generated by the rapid development of the "Internet +" and the sharing economy. Due to the limited energy carried by shared e‐bikes, the energy problem becomes the primary obstacle restricting its development. At present, one way to solve the energy problem is to use mobile charging vehicles (MCVs). However, how to schedule MCVs to achieve fast response, reduce energy consumption, and improve charging efficiency is crucial. In this paper, we propose a Charging Scheduling scheme based on Dynamic Characteristic of shared e‐bike in Obstacle Space (CSDC‐OS). Firstly, we design two MCV departure mechanisms to solve the problems of low utilization of MCVs and long waiting time for shared e‐bikes. Then, we design the schedulability conditions based on the A‐star algorithm and the dynamic change of e‐bikes to ensure that MCVs can return to the service station in time. Finally, we propose a charging sequence algorithm based on linear skyline query and a selective insertion algorithm to improve the charging efficiency of MCVs. Simulation results show that the CSDC‐OS can improve the response time, mobile consumption, and charging efficiency by more than 8% on average. [ABSTRACT FROM AUTHOR]

Parallel machine scheduling is one of the most common studied problems in recent years, however, this classic optimization problem has to achieve two conflicting objectives, i.e. minimizing the total tardiness and minimizing the total wastes, if the scheduling is done in the context of plastic injection industry where jobs are splitting and molds are important constraints. This paper proposes a mathematical model for scheduling parallel machines with splitting jobs and resource constraints. Two minimization objectives - the total tardiness and the number of waste - are considered, simultaneously. The obtained model is a bi-objective integer linear programming model that is shown to be of NP-hard class optimization problems. In this paper, a novel Multi-Objective Volleyball Premier League (MOVPL) algorithm is presented for solving the aforementioned problem. This algorithm uses the crowding distance concept used in NSGA-II as an extension of the Volleyball Premier League (VPL) that we recently introduced. Furthermore, the results are compared with six multi-objective metaheuristic algorithms of MOPSO, NSGA-II, MOGWO, MOALO, MOEA/D, and SPEA2. Using five standard metrics and ten test problems, the performance of the Pareto-based algorithms was investigated. The results demonstrate that in general, the proposed algorithm has supremacy than the other four algorithms. [ABSTRACT FROM AUTHOR]

This paper deals the scheduling identical parallel batch-processing machines (BPMs) that each machine can be process a group of jobs as a batch simultaneously. The paper presents a new bi-objective-mixed integer linear programming model for BPM in which arbitrary job size, unequal release time and capacity limits are considered as realistic assumptions occur in the manufacturing environments. The objectives are to minimise the makespan and the total weighted earliness and tardiness of jobs (just in time). After developing a new bi-objective model, anɛ-constraint method is proposed to solve the problem. This problem has been known as Np-hard. Therefore, two multi-objective optimisation methods, namely, fast non-dominated sorting genetic algorithm (NSGA-II) and multi-objective imperialist competitive algorithm (MOICA) are employed to find the pareto-optimal front for large-sized problems. The parameters of the proposed algorithms are calibrated using Response surface methodology (RSM) and the performances of the proposed algorithms on the problems of various sizes are analysed and the computational results clarify that MOICA outperform than NSGA-II in quality of solutions and computational time. [ABSTRACT FROM PUBLISHER]

Multi-objective evolutionary algorithms (MOEAs) have been successfully employed to solve many scientific and engineering problems. However, many algorithms perform ill in maintaining diversity and convergence simultaneously. In this paper, we devised a novel operator selection framework based on two collaborative indicators, generational distance (GD) and maximum spread (MS) to improve the diversity while maintaining a good convergence. By calculating the variation of GDs and MSs over the past 7 iterations, an instruction is conveyed to select a proper operator to execute next 7 iterations. This process is repeated until it reaches the maximum iteration. Two operators are embedded in this algorithm which are differential evolution operator (DE/rand/1) and our proposed crow search operator which is deemed to be efficient in explorating the search space. MOEA/D is utilized as the basis framework of our proposed algorithm. Experiments indicate that our proposed algorithm is valid and outperforms other famous algorithms in terms of diversity and convergence. In the end, a particular aeroengine maintenance scheduling problem is solved by our proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper proposes a single machine scheduling problem with learning-effect and release times by considering two objectives requiring minimization of makespan and total tardiness, simultaneously. Due to the NP-hardness of this problem, two memetic algorithms with meme variants are presented for solving the bi-objective problem and applied by combining three different scalarization methods, including weighted sum, conic, and tchebycheff. The performance of all memetic algorithms with the meme is investigated across randomly generated twenty-seven test problems ranging from 'small' to 'large' size. The experimental results indicate that the Multimeme Memetic Algorithm using the tchebycheff outperforms the other algorithms producing the best-known results for almost all bi-objective single machine scheduling instances with learning-effects. All algorithms perform effectively in solving large-sized problems with up to 200 jobs. [ABSTRACT FROM AUTHOR]

This paper deals with fuzzy multi-depot bus scheduling (FMDBS) problem in which the objective function and constraints are defined with fuzzy attributes. Credibility relation is used to formulate the problem as an integer multicommodity flow problem. A novel combination of branch-and-price and heuristic algorithms, is proposed to efficiently solve FMDBS problem. In the proposed algorithm, the heuristic algorithm is applied to generate initial columns for the column generation method. Also, a heuristic algorithm is used to improve the generated solutions in each node of the branch-and-price tree. Two sets of benchmark examples are applied to demonstrate the efficiency of the proposed algorithm for large-scale instances. Also, the algorithm is applied to solve the classical multi-depot bus scheduling problem. The results show that the proposed algorithm decreases integrality gap and computational time in comparison with the state-of-the-art algorithms and normal branch-and-price algorithm. Finally, as a case study, the bus schedules in Tehran BRT network are generated. [ABSTRACT FROM AUTHOR]

Cloud providers deliver heterogeneous virtual machines to run complicated jobs submitted by users. The task scheduling issue is formulated to a discrete optimization problem which is well-known NP-Hard. This paper presents a hybrid meta-heuristic algorithm based on genetic and thermodynamic simulated annealing algorithms to solve this problem. In the proposed algorithm, the genetic and simulated annealing algorithms have respective global and local search inclinations covering each other's shortcomings. A novel theorem is presented and applied to produce a semi-conducted initial population. In a used genetic algorithm with a global trend, the crossover operator is performed to explore search space. The thermodynamic simulated annealing algorithm is utilized to improve the efficiency, which considers entropy and energy difference concepts in the cooling schedule process. After obtaining a suitable solution, one of the three novel neighbor operators is randomly called to enhance the given solution potentially. In this way, the efficient balance between exploration and exploitation in the search space is achieved. Simulation results prove that the proposed hybrid algorithm has 10.17%, 9.31%, 7.76%, and 8.21% dominance in terms of makespan, schedule length ratio, speedup, and efficiency against other comparative algorithms. [ABSTRACT FROM AUTHOR]

At present, resource configuration of mobile cloud computing has received extensive attention from the outside world. Most of the similar resource scheduling configuration fails to comprehensively consider the dynamics of mobile terminals and the difference in user requested resources. Therefore, considering uncertainty in paging scheduling under mobile cloud resource environment from the perspective of consumers has become the key to solving the problem of resource allocation in the mobile cloud computing environment. This paper proposes an adaptive matching resource allocation algorithm based on uncertain factors under mobile cloud computing environment. Uncertain factors of the mobile terminal are derived via QoS attribute, and then user information and load characteristics of the user requested resources are analyzed through CLIQUE similarity matching. Afterwards, based on the mapping between similarity and resources, resource paging allocation can be carried out based on adaptive matching resource allocation algorithm. From the perspective of consumers, dynamics of mobile terminals and uncertainty of paging scheduling in the mobile cloud resource environment under different user requested resources can be considered to allow minimized delay and optimized paging strategies. [ABSTRACT FROM AUTHOR]

This work is interested to optimize the job shop scheduling problem with a no wait constraint. This constraint occurs when two consecutive operations in a job must be processed without any waiting time either on or between machines. The no wait job shop scheduling problem is a combinatorial optimization problem. Therefore, the study presented here is focused on solving this problem by proposing strategy for making Jaya algorithm applicable for handling optimization of this type of problems and to find processing sequence that minimizes the makespan (Cmax). Several benchmarks are used to analyze the performance of this algorithm compared to the best-known solutions. [ABSTRACT FROM AUTHOR]

In order to solve the problems of uneven resource utilization and long task completion time in complex task group scheduling, this paper constructed a complex task group resource scheduling model to minimize the mean square error of resource load and the task group completion time, and proposed a multi-objective optimization algorithm based on boundary range local search and NSGA-Ⅱ, called BRLSN. The algorithm used an effective coding method and cross mutation operator for iterative optimization, and constructed an elite retention strategy based on local search in boundary region to expand the search scope of the algorithm and preserved good individuals in the population. Experimental results show that compared with other multi-objective algorithms, the convergence and diversity of BRLSN are significantly improved. At the same time, the algorithm convergence speed is faster, the population quality is higher, and the result value of the final objective function is obviously optimized. [ABSTRACT FROM AUTHOR]

Medium-term optimal scheduling of hydropower plants (MOSHPP) should be frequently updated for recurring extreme precipitation events in China to reduce spillage and increase power generation; however, the curse of dimensionality makes obtaining a satisfactory solution in an acceptable time difficult. In this paper, a parallel improved dynamic programming with successive approximation (PIDPSA) for MOSHPPs is proposed to improve the solution quality and meet time requirements. The solution quality is improved by successive approximation of multiple plants instead of one plant for considering more hydraulic connections, a state space reduction strategy combined with constraint preprocessing is adopted to reduce unnecessary calculations and the fine-grained parallelism based on the fork/join framework is employed to greatly shorten the solution time. The proposed method was applied to 11 hydropower cascade plants in the Lancang River with a time horizon of 30 days. The results showed that higher quality solutions can be obtained by IDPSA than conventional methods and DPSA, and the space reduction strategy can effectively improve the solution efficiency. The computation time of PIDPSA decreased from 81345 s for the single-core environment to 6073 s for the 32-core environment, which proves the high efficiency and practical value of PIDPSA for solving MOSHPP problems. [ABSTRACT FROM AUTHOR]

The Workload Allocation Problem consists of assigning a sequence of | S | operations to workers. The order of these operations is fixed. Each operation consists of a batch of B units, hence a total of | J | jobs have to be performed. Each worker is assigned to an ordered subset of consecutive jobs. Workers have different skills, and therefore jobs take a variable time to process, depending on the assigned worker. The study of this problem is rooted in the operations of Calzedonia. In this paper, we briefly introduce the application before presenting algorithms for solving the problem exactly and heuristically. Our computational results compare the performance of a stand-alone mathematical formulation solved by CPLEX, a sequential exact algorithm, and a metaheuristic, with a simple heuristic implemented in the company. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the one-machine scheduling problem with release and delivery times with the minimum makespan objective. Both heuristics and branch-and-bound algorithms have been formulated for the problem. One such branch-and-bound algorithm solves the problem and a variation that requires a delay between the completion of one job and the start of another (delayed precedence constraints). This paper analyzes key components of this branch-and-bound algorithm and proposes an improved heuristic to be used in conjunction with a different search strategy. Computational experiments demonstrate that the modifications lead to substantial improvements in running time and number of iterations on the one-machine problem instances both with and without delayed precedence constraints. [ABSTRACT FROM AUTHOR]

This paper addresses the flexible-job-shop scheduling problem (FJSP) with the objective of minimising total tardiness. FJSP is the generalisation of the classical job-shop scheduling problem. The difference is that in the FJSP problem, the operations associated with a job can be processed on any set of alternative machines. We developed a new algorithm by hybridising genetic algorithm and variable neighbourhood search (VNS). The genetic algorithm uses advanced crossover and mutation operators to adapt the chromosome structure and the characteristics of the problem. Parallel-executed VNS algorithm is used in the elitist selection phase of the GA. Local search in VNS uses assignment of operations to alternative machines and changing of the order of the selected operation on the assigned machine to increase the result quality while maintaining feasibility. The purpose of parallelisation in the VNS algorithm is to minimise execution time. The performance of the proposed method is validated by numerical experiments on several representative problems and compared with adapted constructive heuristic algorithms’ (earliest due date, critical ratio and slack time per remaining operation) results. [ABSTRACT FROM PUBLISHER]

In order to solve the trust problem and resource scheduling efficiency problem in the current cloud manufacturing system, this paper researched the application of block chain technology in cloud manufacturing system. Firstly, this paper expounded the significance of applying blockchain technology to cloud manufacturing system, and proposed a cloud manufacturing system based on blockchain technology. Secondly, this paper designed the manufacturing resource scheduling mode based on smart contract. And constructed the resource scheduling model aim to with the minimum manufacturing cost, the shortest time and the highest qualification rate. The model used differential evolution algorithm to solve. Finally, it simulated the experiment . The simulation results show the resource scheduling method based on the blockchain technology in the smart contract not only ensures the mutual trust between the participants in the system, but also effectively improves the resource scheduling efficiency and the superiority of the resource scheduling scheme of the cloud manufacturing system. [ABSTRACT FROM AUTHOR]

Resource-constrained project scheduling problem (RCPSP) is a kind of representative practical engineering problem, the purpose is to schedule activities in the project through rational use of limited resources in the minimum time. This paper proposes an improved hybrid cuckoo algorithm (CS&SA) to solve the RCPSP problem. Firstly, the individual elements are randomly coded into priority vectors, and the population is decoded using serial scheduling to convert the individual into a set of task scheduling sequences. Secondly, the Levy flight is redesigned to change the algorithm from random walk to adaptive as the population fitness changes. Then, this article adds three neighborhood update techniques to meet the update requirements of the algorithm at different stages. Finally, in order to prevent the algorithm from falling into a local optimum, this paper introduces a simulated annealing strategy to allow the algorithm to accept some individuals with poor quality with a certain probability in each iteration. In the testing part, this paper firstly tests the effectiveness and optimization of three different-scale examples in the classic example library PSPLIB for RCPSP problems. Among them, the average error of the CS&SA algorithm in the small-scale J30 is 0.25%, and the average error in the medium-scale J60 is 11.21%, and the average error of the large-scale J120 is 19.83%. Then, by comparing other intelligent optimization algorithms, it is proved that NCS&SA is superior to other algorithms in optimization and accuracy. [ABSTRACT FROM AUTHOR]

We consider a variant of the NP-hard problem of assigning jobs to machines to minimize the completion time of the last job. Usually, precedence constraints are given by a partial order on the set of jobs, and each job requires all its predecessors to be completed before it can start. In this paper, we consider a different type of precedence relation that has not been discussed as extensively and is called OR-precedence. In order for a job to start, we require that at least one of its predecessors is completed—in contrast to all its predecessors. Additionally, we assume that each job has a release date before which it must not start. We prove that a simple List Scheduling algorithm due to Graham (Bell Syst Tech J 45(9):1563–1581, 1966) has an approximation guarantee of 2 and show that obtaining an approximation factor of 4 / 3 - ε is NP-hard. Further, we present a polynomial-time algorithm that solves the problem to optimality if preemptions are allowed. The latter result is in contrast to classical precedence constraints where the preemptive variant is already NP-hard. Our algorithm generalizes previous results for unit processing time jobs subject to OR-precedence constraints, but without release dates. The running time of our algorithm is O (n 2) for arbitrary processing times and it can be reduced to O(n) for unit processing times, where n is the number of jobs. The performance guarantees presented here match the best-known ones for special cases where classical precedence constraints and OR-precedence constraints coincide. [ABSTRACT FROM AUTHOR]

This paper studies linear non-increasing processing times and the common/slack due window assignment problems on a single machine, where the actual processing time of a job is a linear non-increasing function of its starting time. The aim is to minimize the sum of the earliness cost, tardiness cost, due window location and due window size. Some optimality results are discussed for the common/slack due window assignment problems and two O(nlogn) time algorithms are presented to solve the two problems. Finally, two examples are provided to illustrate the correctness of the corresponding algorithms. [ABSTRACT FROM PUBLISHER]

Copyright of Control Theory & Applications / Kongzhi Lilun Yu Yinyong is the property of Editorial Department of Control Theory & Applications and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

In order to solve the problems of long path planning time and large number of redundant points in the rapidly-exploring random trees algorithm, this paper proposed an improved algorithm based on the parent point priority determination strategy and the real-time optimization strategy to optimize the rapidly-exploring random trees algorithm. First, in order to shorten the path-planning time, the parent point is determined before generating a new point, which eliminates the complicated process of traversing the random tree to search the parent point when generating a new point. Second, a real-time optimization strategy is combined, whose core idea is to compare the distance of a new point, its parent point, and two ancestor points to the target point when a new point is generated, choosing the new point that is helpful for the growth of the random tree to reduce the number of redundant points. Simulation results of 3-dimensional path planning showed that the success rate of the proposed algorithm, which combines the strategy of parent point priority determination and the strategy of real-time optimization, was close to 100%. Compared with the rapidly-exploring random trees algorithm, the number of points was reduced by more than 93.25%, the path planning time was reduced by more than 91.49%, and the path length was reduced by more than 7.88%. The IRB1410 manipulator was used to build a test platform in a laboratory environment. The path obtained by the proposed algorithm enables the manipulator to safely avoid obstacles to reach the target point. The conclusion can be made that the proposed strategy has a better performance on optimizing the success rate, the number of points, the planning time, and the path length. [ABSTRACT FROM AUTHOR]

6G vehicle-to-everything (V2X) communication will be combined with vehicle automatic driving technology and play an important role in automatic driving. However, in 6G V2X systems, vehicle users have the characteristics of high-speed movement. Therefore, how to provide stable and reliable wireless link quality and improve channel gain has become a problem that must be solved. To solve this problem, a new multi-user scheduling algorithm based on block diagonalization (BD) precoding for 6G ultra-massive multiple-input multiple-output (MIMO) systems is proposed in this paper. The algorithm takes advantage of the sensitive nature of BD precoding to channel correlation, uses the Pearson coefficient after matrix vectorization to measure the channel correlation between users, defines the scheduling factor to measure the channel quality according to the user noise enhancement factor, and jointly considers the influence of the correlation between user channels and channel quality, ensuring the selection of high-quality channels while minimizing channel correlation. Simulation results show that compared with the multi-user scheduling algorithm based on subspace correlation, condition number, and geometric angle, the proposed algorithm can obtain higher user channel gain, effectively reduce the system bit error rate, and can be applied to 6G V2X communication. [ABSTRACT FROM AUTHOR]

In this paper, we consider a two parallel machine problem where each machine has a fixed and known unavailable period. The objective is to minimize the makespan. In the literature, the problem has been considered for the case in which there is only one unavailable period on either one of the machines. This paper extends the results to two unavailable periods, one for each machine. For each of the different cases of the problem, an algorithm is developed to find the optimal solution. Although all the proposed algorithms have exponential time complexities, they are quite efficient in solving large problems. Computational results for problems with up to 1000 jobs are reported. [ABSTRACT FROM AUTHOR]

We address in this paper the two-machine job shop scheduling problem with a single server that sets up the jobs before they get processed on the machines. The server is only needed during the set-up and becomes free at the end of this phase. Moreover, the set-ups are non-anticipatory and the set-up times are sequence-independent. We seek a schedule that minimizes the overall completion time, also called the makespan. We propose several lower bounds to the problem and prove the N P -hardness in the strong sense of two restricted cases. In addition, we present a linear time algorithm for a special case. In order to solve the general problem, we develop a genetic and simulated annealing algorithms that use feasibility guaranteed procedures. An experimental study is carried out to analyze the performance of these meta-heuristic methods. [ABSTRACT FROM AUTHOR]

Industrial scheduling problems (ISPs), especially industrial production workshop scheduling problems (IPWSPs) in various sectors like manufacturing, and power require allocating resources to tasks within multiple constraints. Addressing these complex challenges involves computationally solving problems with numerous variables and constraints. Lagrangian relaxation-based algorithms (LRAs) effectively tackle ISPs (particularly IPWSPs) by relaxing constraints through multipliers. While LRAs may violate original constraints, heuristic algorithms rectify this by crafting feasible solutions. LRAs offer efficient problem-solving and yield high-quality results with manageable computational effort. This review presents the cutting-edge LRAs for ISPs, based on 200 papers from the fields of supply chain, manufacture, power, etc. It exemplifies LRAs' principles through practical cases, and provides a classification of problems in detail, along with LRA's problem-solving process. We discuss strengths, weaknesses, and future research prospects, offering comprehensive guidance. Summarizing these findings, the review enhances understanding of LRAs' application potential in solving ISPs for practitioners and researchers. • Propose tutorials & examples for mastering ISP solving with LRAs. • Demonstrate an algorithm framework and diverse solution designs. • List pros & cons of using LRAs and analyze applicable scenarios. • Organize LRA development stages and future research directions. [ABSTRACT FROM AUTHOR]

With the development of vehicles towards intelligence and connectivity, vehicular data is diversifying and growing dramatically. A task allocation model and algorithm for heterogeneous Intelligent Connected Vehicle (ICV) applications are proposed for the dispersed computing network composed of heterogeneous task vehicles and Network Computing Points (NCPs). Considering the amount of task data and the idle resources of NCPs, a computing resource scheduling model for NCPs is established. Taking the heterogeneous task execution delay threshold as a constraint, the optimization problem is described as the problem of maximizing the utilization of computing resources by NCPs. The proposed problem is proven to be NP-hard by using the method of reduction to a 0–1 knapsack problem. A many-to-many matching algorithm based on resource preferences is proposed. The algorithm first establishes the mutual preference lists based on the adaptability of the task requirements and the resources provided by NCPs. This enables the filtering out of un-schedulable NCPs in the initial stage of matching, reducing the solution space dimension. To solve the matching problem between ICVs and NCPs, a new many-to-many matching algorithm is proposed to obtain a unique and stable optimal matching result. The simulation results demonstrate that the proposed scheme can improve the resource utilization of NCPs by an average of 9.6% compared to the reference scheme, and the total performance can be improved by up to 15.9%. [ABSTRACT FROM AUTHOR]

This paper studies the online hierarchical scheduling problem on two uniform machines with rejection. Two uniform machines M1, M2 run at the speeds of s ∈ (0, +∞), 1 separately; and they are provided with different capabilities. Each machine has a certain GOS level 1 or 2 and every job is also associated with a hierarchy 1 or 2. The job can only be assigned to the machine whose GOS level does not exceed the job's hierarchy. Preemption is permitted but idle is not introduced. Jobs come one by one over list. When a job arrives, it can be accepted and scheduled on some machine or rejected by paying its penalty. The objective is to minimize the sum of makespan yielded by accepted jobs and total penalties of all rejected jobs. For this problem, we propose a family of several online algorithms according to the range of s and the related lower bound is also obtained. These algorithms achieve optimal competitive ratio when s ∈ (0, 1) ∪ [1.618, +∞), but have a small gap between upper bound and lower bound in interval [1, 1.618). [ABSTRACT FROM AUTHOR]

Job learning and deterioration coexist in many realistic machine-job scheduling situations. However, in literature, the constructed forms of the machine scheduling models with job learning and/or deteriorating effects were specific types of functions, which constrained their applicability in practice. This paper introduces a new single-machine scheduling model, where the actual processing time of a job is a general function of its starting time as well as scheduled position, which shows a broad generalization in contrast to that of certain existing models. For three objectives corresponding to the single-machine scheduling problem-total weighted completion time, discounted total weighted completion time, and maximum lateness - this paper presents their respective approximation result on the basis of the worst-case bound analysis from the optimal algorithm. The results demonstrate that under our proposed model, minimization of scheduling operations such as the makespan, sum of the kth power of completion times, and total lateness are polynomially solvable. Moreover, under some feasible conditions for the scheduling parameters, the minimum optimization problems of the total weighted completion time, discounted total weighted completion time, maximum lateness, and total tardiness are all recognized as polynomial forms and their solutions are provided. [ABSTRACT FROM AUTHOR]

In the edge computing network environment, our applications can be deployed on edge servers. The request to execute the application can be produced on the edge device and transmitted to the edge server for calculation. A complex request may be divided into multiple computing tasks and transmitted to different servers and then parallel calculated before obtaining the final result. How to schedule computing tasks in multiple requests so that all requests can be completed faster is a difficult problem, especially in the edge computing environment where we should consider the communicating work and the calculating work simultaneously. In this paper, we first build a task dependency model of the computing tasks included in the request based on the idea of dividing the method components of the application. The dependencies include sequence, selection and parallel. Then we propose an online scheduling algorithm MCOS based on optimizing the task with the maximum amount of calculation to solve the problem of the minimum sum of the completion time of all requests. In simulations, we show the algorithm MCOS has a better completion time. [ABSTRACT FROM AUTHOR]

In scheduling problems with two competing agents, each one of the agents has his own set of jobs and his own objective function, but both share the same processor. The goal is to minimize the value of the objective function of one agent, subject to an upper bound on the value of the objective function of the second agent. In this paper we study two-agent scheduling problems on a proportionate flowshop. Three objective functions of the first agent are considered: minimum maximum cost of all the jobs, minimum total completion time, and minimum number of tardy jobs. For the second agent, an upper bound on the maximum allowable cost is assumed. We introduce efficient polynomial time solution algorithms for all cases. [ABSTRACT FROM AUTHOR]

The deterministic permutation flow shop scheduling problem with makespan criterion is not solvable in polynomial time. Therefore, researchers have thought about heuristic algorithms. There are many heuristic algorithms for solving it that is a very important combinatorial optimization problem. In this paper, a new algorithm is proposed for solving the mentioned problem. The presented algorithm chooses the weighted path that starts from the up-left corner and reaches the down-right in the matrix of jobs processing times and calculates the biggest sum of the times in the footprints of this path. The row with the biggest sum permutes among all the rows of the matrix for locating the minimum of makespan. This method was run on Taillards standard benchmark and the solutions were compared with the optimum or the best ones as well as 14 famous heuristics. The validity and effectiveness of the algorithm are shown with tables and statistical evaluation. [ABSTRACT FROM AUTHOR]

In order to obtain efficiency and flexibility, assignment of machines' layout and determination of jobs' schedule on each machine are among the most important decisions. These decisions are interrelated and may impact each other but they are often treated separately or as a sequential decision in prior researches. In this paper, we propose a new approach to concurrently make the layout and scheduling decisions in a job shop environment. In other words, we consider an extension of the well-known job shop scheduling problem with transportation delay in which in addition to decisions made in the classic problem, the locations of machines have to be selected among possible sites. The only goal of the problem is the minimization of the makespan. A hybrid metaheuristic approach based on the scatter search algorithm is developed to tackle this problem. Using 43 randomly generated benchmark instances, the performance of the scatter search and its components are evaluated. We also applied our procedure to the classic job shop scheduling problems. Computational results show that our procedure is efficient. [ABSTRACT FROM AUTHOR]

In the past decades, resource parameters have been introduced in project scheduling literature to measure the scarceness of resources of a project instance. In this paper, we incorporate these resource scarceness parameters in the search process to solve the multi-mode resource constrained project scheduling problem, in which multiple execution modes are available for each activity in the project. Therefore, we propose a scatter search algorithm, which is executed with different improvement methods, each tailored to the specific characteristics of different renewable and nonrenewable resource scarceness values. Computational results prove the effectiveness of the improvement methods and reveal that the procedure is among the best performing competitive algorithms in the open literature. [ABSTRACT FROM AUTHOR]

In the paper, single machine scheduling problems with a learning effect and a rate-modifying activity are considered. Under the learning effect, the processing time of a job is a decreasing function of its position in the sequence. The rate-modifying activity is an event that can change the speed of the machine, and hence the processing time of jobs after the activity. The following objective functions are considered: the makespan, the total earliness, tardiness and completion time penalty, and the total earliness, tardiness, due-window starting time and due-window size penalty. Polynomial time algorithms are proposed to optimally solve the problems. [ABSTRACT FROM AUTHOR]

In this paper, we consider a semi-online preemptive scheduling problem on two uniform machines, where we assume that all jobs have sizes between p and rp for some p > 0 and r ≥ 1. The goal is to maximize the continuous period of time (starting from time zero) when both machines are busy. We present an optimal semi-online algorithm for any combination of the job size ratio r and machine speed ratio s. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Chongqing University of Posts & Telecommunications (Natural Science Edition) is the property of Chongqing University of Posts & Telecommunications and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The vehicular participatory sensing network (VPSN) is now becoming more and more prevalent, and additionally has shown its great potential in various applications. A general VPSN consists of many tasks from task, publishers, trading platforms and a crowd of participants. Some literature treats publishers and the trading platform as a whole, which is impractical since they are two independent economic entities with respective purposes. For a trading platform in markets, its purpose is to maximize the profit by selecting tasks and recruiting participants who satisfy the requirements of accepted tasks, rather than to improve the quality of each task. This scheduling problem for a trading platform consists of two parts: which tasks should be selected and which participants to be recruited? In this paper, we investigate the scheduling problem in vehicular participatory sensing with the predictable mobility of each vehicle. A genetic-based trading scheduling algorithm (GTSA) is proposed to solve the scheduling problem. Experiments with a realistic dataset of taxi trajectories demonstrate that GTSA algorithm is efficient for trading platforms to gain considerable profit in VPSN. [ABSTRACT FROM AUTHOR]

For the path planning of quad-rotor UAVs, the traditional RRT* algorithm has weak exploration ability, low planning efficiency, and a poor planning effect. A TD-RRT* algorithm based on target bias expansion and dynamic step size is proposed herein. First, random-tree expansion is combined with the target bias strategy to remove the blindness of the random tree, and we assign different weights to the sampling point and the target point so that the target point can be quickly approached and the search speed can be improved. Then, the dynamic step size is introduced to speed up the search speed, effectively solving the problem of invalid expansion in the process of trajectory generation. We then adjust the step length required for the expansion tree and obstacles in real time, solve the opposition between smoothness and real time in path planning, and improve the algorithm's search efficiency. Finally, the cubic B-spline interpolation method is used to modify the local inflection point of the path of the improved RRT* algorithm to smooth the path. The simulation results show that compared with the traditional RRT* algorithm, the number of iterations of path planning of the TD-RRT* algorithm is reduced, the travel distance from the starting position to the end position is shortened, the time consumption is reduced, the path route is smoother, and the path optimization effect is better. The TD-RRT* algorithm based on target bias expansion and dynamic step size significantly improves the planning efficiency and planning effect of quad-rotor UAVs in a three-dimensional-space environment. [ABSTRACT FROM AUTHOR]

An efficiency improvement of product transport through pipeline networks can be obtained by a better allocation of available resources. That is a hard combinatorial problem with multi-objective optimization characteristics due to different types of products to be moved and the high occupance rate of the network. This paper presents a novel modified shuffled frog leaping algorithm, named modified shuffled frog leaping Pareto approach (MSFLPA), to solve this resource allocation problem. This new algorithm combines the use of a small population and an archiving strategy with a procedure to restart the population using two auxiliary memories to store nondominated solutions (Pareto set) found during population evolution. To validate the performance and efficiency of the proposed MSFLPA in spread Pareto front, five Zitzler-Deb-Thiele functions are examined and compared against two well-known multi-objective genetic algorithms: NSGA-II and SPEA2. The numerical experiments indicate that MSFLPA yields spread solutions and converges to the true Pareto front, and it is verified to be efficient and competitive for solving multi-objective problem. After this validation, the MSFLPA is used to optimize the allocation of resources and to solve the scheduling problem of a real-world pipeline network and if compared with NSGA-II and $$\mu \hbox {GA}$$ , MSFLPA is verified to be a new effective alternative for solving multi-objective scheduling problems with more than two objectives as it is the case of the pipeline scheduling problems. [ABSTRACT FROM AUTHOR]

This study focuses on the maximization of the minimum completion time using identical parallel processors. The objective of this maximization is to ensure fair distribution. A set of processes is to be scheduled to several identical parallel processors, and this problem is proved as NP-hard. The research for this paper is based primarily on the performance of the proposed heuristics with other methods cited in the literature review. Our heuristics are developed mainly using the randomization method and the iterative utilization of the knapsack problem to solve the above-mentioned problem. The heuristics are assessed by several instances represented in the experimental results. The results shew that the knapsack-based heuristic provides a performance that is almost like the heuristic in the literature review but with better running time. [ABSTRACT FROM AUTHOR]

Necklace maps visualize quantitative data associated with regions by placing scaled symbols, usually disks, without overlap on a closed curve (the necklace) surrounding the map regions. Each region is projected onto an interval on the necklace that contains its symbol. In this paper we address the algorithmic question how to maximize symbol sizes while keeping symbols disjoint and inside their intervals. For that we reduce the problem to a one-dimensional problem which we solve efficiently. Solutions to the one-dimensional problem provide a very good approximation for the original necklace map problem. We consider two variants: Fixed-Order, where an order for the symbols on the necklace is given, and Any-Order where any symbol order is possible. The Fixed-Order problem can be solved in O(n log n) time. We show that the Any-Order problem is NP-hard for certain types of intervals and give an exact algorithm for the decision version. This algorithm is fixed-parameter tractable in the thickness K of the input. Our algorithm runs in O(n log n + n2K4K) time which can be improved to O(n log n + nK2K) time using a heuristic. We implemented our algorithm and evaluated it experimentally. [ABSTRACT FROM AUTHOR]

In the process of the integrated scheduling of multi-variety and small-batch complex products, the process structure and attribute characteristics are often ignored, which affects the overall scheduling effect. Aiming at solving this problem, a heuristic integrated scheduling algorithm (HIS-IDA) based on the improved Dijkstra algorithm is proposed. The algorithm takes the processing time of the process itself as the path value of the preceding and the following adjacent processes. Firstly, the improved Dijkstra algorithm prioritized the scheduling of the process sequence with long longitudinal paths and realized the "longitudinal optimization" of the integrated scheduling. Secondly, the layer priority strategy is used to shorten the interval time of process processing and realize the "horizontal optimization" of integrated scheduling. On the basis of "vertical and horizontal optimization", the idle time of the equipment is further reduced by using the process priority strategy of the leaf node, and the "idle optimization" of the integrated scheduling is realized, so as to optimize the overall effect of the integrated scheduling. The effectiveness and superiority of the algorithm are proved using comparison analysis. [ABSTRACT FROM AUTHOR]