Search

In this paper, we address the problem of scheduling jobs on identical machines for minimising the maximum completion time (makespan). Each job requires a sequence-independent setup time, which represents the time needed to prepare the machines for job execution. Then, we introduce a dynamic programme to solve the case with two machines, and show that this problem admits a fully polynomial time approximation scheme. For the case of m machines, we propose heuristics and an adapted genetic algorithm. Some numerical experiments are done to evaluate the proposed algorithms. [ABSTRACT FROM AUTHOR]

The electrical sector forces manufacturing companies of electrical solutions to continually innovate and implement new processes for greater efficiency. The growing demand for electrical energy, as well as the need to adapt to hybrid operations that combine multi-project operation models with continuous production models, requires efficient workflow management. Accordingly, this article proposes a Genetic Algorithm (GA) approach for solving the scheduling problem in a Flexible Hybrid Flow Shop (FHFS) environment considering a transfer batch approach to minimize makespan and total tardiness. The approach is inspired by a real-world application in the electrical industry and also accounts for unrelated parallel machines, precedence, release times, and due dates for jobs at each production center as key constraints. Three real-data scenarios were generated and evaluated. In the first scenario, a 7 % improvement in makespan was observed compared to real execution times. In Scenario 2, the makespan improved significantly by 33 %, and only 17.4 % of jobs were delayed, compared to 96 % in the real data. Likewise, GA showed a lightly better performance over Tabu Search (TS) in 3.01 % for makespan while the delayed jobs found by GA were 25 % below those obtained by TS. These results highlight the potential of the proposed method to improve overall production efficiency, not only in the electrical sector but also in similar industries. [ABSTRACT FROM AUTHOR]

The job shop scheduling problem (JSSP) is to find the optimal jobs sequence to optimise one or more performance indicators and makespan is the most common optimisation target. In solving NP-hard problems such as JSSPs by genetic algorithm (GA), trapping in local extremum, low search efficiency and instability are often encountered, especially unable to find the optimisation direction. To restrain this condition, a new neighbourhood structure with adaptive GA was put forward. The crossover probability (Pc) and mutation probability (Pm) can be adjusted in nonlinear and adaptive based on the dispersion of the fitness of population in the evolution. The idle time before critical operations can be made full use of through the multi-operations combination and adjustment. To research the performance of the proposed method in solving JSSPs, a detailed application scheme was given out for the process of it. In the solving scheme, the chromosome active decoding algorithm with the objective function of maximum makespan was proposed. From the results of testing of 28 JSSP benchmark instances in 3 adaptive strategies and 3 neighbourhood strategies, the new neighbourhood structure with adaptive GA has been significant improvement in solution accuracy and convergence efficiency. [ABSTRACT FROM AUTHOR]

Ensuring optimal load balancing is imperative for maintaining reliability and upholding quality of service as specified in service-level agreements (SLAs) for cloud computing providers. This research addresses the most common shortcomings of existing state-of-the-art methods, which often lack responsiveness and struggle to adapt to exponentially increasing demand, especially in the era of the internet of things (IoT). The proposed hybrid approach surpasses current literature approaches in performance metrics such as makespan, response time, number of cloudlet migrations, and SLA violations. It operates on two levels, initially employing a k-means clustering algorithm to group servers within each datacenter based on similar utilization rates. Subsequently, a round-robin method allocates task groups sequentially to non-overloaded clusters, and within each cluster, a genetic algorithm optimally assigns tasks to servers. This multilayered approach facilitates hot-deployment and scalability in operational cloud environments while promoting strong interoperability and decoupling of core mechanisms missions. Simulation experiments conducted on CloudSim Plus validate the superiority of our method, positioning it as a robust solution for enhancing load balancing and tasks scheduling in cloud environments, especially in the face of rapidly increasing IoT-related demands. [ABSTRACT FROM AUTHOR]

In this paper, we address the weighted multi-objective re-entrant owshop scheduling problem considering release dates in order to minimize makespan, total completion time, total tardiness, maximum idle time, and number of tardy jobs. Each job is taken into account with deterministic processing times, and release dates. The flow-shop comprised of two workshops in whose jobs are entered to the main workshop and after the first part of the processing, they are transferred to the second workshop and after this stage, the jobs are returned to the main workshop for the last part of the processing. We model the problem by a new mixed integer programming based on formulating sum of idle time as a new concept. Moreover, a hybrid evolutionary algorithm is proposed based on some dispatching rules, ant colony optimization, and genetic algorithm. The performance of the proposed algorithm on some test instances is compared to the mixed integer linear programming model as well as the state-of-the-art algorithms called genetic algorithm, tabu search, bio-geography based optimization, and artificial bee colony. The computational experiments show that our proposed approach outperforms other algorithms and the results indicate efficiency and capability of the proposed algorithm in comparison with the traditional algorithms. [ABSTRACT FROM AUTHOR]

The gate-based model is one of the leading quantum computing paradigms for representing quantum circuits. Within this paradigm, a quantum algorithm is expressed in terms of a set of quantum gates that are executed on the quantum hardware over time, subject to a number of constraints whose satisfaction must be guaranteed before running the circuit, to allow for feasible execution. The need to guarantee the previous feasibility condition gives rise to the Quantum Circuit Compilation Problem (QCCP). The QCCP has been demonstrated to be NP-Complete, and can be considered as a Planning and Scheduling problem. In this paper, we consider quantum compilation instances deriving from the general Quantum Approximation Optimization Algorithm (QAOA), applied to the MaxCut problem, devised to be executed on Noisy Intermediate Scale Quantum (NISQ) hardware architectures. More specifically, in addition to the basic QCCP version, we also tackle other variants of the same problem such as the QCCP-X (QCCP with crosstalk constraints), the QCCP-V (QCCP with variable qubit state initialization), as well as the QCCP-VX that includes both previous variants. All problem variants are solved using genetic algorithms. We perform an experimental study across a conventional set of instances taken from the literature, and show that the proposed genetic algorithm, termed G A VX , outperforms previous approaches in the literature. [ABSTRACT FROM AUTHOR]

