In this paper, we propose a competitive Constraint Programming (CP) approach to solve the Group Shop Scheduling Problem (GSSP) under the makespan minimization criteria. Our contribution is two-fold: ...we provide a flexible mathematical formulation to solve the GSSP that can be used without change to solve other closed-related scheduling problems such as the Open Shop Scheduling Problem (OSSP), Job Shop Scheduling Problem (JSSP), and Mixed Shop Scheduling Problem (MSSP); and we improve several lower bounds and upper bounds from 130 classical GSSP instances from the literature. We evaluate our approach by comparing the performance with competitive methods mainly based on metaheuristics, where we were able to prove optimality in more than 85% of the instances in competitive running time, with a relative percentage deviation lower than 3% on average. In contrast to metaheuristics approaches, our CP method does not require calibrations of multiple parameters, several replicates for each instance, and complex computational coding to be competitive in both, solution quality and computational running times.
•Energy-efficient job-shop scheduling with deteriorating machines is studied.•Green production and tardiness related objectives are considered.•A multi-population, multi-objective memetic algorithm ...is proposed for the problem.•The proposed algorithm exhibits superior performance across a range of metrics.
This paper focuses on an energy-efficient job-shop scheduling problem within a machine speed scaling framework, where productivity is affected by deterioration. To alleviate the deterioration effect, necessary maintenance activities must be put in place during the scheduling process. In addition to sequencing operations on machines, the problem at hand aims to determine the appropriate speeds of machines and positions of maintenance activities for the schedule, in order to minimise the total weighted tardiness and total energy consumption simultaneously. To deal with this problem, a multi-population, multi-objective memetic algorithm is proposed, in which the solutions are distributed into sub-populations. Besides a general local search, an advanced objective-oriented local search is also executed periodically on a portion of the population. These local search methods are designed based on a new disjunctive graph introduced to cover the solution space. Furthermore, an efficient non-dominated sorting method for bi-objective optimisation is developed. The performance of the memetic algorithm is evaluated via a series of comprehensive computational experiments, comparing it with state-of-the-art algorithms presented for job-shop scheduling problems with/without considering energy efficiency. Experimental results confirm that the proposed algorithm can outperform other algorithms being compared across a range of performance metrics.
This edited book presents new results in the area of the development of exact and heuristic scheduling algorithms. It contains eight articles accepted for publication for a Special Issue in the ...journal Algorithms. The book presents new algorithms, e.g., for flow shop, job shop, and parallel machine scheduling problems. The particular articles address subjects such as a heuristic for the routing and scheduling problem with time windows, applied to the automotive industry in Mexico, a heuristic for the blocking job shop problem with tardiness minimization based on new neighborhood structures, fast heuristics for the Euclidean traveling salesman problem or a new mathematical model for the period-aggregated resource leveling problem with variable job duration, and several others.
Flexible job shop scheduling has been widely researched due to its application in many types of fields. However, constraints including setup time and transportation time should be considered ...simultaneously among the realistic requirements. Moreover, the energy consumptions during the machine processing and staying at the idle time should also be taken into account for green production. To address this issue, first, we modeled the problem by utilizing an integer programming method, wherein the energy consumption and makespan objectives are optimized simultaneously. Afterward, an improved Jaya (IJaya) algorithm was proposed to solve the problem. In the proposed algorithm, each solution is represented by a two-dimensional vector. Consequently, several problem-specific local search operators are developed to perform exploitation tasks. To enhance the exploration ability, a SA-based heuristic is embedded in the algorithm. Meanwhile, to verify the performance of the proposed IJaya algorithm, 30 instances with different scales were generated and used for simulation tests. Six efficient algorithms were selected for detailed comparisons. The simulation results confirmed that the proposed algorithm can solve the considered problem with high efficiency.
•The FJSPs with transportation and setup time are considered.•Two objectives are optimized simultaneously.•Seven different types of local search approaches are proposed.•SA-based acceptation criterion is embedded.
This paper studies the flexible assembly job-shop scheduling problem in a dynamic manufacturing environment, which is an exension of job-shop scheduling with incorporation of serveral types of ...flexibilies and integration of an assembly stage. Each product is assembled from several parts with nonlinear process plans with operations involving alternative machines. Setup times are sequence dependent and serparately considered from processing times. Part sharing is fully allowed such that they can be used for the assembly of any possible product, rather than being preassociated to a specfic product. We employ constraint programming and mixed-integer linear programming to formulate the problem. Besides, several dispatching rules with machine feedback machanism are developped. Experimental studies are conducted based on test case problems with different scales and complexities. It is found that constraint programming is the most efficacious approach, whose solution fitness outperforms mixed-integer linear programming as well as all dispatching rules in both static and dynamic cases. On the other hand, dispatching rules are simple to implement, among which the "earliest completion time" rule is the most favourable. A real-time scheduling/rescheduling system has been constructed for the implementation of the proposed approaches to solve practical problems in production.
Flexible job shop scheduling problems (FJSPs) have attracted significant research interest because they can considerably increase production efficiency in terms of energy, cost and time; they are ...considered the main part of the manufacturing systems which frequently need to be resolved to manage the variations in production requirements. In this study, novel reinforcement learning (RL) models, including advanced Q-learning (QRL) and RL-based state–action–reward–state–action (SARSA) models, are proposed to enhance the scheduling performance of FJSPs, in order to reduce the total makespan. To more accurately depict the problem realities, two categories of simulated single-machine job shops and multi-machine job shops, as well as the scheduling of a furnace model, are used to compare the learning impact and performance of the novel RL models to other algorithms. FJSPs are challenging to resolve and are considered non-deterministic polynomial-time hardness (NP-hard) problems. Numerous algorithms have been used previously to solve FJSPs. However, because their key parameters cannot be effectively changed dynamically throughout the computation process, the effectiveness and quality of the solutions fail to meet production standards. Consequently, in this research, developed RL models are presented. The efficacy and benefits of the suggested SARSA method for solving FJSPs are shown by extensive computer testing and comparisons. As a result, this can be a competitive algorithm for FJSPs.
Given the dynamic and uncertain production environment of job shops, a scheduling strategy with adaptive features must be developed to fit variational production factors. Therefore, a dynamic ...scheduling system model based on multi-agent technology, including machine, buffer, state, and job agents, was built. A weighted Q-learning algorithm based on clustering and dynamic search was used to determine the most suitable operation and to optimize production. To address the large state space problem caused by changes in the system state, four state features were extracted. The dimension of the system state was decreased through the clustering method. To reduce the error between the actual system states and clustering ones, the state difference degree was defined and integrated with the iteration formula of the Q function. To select the optimal state-action pair, improved search and iteration update strategies were proposed. Convergence analysis of the proposed algorithm and simulation experiments indicated that the proposed adaptive strategy is well adaptable and effective in different scheduling environments, and shows better performance in complex environments. The two contributions of this research are as follows: (1) a dynamic greedy search strategy was developed to avoid blind searching in traditional strategy. (2) Weighted iteration update of the Q function, including the weighted mean of the maximum fuzzy earning, was designed to improve the speed and accuracy of the improved learning algorithm.
As economic globalization, large manufacturing enterprises build production centers in different places to maximize profit. Therefore, scheduling problems among multiple production centers should be ...considered. This paper studies a distributed hybrid flow shop scheduling problem (DHFSP) with makespan criterion, which combines the characteristic of distributed flow shop scheduling and parallel machine scheduling. In the DHFSP, a set of jobs are assigned into a set of identical factories to process. Each job needs to be through same route with a set of stages, and each stage has several machines in parallel and at least one of stage has more than one machine. For solving the DHFSP, this paper proposes two algorithms: DNEH with smallest-medium rule and multi-neighborhood iterated greedy algorithm. The DNEH with smallest-medium rule constructive heuristic first generates a seed sequence by decomposition and smallest-medium rule, and then uses a greedy iteration to assign jobs to factories. In the iterated greedy algorithm, a multi-search construction is proposed, which applies the greedy insertion to the factory again after inserting a new job. Then, a multi-neighborhood local search is utilized to enhance local search ability. The proposed algorithms are evaluated by a comprehensive comparison, and the experimental results demonstrate that the proposed algorithms are very competitive for solving the DHFSP.
•A distributed hybrid flow shop scheduling with makespan criterion is studied.•A DNEH_SMR based on decomposition and small–medium rule is proposed.•An IG with multi-search construction and local search is proposed.•The DNEH_SMR and IG are competitive algorithms for solving the DHFSP.
•An integrated optimization problem of flexible job shop scheduling and preventive maintenance is investigated.•A flexible maintenance strategy that integrates time-based maintenance and ...condition-based maintenance is proposed.•Both the machine resource and the worker resource are under consideration.•Four dynamic disturbances are considered, and respective rescheduling processes are illustrated.•A double-layer Q-learning algorithm is integrated with the digital twin for effective dynamic scheduling.
Dynamic scheduling methods are essential and critical to manufacturing systems because of uncertain events in the production process, such as new job insertions, order cancellations, worker absences, and machine breakdowns. Emerging digital twin (DT) technology can help detect disturbances by continuously comparing physical space with virtual space and triggering a rescheduling policy immediately after a disturbance. This enables dynamic scheduling and greatly reduces the deviation between preschedules and actual schedules. This study focuses on a DT-enabled integrated optimisation problem of flexible job shop scheduling and flexible preventive maintenance (PM) considering both machine and worker resources. A double-layer Q-learning algorithm (DLQL) is designed as the underlying key optimisation method to simultaneously learn the selection process of machines and operations to achieve efficient real-time scheduling. The superior solution performance of DLQL was verified by comparing it with two well-known metaheuristic algorithms and a single-layer Q-learning algorithm under several benchmarks. Furthermore, different disturbance settings were designed to illustrate the DLQL-based dynamic scheduling process in detail. The proposed reinforcement learning (RL)-driven DT enables efficient collaborative scheduling between production and maintenance departments and helps manufacturing companies improve the real-time decision-making process under uncertain perturbations.
This paper studies a simultaneous scheduling of production and material transfer in a job shop environment. The simultaneous scheduling approach has been recently adopted by warehouse operations, ...wherein transbots pick up jobs and deliver to pick-machines for processing that requires a simultaneous scheduling of jobs, transbots, and machines. However, both a large proportion of literature and real-world scheduling systems consider only one side of the problem. In our study, machines and transbot are both considered as constraining resources. The contributions of this paper are twofold. First, we propose a novel application of constraint programming for the job shop scheduling problem (JSP) with transbots, significantly outperforming all other benchmark approaches in the literature and proving optimality of the well-known benchmark instances, for the first time. Second, we propose a medium-scale benchmark instance.