Given the interest and complexity, of the hybrid flow shops (HFS) problem in industry, he has been extensively considered, the HFS, is a complex combinatorial problem supported in many original world applications. We consider a hybrid flow shop FH4(P3, P2)||Cmax to applied in this paper. In this papers we attempt to optimize the makespan which refers to the last task completion time by an adequate meta-heuristic algorithm based on electromagnetism mechanism (EM). We also present analysis on the performance of the EM-algorithm adapted to HFS scheduling problems. The electromagnetism-like mechanism method gave us efficient and fair results comparing to particle swarm and genetic algorithm. [ABSTRACT FROM AUTHOR]

Task allocation is an essential element for determining the capability of multi-UAV systems to perform various tasks. This paper presents a procedure called a "rebalancing algorithm" for generating task-performing routes in heterogeneous multi-UAV systems. The algorithm adopts a greedy-based heuristic approach to find solutions efficiently in dynamically changing environments. A novel variable named "loitering" is introduced to satisfy temporal constraints, resulting in improved performance compared to heuristic algorithms: a sequential greedy algorithm, a genetic algorithm, and simulated annealing. The rebalancing algorithm is divided into two phases to minimize the makespan, i.e., the initial allocation and reallocation phases. Simulation results demonstrate the proposed algorithm's effectiveness in highly constrained conditions and its suitability for heterogeneous systems. Additionally, the results show a reduction in calculation time and improved performance compared to the heuristic algorithms. [ABSTRACT FROM AUTHOR]

This paper considers the problem of minimising makespan on a single batch processing machine with flexible periodic preventive maintenance. This problem combines two sub-problems, scheduling on a batch processing machine with jobs' release dates considered and arranging the preventive maintenance activities on a batch processing machine. The preventive maintenance activities are flexible but the maximum continuous working time of the machine, which is allowed, is determined. A mathematical model for integrating flexible periodic preventive maintenance into batch processing machine problem is proposed, in which the grouping of jobs with incompatible job families, the starting time of batches and the preventive maintenance activities are optimised simultaneously. A method combining rules with the genetic algorithm is proposed to solve this model, in which a batching rule is proposed to group jobs with incompatible job families into batches and a modified genetic algorithm is proposed to schedule batches and arrange preventive maintenance activities. The computational results indicate the method is effective under practical problem sizes. In addition, the influences of jobs' parameters on the performance of the method are analyzed, such as the number of jobs, the number of job families, jobs' processing time and jobs' release time. [ABSTRACT FROM AUTHOR]

The job shop scheduling problem (JSSP) is a classical combinatorial optimization problem that exists widely in diverse scenarios of manufacturing systems. It is a well-known NP-hard problem, when the number of jobs increases, the difficulty of solving the problem exponentially increases. Therefore, a major challenge is to increase the solving efficiency of current algorithms. Modifying the neighborhood structure of the solutions can effectively improve the local search ability and efficiency. In this paper, a genetic Tabu search algorithm with neighborhood clipping (GTS_NC) is proposed for solving JSSP. A neighborhood solution clipping method is developed and embedded into Tabu search to improve the efficiency of the local search by clipping the search actions of unimproved neighborhood solutions. Moreover, a feasible neighborhood solution determination method is put forward, which can accurately distinguish feasible neighborhood solutions from infeasible ones. Both of the methods are based on the domain knowledge of JSSP. The proposed algorithmis compared with several competitive algorithms on benchmark instances. The experimental results show that the proposed algorithm can achieve superior results compared to other competitive algorithms. According to the numerical results of the experiments, it is verified that the neighborhood solution clipping method can accurately identify the unimproved solutions and reduces the computational time by at least 28%. [ABSTRACT FROM AUTHOR]

This paper elucidates an algorithmic methodology aimed at optimizing the scheduling on parallel machines to minimize the total Makespan and bolster preventive protections. The scenario under consideration involves a predetermined set of 'c' jobs, processed on 'd' parallel machines, with the stipulation of non-preemptive task execution and a single job assignment per machine at any given time. The context predominantly revolves around production planning scenarios with fixed delivery dates. A mixed-integer programming approach is leveraged in the study to attain minimization of the Makespan, a key focus of this analysis. The problem at hand is tackled effectively through the application of both Genetic Algorithm (GA) and CPLEX algorithmic strategies. A thorough numerical analysis follows, aimed at evaluating the performance measures. The findings of this analysis promise to shed significant light on the optimization of scheduling and preventive measures in parallel machines, thereby paving the way for future research in this sphere. [ABSTRACT FROM AUTHOR]

Scheduling complex applications as task graphs on finite computational resources assuring task interdependencies is a well-known NP-complete optimization problem. This problem is well-addressed for microprocessor systems but for Dynamically Reconfigurable Hardware (DRHW) systems in which, in addition to tasks, the reconfiguration time and complexity also have to be scheduled; this problem is more complicated. DRHW reconfiguration overhead is considerable and can be crucial for real-world applications. To deal with this overhead, in this paper, a meta-heuristic method named Graph-Oriented Simulated Annealing (GOSA) is proposed. By introducing an innovative graph and solution structures called schedule graphs, and also some controlling functions which are inherited from the nature of the problem, the proposed method adapts itself to the characteristics of the problem. This helps the algorithm to adjust its exploration and exploitation speed and accuracy according to the requirements of the given problem and consequently find high-quality solutions quickly. To demonstrate the performance of the proposed method, it was tested on several synthetic and real-world benchmark task graphs, and the results were compared with a selection of classic and state-of-the-art algorithms. The method is comprehensively evaluated by performing numerous experiments in terms of execution time, makespan, scalability, and reliability. The results of the experiments on benchmarks show that in terms of the quality of the solutions, GOSA outperforms BGA, HPSO-GA, and FATS by 17%, 13%, and 5%, respectively, and its execution time is considerably less than all competing algorithms. Moreover, according to the experiments done on synthetic graphs, the makespan of the solutions generated by GOSA, Genetic Algorithm (GA), and the Gxhaustive Search over the List Scheduler are improved on average by 7.2%, 8.1%, and 19.1%, respectively. The most significant achievement of the proposed method is its execution time which is 31 times faster than GA. Finally, the results confirm that the proposed method is scalable for large task graphs, and its reliability is superior. [ABSTRACT FROM AUTHOR]

Previous research focuses on approaches of deep reinforcement learning (DRL) to optimize diverse types of the single-objective dynamic flexible job shop scheduling problem (DFJSP), e.g., energy consumption, earliness and tardiness penalty and machine utilization rate, which gain many improvements in terms of objective metrics in comparison with metaheuristic algorithms such as GA (genetic algorithm) and dispatching rules such as MRT (most remaining time first). However, single-objective optimization in the job shop floor cannot satisfy the requirements of modern smart manufacturing systems, and the multiple-objective DFJSP has become mainstream and the core of intelligent workshops. A complex production environment in a real-world factory causes scheduling entities to have sophisticated characteristics, e.g., a job's non-uniform processing time, uncertainty of the operation number and restraint of the due time, avoidance of the single machine's prolonged slack time as well as overweight load, which make a method of the combination of dispatching rules in DRL brought up to adapt to the manufacturing environment at different rescheduling points and accumulate maximum rewards for a global optimum. In our work, we apply the structure of a dual layer DDQN (DLDDQN) to solve the DFJSP in real time with new job arrivals, and two objectives are optimized simultaneously, i.e., the minimization of the delay time sum and makespan. The framework includes two layers (agents): the higher one is named as a goal selector, which utilizes DDQN as a function approximator for selecting one reward form from six proposed ones that embody the two optimization objectives, while the lower one, called an actuator, utilizes DDQN to decide on an optimal rule that has a maximum Q value. The generated benchmark instances trained in our framework converged perfectly, and the comparative experiments validated the superiority and generality of the proposed DLDDQN. [ABSTRACT FROM AUTHOR]

Cloud Computing is no longer just a fad and announcement. Since the beginning of this decade and up to the present, cloud computing has changed and evolved. Workflows are employed in many different scientific disciplines to coordinate data demanding applications, but their virtualized apps, platforms, compute, and storage must be promptly provisioned, scaled, and released instantly. The vast majority of researchers agree that using scientific workflows as a paradigm to define, arrange, and communicate complex scientific analysis is helpful. Workflow scheduling aims to optimally assign and execute sequence of tasks on various virtual machine instances shared and controlled by the workflow scheduler. Numerous scheduling algorithms have been proposed to tackle difficult problems more quickly than metaheuristic ones due to the NP-complete nature of this problem and its dependence on theproblem size. Energy consumption has emerged as a major issue in the cloud computing environment, in addition to the standard quality of service(QoS) restrictions like time and cost to handle this issue. The goal of this paper is to develop the Dynamic Provisioning Based on Demand (DPBD) algorithm for workflow scheduling. While sequential task completion and task priority are design restrictions, the dual objectives of the cloud service are to minimize makespan and energy usage. Using the non-dominated sorting genetic algorithm (NSGA-II), the multi-objective optimization problem's Pareto optimal solutions are found. Our approach is validated by simulating a complex workflow application. [ABSTRACT FROM AUTHOR]

This paper proposes a genetic algorithm approach to solve the identical parallel machines problem with tooling constraints in job shop flexible manufacturing systems (JS-FMSs) with the consideration of tool wear. The approach takes into account the residual useful life of tools and allocates a set of jobs with specific processing times and tooling requirements on identical parallel machines. Two metrics are introduced to evaluate the scheduling decisions and optimize the scheduling process, with the competitive goal of maximizing tool utilization and minimizing production makespan. The proposed approach searches for a set of optimal solutions on the Pareto front that offers the best possible balance between these two objectives, achieving optimal local performance in terms of both makespan and tool utilization. The approach is implemented with a customized genetic algorithm and validated on a real case study from a company operating in the aerospace sector, which confirms its effectiveness in increasing tool utilization and reducing the makespan. The results show that the proposed approach has significant practical implications for the manufacturing industry, particularly in the production of high-value materials such as those in the aerospace sector that require costly tools. This paper contributes to the operational research community by providing advanced scheduling algorithms that can optimize both the makespan and the tool utilization concurrently, improving production efficiency and maintaining competitiveness in the manufacturing industry. [ABSTRACT FROM AUTHOR]

Cloud technology has raised significant prominence providing a unique market economic approach for resolving large-scale challenges in heterogeneous distributed systems. Through the use of the network, it delivers secure, quick, and profitable information storage with computational capability. Cloud applications are available on-demand to meet a variety of user QoS standards. Due to a large number of users and tasks, it is important to achieve efficient scheduling of tasks submitted by users. One of the most important and difficult non-deterministic polynomial-hard challenges in cloud technology is task scheduling. Therefore, in this paper, an efficient task scheduling approach is developed. To achieve this objective, a hybrid genetic algorithm with particle swarm optimization (HGPSO) algorithm is presented. The scheduling is performed based on the multi-objective function; the function is designed based on three parameters such as makespan, cost, and resource utilization. The proper scheduling system should minimize the makespan and cost while maximizing resource utilization. The proposed algorithm is implemented using WorkflowSim and tested with arbitrary task graphs in a simulated setting. The results obtained reveal that the proposed HGPSO algorithm outperformed all available scheduling algorithms that are compared across a range of experimental setups. [ABSTRACT FROM AUTHOR]

The developments of multi-core systems (MCS) have considerably improved the existing technologies in the field of computer architecture. The MCS comprises several processors that are heterogeneous for resource capacities, working environments, topologies, and so on. The existing multi-core technology unlocks additional research opportunities for energy minimization by the use of effective task scheduling. At the same time, the task scheduling process is yet to be explored in the multi-core systems. This paper presents a new hybrid genetic algorithm (GA) with a krill herd (KH) based energy-efficient scheduling technique for multi-core systems (GAKH-SMCS). The goal of the GAKH-SMCS technique is to derive scheduling tasks in such a way to achieve faster completion time and minimum energy dissipation. The GAKH-SMCS model involves a multiobjective fitness function using four parameters such as makespan, processor utilization, speedup, and energy consumption to schedule tasks proficiently. The performance of the GAKH-SMCS model has been validated against two datasets namely random dataset and benchmark dataset. The experimental outcome ensured the effectiveness of the GAKH-SMCS model interms of makespan, processor utilization, speedup, and energy consumption. The overall simulation results depicted that the presented GAKH-SMCS model achieves energy efficiency by optimal task scheduling process in MCS. [ABSTRACT FROM AUTHOR]

Task scheduling in highly elastic and dynamic processing environments such as cloud computing have become the most discussed problem among researchers. Task scheduling algorithms are responsible for the allocation of the tasks among the computing resources for their execution, and an inefficient task scheduling algorithm results in under-or over-utilization of the resources, which in turn leads to degradation of the services. Therefore, in the proposed work, load balancing is considered as an important criterion for task scheduling in a cloud computing environment as it can help in reducing the overhead in the critical decision-oriented process. In this paper, we propose an adaptive genetic algorithm-based load balancing (GALB)- aware task scheduling technique that not only results in better utilization of resources but also helps in optimizing the values of key performance indicators such as makespan, performance improvement ratio, and degree of imbalance. The concept of adaptive crossover and mutation is used in this work which results in better adaptation for the fittest individual of the current generation and prevents them from the elimination. CloudSim simulator has been used to carry out the simulations and obtained results establish that the proposed GALB algorithm performs better for all the key indicators and outperforms its peers which are taken into the consideration. [ABSTRACT FROM AUTHOR]

Flexible Job Shop Scheduling is an important problem in the fields of combinatorial optimization and production management. This research addresses multi-objective flexible job shop scheduling problem with the objective of simultaneous minimization of: (1) makespan, (2) workload of the most loaded machine, and (3) total workload. A general-purpose, domain independent genetic algorithm implemented in a spreadsheet environment is proposed for the flexible job shop. Spreadsheet functions are used to develop the shop model. Performance of the proposed algorithm is compared with heuristic algorithms already reported in the literature. Simulation experiments demonstrated that the proposed methodology can achieve solutions that are comparable to previous approaches in terms of solution quality and computational time. Flexible job shop models presented herein are easily customizable to cater for different objective functions without changing the basic genetic algorithm routine or the spreadsheet model. Experimental analysis demonstrates the robustness, simplicity, and general-purpose nature of the proposed approach.

Copyright of China Mechanical Engineering is the property of Editorial Board of China Mechanical Engineering 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.)

This paper combines the tabu search process with a genetic algorithm by employing a new partial opposed-based as the population initialization technique to minimize makespan. Flow shop is a prominent variety in scheduling with various applications in numerous disciplines, including production. Its difficulty makes many researchers develop algorithms to solve it since it is categorized as an NP-hard problem. Some approaches have been developed to resolve production scheduling, especially evolutionary algorithms. The genetic algorithm becomes the most used algorithm in evolutionary to address production schedule because of its capability to produce good, fast, and efficient results to explore complex solution space (global search). However, it provides ineffective results when doing exploitation (local search) that is easily stuck in the optimum local area. Contrarily, tabu search has superiority in local search to help genetic algorithms not be trapped in a local optimum. By combining these two algorithms with the initialization scheme, a new algorithm that balances searches in resulting higher quality solutions is obtained. The proposed algorithm was tested using 120 problem instances to carry out the algorithm performance. The empirical results state that the developed algorithm can improve 115 solutions out of 120 instances than the six other hybrid algorithms. [ABSTRACT FROM AUTHOR]

This paper addresses the unrelated parallel machine scheduling problem with sequence and machine dependent setup times and machine eligibility constraints. The objective is to minimize the maximum completion time (makespan). Instances of more than 500 jobs and 50 machines are not uncommon in industry. Such large instances become increasingly challenging to provide high-quality solutions within limited amount of computational time, but so far, have not been adequately addressed in recent literature. A hybrid genetic algorithm is developed, which is lean in the sense that is equipped with a minimal number of parameters and operators, and which is enhanced with an effective local search operator, specifically targeted to solve large instances. For evaluation purposes a new set of larger problems is generated, consisting of up to 800 jobs and 60 machines. An extensive comparative study shows that the proposed method performs significantly better compared to other state-of-the-art algorithms, especially for the new larger instances. Also, it is demonstrated that calibration is crucial and in practice it should be targeted at a narrower set of representative instances. [ABSTRACT FROM AUTHOR]

This paper introduces the Twin Robot Palletising Problem (TRPP) in which two robots must be scheduled and routed to pick up and deliver products at specified locations along a rail. The robots are initially located at the opposite ends of the rail and must preserve a minimum safe distance from one another. The objective is to minimise the makespan, defined as the time required to complete all operations and for both robots to return to their starting positions. The paper presents a proof of NP-Hardness of the TRPP, as well as two mixed integer linear programming models. Local search operators are introduced, before an iterated local search and an iterated local search and a genetic algorithm are developed, in which a linear-time scheduling algorithm and dynamic programming are utilised to evaluate the quality of solutions. Extensive computational results demonstrate the limits of the mathematical models, the effectiveness of the metaheuristics, and the savings obtained using twin robots instead of a single one. [ABSTRACT FROM AUTHOR]

Manufacturing scheduling aims to optimize one or more performance measures by allocating a set of resources to a set of jobs or tasks over a given period of time. It is an area that considers a very important decision-making process for manufacturing and production systems. In this paper, the unrelated parallel machine scheduling problem with machine-dependent and job-sequence-dependent setup times is addressed. This problem involves the scheduling of tasks on unrelated machines with setup times in order to minimize the makespan. The genetic algorithm is used to solve small and large instances of this problem when processing and setup times are balanced (Balanced problems), when processing times are dominant (Dominant P problems), and when setup times are dominant (Dominant S problems). For small instances, most of the values achieved the optimal makespan value, and, when compared to the metaheuristic ant colony optimization (ACOII) algorithm referred to in the literature, it was found that there were no significant differences between the two methods. However, in terms of large instances, there were significant differences between the optimal makespan obtained by the two methods, revealing overall better performance by the genetic algorithm for Dominant S and Dominant P problems. [ABSTRACT FROM AUTHOR]

In this article, meta-heuristic algorithms are proposed for the production scheduling problem of a flow workshop, considered as a complete non-polynomial problem due to its complexity. The study of the problem is relevant given its usefulness in practice, for example, in factories with assembly lines or in collaborative supply chains planning. Thus, the objective of the present study consisted of evaluating two meta-heuristic algorithms, GRASP and a genetic algorithm. An experimental design was proposed to determine which factors (method, number of jobs and number of iterations) have a statistically significant effect on production scheduling completion time. According to the results, it could be observed that there is incidence of the first, second and third order of the factors, allowing to characterize the performance of the two algorithms in environments generated by the interaction of the three factors analyzed. [ABSTRACT FROM AUTHOR]

In our previous research applied to the job shop scheduling problem (JSSP) for machine tool production, the multi-objective optimisation model based on the particle swarm optimization (PSO) research had an imbalance performance between the convergence rate and the convergence precision. In this article, a new hybrid algorithm using PSO and generic algorithm (GA) is proposed to solve this particular problem. In this new algorithm, named hybrid PSO-GA algorithm (HPGA), the PSO algorithm is redefined and modified by introducing genetic operators, i.e. the crossover operator and the mutation operator, to update the particles in the population. The HPGA is then applied in heavy machinery company with minimising machines’ makespan and minimising jobs’ tardiness as the two optimal objectives. The comparisons with actual application report have illustrated that the proposed HPGA can obtain higher quality of schedule solution for machine tool production. Furthermore, with solution quality and convergence rate as the two estimation measurements metrics, some comparisons are performed in order to illustrate that the HPGA has superiority over the PSO, GA and simulated annealing algorithm (SA). Results have indicated that, with the combination of the merits of PSO and GA, the proposed HPGA approach can achieve not only better solution quality but also faster convergence rate than the PSO, GA and SA, within a reasonable computation time for high dimensions JSSP. [ABSTRACT FROM PUBLISHER]

This paper deals with the problem of scheduling the no-wait flow-shop system with sequence-dependent set-up times and server side-constraints. No-wait constraints state that there should be no waiting time between consecutive operations of jobs. In addition, sequence-dependent set-up times are considered for each operation. This means that the set-up time of an operation on its respective machine is dependent on the previous operation on the same machine. Moreover, the problem consists of server side-constraints i.e. not all machines have a dedicated server to prepare them for an operation. In other words, several machines share a common server. The considered performance measure is makespan. This problem is proved to be strongly NP-Hard. To deal with the problem, two genetic algorithms are developed. In order to evaluate the performance of the developed frameworks, a large number of benchmark problems are selected and solved with different server limitation scenarios. Computational results confirm that both of the proposed algorithms are efficient and competitive. The developed algorithms are able to improve many of the best-known solutions of the test problems from the literature. Moreover, the effect of the server side-constraints on the makespan of the test problems is explained using the computational results. [ABSTRACT FROM AUTHOR]

Summary: Cloud computing is the current computing standard, which provides information technology (IT) services over the Internet on demand. In the cloud environment, a task is mapped with an available resource to attain a good result. Task scheduling is the technique that is used to allocate tasks on virtual machines (VMs) of a server based on its capacity of workload. Tasks are scheduled to the server in such a way to minimize traffic and time delay. Particle swarm optimization (PSO) is the best existing algorithm used to schedule a task to an existing resource on the environment of the cloud. By PSO, the task is scheduled for an existing resource to reduce computational cost. In this paper, a hybrid swarm optimization (HSO) algorithm, which is the combination of PSO and salp swarm optimization (SSO), is proposed to resolve task scheduling issues in the cloud environment. The main goal of HSO is to schedule the task to the available resource in such a way to reduce the execution time and computation cost. Multilayer logistic regression (MLR) is an approach used to detect the overloaded VMs, so that a task can be scheduled to a VM according to its capacity of workload. The proposed HSO algorithm with MLR is simulated on the cloudsim toolkit, and the results reveal the efficiency of the proposed algorithm in terms of cost, execution time, and makespan. Compared to the existing algorithms such as the genetic algorithms (GAs), the improved efficiency evolution (IDEA), and the PSO, the proposed algorithm reveals superiority in terms of efficiency, resource utilization, and speed. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Guangdong University of Technology is the property of Journal of Guangdong University of Technology 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.)

Modern information technology, such as the internet of things (IoT) provides a real‐time experience into how a system is performing and has been used in diversified areas spanning from machines, supply chain, and logistics to smart cities. IoT captures the changes in surrounding environments based on collections of distributed sensors and then sends the data to a fog computing (FC) layer for analysis and subsequent response. The speed of decision in such a process relies on there being minimal delay, which requires efficient distribution of tasks among the fog nodes. Since the utility of FC relies on the efficiency of this task scheduling task, improvements are always being sought in the speed of response. Here, we suggest an improved elitism genetic algorithm (IEGA) for overcoming the task scheduling problem for FC to enhance the quality of services to users of IoT devices. The improvements offered by IEGA stem from two main phases: first, the mutation rate and crossover rate are manipulated to help the algorithms in exploring most of the combinations that may form the near‐optimal permutation; and a second phase mutates a number of solutions based on a certain probability to avoid becoming trapped in local minima and to find a better solution. IEGA is compared with five recent robust optimization algorithms in addition to EGA in terms of makespan, flow time, fitness function, carbon dioxide emission rate, and energy consumption. IEGA is shown to be superior to all other algorithms in all respects. [ABSTRACT FROM AUTHOR]

Combining Deep Reinforcement Learning and meta-heuristic techniques represents a new research direction for enhancing the search capabilities of meta-heuristic methods in the context of production scheduling. Q-learning is a prominent reinforcement learning in which its utilization aims to direct the selection of actions, thus preventing the necessity for a random exploration in the iterative process of the metaheuristics. In this study, we provide Q-learning guided algorithms for the Bi-Criteria No-Wait Flowshop Scheduling Problem (NWFSP). The problem is treated as a bi-criteria combinatorial optimization problem where total flow time and makespan are optimized simultaneously. Firstly, a deterministic mixed-integer linear programming (MILP) model is provided. Then, Q-learning guided algorithms are developed: Bi-Criteria Iterated Greedy Algorithm with Q-Learning (BC-IG QL). Bi-Criteria Block Insertion Heuristic Algorithm with Q-Learning (BC-BIH QL). Moreover, the performance of the proposed Q-learning guided algorithms is compared over a collection of Bi-Criteria Genetic Local Search Algorithms (BC-GLS), Bi-Criteria Iterated Greedy Algorithm (BC-IG), Bi-Criteria Iterated Greedy Algorithm with a Local Search (BC-IG ALL) and Bi-Criteria Variable Block Insertion Heuristic Algorithm (BC-VBIH). The complete computational experiment, performed on 480 problem instances of Vallada et al. (2015), which is known as the VRF benchmark set, indicates that the BC-BIH QL and the BC-IG QL algorithms outperform the BC-GLS, BC-IG, BC-IG ALL, and BC-VBIH algorithms in comparative performance metrics. More specifically, the proposed BC-BIH QL and BC-IG QL algorithms can yield more non-dominated bi-criteria solutions with the most substantial competitiveness than the remaining algorithms. At the same time, both are competitive with each other on the benchmark problems. Moreover, the BC-IG QL algorithm dominates almost 97% and 99% of the solutions reached by the BC-IG, BC-IG ALL , and BC-VBIH algorithms in small and large datasets. Similarly, The BC-BIH QL algorithm dominates almost 98% and 99% of the solutions reached by the BC-IG, BC-IG ALL , and BC-VBIH algorithms in small and large datasets, respectively. This means that, among all the features that have been compared, the Q-learning-guided algorithms demonstrate the highest level of competitiveness. The outcomes of this study encourage us to discover many more bi-criteria NWFSPs to reveal the trade-off between other conflicting objectives, such as makespan & the number of early jobs, to overcome various industries' problems. [ABSTRACT FROM AUTHOR]

Energy consumption in cloud data centers is increasing as the use of such services increases. It is necessary to propose new ways of reducing energy consumption. Task scheduling is an essential aspect of energy consumption in a cloud data center. The main objective of this research is to efficiently schedule various workflows so that energy consumption is minimized in the overall makespan and slice time of the processor. In this paper, the author makes a new approximation for the dynamic allocation of workflow tasks to currently available resources using genetic algorithm crossover, mutations, and evaluation operators. The purpose of this scheduling is to reduce the makespan and slack time on the processor and thus reduce the energy consumption of the processor in times that are not in use. [ABSTRACT FROM AUTHOR]

It has been well established that to find an optimal or near-optimal solution to job shop scheduling problems (JSSPs), which are NP-hard, one needs to harness different features of many techniques, such as genetic algorithms (GAs) and tabu search (TS). In this paper, we report usage of such a framework which exploits the diversified global search and the intensified local search capabilities of GA and TS, respectively. The system takes its input directly from the process information in contrast to having a problem-specific input format, making it versatile in dealing with different JSSP. This framework has been successfully implemented to solve industrial JSSPs. In this paper, we evaluate its suitability by applying it on a set of well-known job shop benchmark problems. The results have been variable. The system did find optimal solutions for moderately hard benchmark problems (40 out of 43 problems tested). This performance is similar to, and in some cases better than, comparable systems, which also establishes the versatility of the system. However for the harder benchmark problems it had difficulty in finding a new improved solution. We analyse the possible reasons for such a performance. [ABSTRACT FROM PUBLISHER]

This paper focuses on the distributed two-stage assembly flowshop scheduling problem for minimising a weighted sum of makespan and mean completion time. This problem involves two inter-dependent decision sub-problems: (1) how to allocate jobs among factories and (2) how to schedule the assigned jobs at each factory. A mathematical model is formulated for solving the small-sized instances of the problem. Since the NP-hardness of the problem, we also proposed a variable neighbourhood search (VNS) algorithm and a hybrid genetic algorithm combined with reduced variable neighbourhood search (GA-RVNS) to solve the distributed two-stage assembly flowshop scheduling problems and approximately optimise makespan and mean completion time simultaneously. Computational experiments have been conducted to compare the performances of the model and proposed algorithms. For a set of small-sized instances, both the model and the proposed algorithms are effective. The proposed algorithms are further evaluated on a set of large-sized instances. The results statistically show that both GA-RVNS and VNS obtain much better performances than the GA without RVNS-based local search step (GA-NOV). For the instances with small numbers of jobs, VNS achieves better performances than GA-RVNS. However, for the instances with large numbers of jobs, GA-RVNS yields better performances than the VNS. It is also shown that the overall performances of VNS are very close to GA-RVNS with different numbers of factories, weights given to makespan and numbers of machines at the first stage. [ABSTRACT FROM AUTHOR]

Under the computer-aided design (CAD) software architecture, this study aims to develop navigation processes for plastic injection mould manufacturing scheduling optimisation. Mould manufacturing is a job-shop scheduling problem, with components processing sequence under limited conditions. This study uses the search capabilities of the ant colony system (ACS) to determine a set of optimal schedules, under the condition of not violating the processing sequences, in order to minimise the total processing time and realise makespan minimisation. As the test results suggest, it can save up to 52% of manufacturing time, and also substantially shorten the processing time of the production plan. This study completes the algorithm steps and manufacturing process time estimation by operations on the navigation interface, and uses mould manufacturing scheduling to make optimised arrangements of finished components. The method can comply with the on-site manufacturing processes, improve scheduling prediction accuracy and consistently and efficiently integrate the optimisation scheduling system and mould manufacturing system. Visualised information of the scheduling results can be provided, thus allowing production management personnel to ensure smooth scheduling. [ABSTRACT FROM AUTHOR]

In production planning and scheduling, data mining methods can be applied to transform the scheduling data into useful knowledge that can be used to improve planning/scheduling by enabling real-time decision-making. In this paper, a novel approach combining dispatching rules, a genetic algorithm, data mining, and simulation is proposed. The genetic algorithm (i) is used to solve scheduling problems, and the obtained solutions (ii) are analyzed in order to extract knowledge, which is then used (iii) to automatically assign in real-time different dispatching rules to machines based on the jobs in their respective queues. The experiments are conducted on a job shop scheduling problem with a makespan criterion. The obtained results from the computational study show that the proposed approach is a viable and effective approach for solving the job shop scheduling problem in real time. [ABSTRACT FROM AUTHOR]

Shorter product life cycles, unpredictable demand patterns and the ever-shrinking time to market, have been constantly keeping the manufacturing firms under a lot of pressure. To face these challenges the manufacturing organizations have been shifting to Cellular Manufacturing (CM) due to its benefits of reducing manufacturing costs, increasing flexibility and delivering orders on time. Despite having several benefits, designing a Cellular Manufacturing System (CMS) for a real-life application is a tough ask. The main challenge is the part-machine grouping in cells. It becomes even more challenging when the group scheduling (GS) problem is handled alongside the part-machine clustering. To take up this challenge, an integrated model is developed during this research which handles the machine-part grouping and the GS problems, simultaneously. To optimize the multiple objectives of maximizing Grouping Efficacy (GE) and minimizing Makespan (Cmax), concurrently, a Hybrid Genetic Algorithm (HGA) based approach is developed. The proposed technique is validated through the famous benchmark problems, unlike the several approaches already available in literature. The computational results have shown that the integrated approach, presented in this paper, is more effective as compared to a sequential technique. Also, its accuracy remains intact even if it is applied to large sized problems. [ABSTRACT FROM AUTHOR]

The first objective of this study is to update a capacity constraint to the mixed integer programming model of the unrelated parallel machines scheduling problem. Then, a new proposed algorithm is developed based on the combination between the genetic algorithm with the so-called ISETP heuristics (Initial Sequence based on Earliness-Tardiness criterion on Parallel machine). The new Genetic Algorithm with Initial Sequence based on Earliness-Tardiness criterion on Parallel machine (GAISETP) generates job sequences and allocates them to the machines subject to capacity constraint. A case of automobile component manufacturing company is investigated to test the performance of the proposed method for both small-sized and large-sized problems. The obtained results are very promising both in terms of makespan and earliness-tardiness. [ABSTRACT FROM AUTHOR]

A multiobjective variable neighborhood descent (VND) based heuristic is developed to solve a bicriteria parallel machine scheduling problem. The problem considers two objectives, one related to the makespan and the other to the flow time, where the setup time depends on the sequence, and the machines are identical. The heuristic has a set of neighborhood structures based on swap, remove, and insertion moves. We propose changing the local search inside the VND to a sequential search through the neighborhoods to obtain nondominated points for the Pareto‐front quickly. In the numerical tests, we consider a single‐objective version of the heuristic, comparing the results on 510 benchmark instances to show that it is quite effective. Moreover, new instances are generated in accordance with the literature for the bicriteria problem, showing the ability of the proposed heuristic to return an efficient set of nondominate solutions compared with the well‐known nondominated sorting genetic algorithm II. [ABSTRACT FROM AUTHOR]

Researchers claim that the processing of most products can be formulated as a two-stage assembly scheduling model. The literature states that cumulative learning experience is neglected in solving two-stage assembly scheduling problems. The sum-of-processing-times-based learning effect means that the actual processing time of a job becomes shorter when it is scheduled later, which depends on the sum of processing time of the jobs already processed. Motivated by this observation, we investigate a novel two-stage assembly scheduling with three machines and sum-of-processing-times-based learning effect to minimize the makespan criterion, where two machines operate at the first stage and an assembly machine operates at the second stage. To solve this NP-hard problem, a branch-and-bound method incorporating with ten dominance properties and a lower bound procedure is first derived to obtain an optimal solution. Three heuristics based on Johnson's rule with and without improvement are then applied separately to a genetic algorithm and a cloud theory-based simulated annealing algorithm, which are further modified with an interchange pairwise method for finding near-optimal solutions. Finally, the numerical results obtained using all proposed algorithms are reported and evaluated. [ABSTRACT FROM AUTHOR]

The sustainability of manufacturing systems is not thoroughly investigated in the existing literature despite that fact that it affects service-oriented organisations. This paper addresses this gap by incorporating the criterion of energy consumption in mixed model assembly line sequencing (MMALS) to explore the potential for energy saving. Energy consumption was integrated with makespan and sequence dependent setup time of mixed models to achieve the sustainability in sequencing. A mathematical model was developed for the optimisation of energy efficient MMAL (EEMMAL). The multi-objective intelligent genetic algorithm (MOIGA) was proposed for minimisation of three conflicting objectives. A case study was conducted using centrifugal pump assembly line to test the performance of proposed MOIGA and the results were compared with those obtained from multi- objective genetic algorithm (MOGA). Finally, a trade-off analysis was conducted between total setup time, makespan (a service level measure on shop floor) and energy consumption (a factor of environmental sustainability). This analysis indicated the effectiveness of MOIGA (compared to MOGA) for EEMMALS problems. [ABSTRACT FROM AUTHOR]

This paper explores flexible job-shop scheduling problem (FJSP), using the rolling window rescheduling strategy. The fuzzy delivery time was considered, which satisfies the trapezoidal delivery window of the fuzzy membership function and directly bears on consumer satisfaction. Taking machine failure as the cause of dynamic interferences, the author established a dynamic scheduling model for the FJSP with fuzzy delivery time, according to the fuzzy mathematics theory. The model has multiple objectives: minimizing energy consumption, maximum makespan and consumer dissatisfaction. Next, the immune genetic algorithm (IGA) was improved to solve the model. The established model and the improved IGA were verified through simulations, in comparison with the genetic algorithm (GA). The research results shed new light on the FJSPs in real-world scenarios. [ABSTRACT FROM AUTHOR]

The objective of this paper is to find a sequence of jobs for the permutation flow shop to minimise the makespan. The shop consists of 10 machines. A feed-forward back-propagation artificial neural network (ANN) is used to solve the problem. The network is trained with the optimal sequences for five-, six- and seven-job problems. This trained network is then used to solve a problem with a greater number of jobs. The sequence obtained using the neural network is used to generate the initial population for the genetic algorithm (GA) using the random insertion perturbation scheme (RIPS). The makespan of the sequence obtained by this approach (ANN-GA-RIPS) is compared with that obtained using GA starting with a random population (ANN-GA). It was found that the ANN-GA-RIPS approach performs better than ANN-GA starting with a random population. The results obtained are compared with those obtained using the Nawaz, Enscore and Ham (NEH) heuristic and upper bounds of Taillard's benchmark problems. ANN-GA-RIPS performs better than the NEH heuristic and the results are found to be within 5% of the upper bounds. [ABSTRACT FROM AUTHOR]

In this work we study a flow shop scheduling problem in which jobs are not allowed to wait between machines, a situation commonly referred to as no-wait. The criterion is to minimise a weighted sum of makespan and maximum lateness. A dominance relation for the case of three machines is presented and evaluated using experimental designs. Several heuristics and local search methods are proposed for the general m-machine case. The local search methods are based on genetic algorithms and iterated greedy procedures. An extensive computational analysis is conducted where it is shown that the proposed methods outperform existing heuristics and metaheuristics in all tested scenarios by a considerable margin and under identical CPU times. [ABSTRACT FROM AUTHOR]

This paper considers the permutation flowshop scheduling problem with the objective of minimizing makespan. Genetic algorithm (GA) is one of the search heuristics used to solve global optimization problems in complex search spaces. It is observed that, the efficiency of GA in solving a flowshop problem can be improved significantly by tailoring the various GA operators to suit the structure of the problem. In this paper, an effective Improved Genetic Algorithm (IGA) for flowshop scheduling, incorporating multi-crossover operators, multi-mutation operators and hypermutation is proposed. Computation results based on some permutation flowshop scheduling benchmark problems (OR-Library) show that the IGA gives a better solution when compared with the earlier reported results. [ABSTRACT FROM AUTHOR]

The flexible job scheduling problem with automated guided vehicles (FJSP-AGVs) is a simplified model of some real manufacturing industries. It contains three strongly coupled subproblems: operation sequences assignment, machine selection, and automatic guided vehicle selection, leading to a huge solution space. Its several unresolved challenges, i.e., problem model and algorithmic designing, persist. Therefore, we first adopt the sequence-based modeling method to establish a mixed-integer linear programming model with makespan, and its correctness is verified by using the Gurobi solver. Subsequently, a multi-strategy-driven genetic algorithm (M u l t _ s t r a _ G A) is proposed based on the implicit features of FJSP-AGVs. In M u l t _ s t r a _ G A , for the operation sequence (OS) and the machine assignment (MS) subproblems, we design three targeted strategies, i.e., two layer-based encoding and decoding strategy, a multiple heuristics-based initialization strategy, double crossover, and dual mutation operators. Meanwhile, the problem-specific diversity checking and restart strategies are introduced to avoid M u l t _ s t r a _ G A falling into local optima. Finally, we conduct experiments on four well-known benchmarks. Through the statistical analysis, the outcomes demonstrate that the M u l t _ s t r a _ G A algorithm exhibits efficacy when contrasted with other advanced algorithms. [ABSTRACT FROM AUTHOR]

The paper addresses minimizing makespan by a genetic algorithm (GA) for scheduling jobs with non-identical sizes on a single-batch-processing machine. A batch-processing machine can process up to B jobs simultaneously. The processing time of a batch is equal to the longest processing time among all jobs in the batch. Two different GAs are proposed based on different encoding schemes. The first is a sequence-based GA (SGA) that generates random sequences of jobs using GA operators and applies the batch first fit heuristic to group the jobs. The second is a batch-based hybrid GA (BHGA) that generates random batches of jobs using GA operators and ensures feasibility by using knowledge of the problem based on a heuristic procedure. A greedy local search heuristic based on the problem characteristics is hybridized with a BHGA that has the ability of steering efficiently the search toward the optimal or near-optimal schedules. The performance of proposed GAs is compared with a simulated annealing (SA) approach proposed by Melouk et al. (Melouk, S., Damodaran, P. and Chang, P.Y., Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing. Int. J. Prod. Econ., 2004, 87, 141-147) and also against a modified lower bound proposed for the problem. Computational results show that BHGA performs considerably well compared with the modified lower bound and significantly outperforms the SGA and SA in terms of both quality of solutions and required runtimes. [ABSTRACT FROM AUTHOR]