Search

Appointment scheduling is critical for logistic parks of manufacturing industry firms to manage inventory turnover and schedule service objects. This work studies the appointment scheduling problem of a logistic park considering truck heterogeneity and order fulfillment delay, where the number of time windows in a day, the number of each type of appointment slot, and the service schedule in each time window are decided. The objective is to minimise the expected total cost of the truck waiting time, inventory, and overtime. We introduce a weighted shortest processing time first scheduling rule to determine the service sequence in each time window and prove that it generates optimal scheduling solutions. Based on our proposed scheduling rule, we develop a recursive calculation to formulate the cost function, which provides a tractable approach to solving combinatorially complex problems. The proposed model is solved by a dual-selection based genetic algorithm (DSGA). The performance of the DSGA is validated by comparing it to a genetic algorithm using a single tournament selection operation. Our experimental results show that the DSGA enlarges the size of subgroups with better fitness and therefore performs satisfactorily. [ABSTRACT FROM AUTHOR]

Over the last decades, scheduling theory has been put into practice so as to tackle production process as a combinatorial optimisation problem and specifically as a PFSP (Permutation Flowshop Scheduling Problem). Often, NP-completeness of PFSP leads numerous research towards suggesting heuristic algorithms. The objective is to propose an optimal or near-to-optimal order of n jobs processing on m machines with a minimum completion time of all jobs. In this paper, a two-phase heuristic algorithm will be presented, named IFRS (Improved FRS). FRS, within the first phase, is going to be used to find a superior order of jobs out of Taillard's instances; then the order of jobs will be improved again in phase 2. While running IFRS, a completely new idea, named Pixelation of time matrices, will be used for the very first time and provide a final pattern, which can be used in any heuristic algorithm with makespan criterion. After using the hard benchmark instances of Taillard, the superiority of IFRS over 20 algorithms is going to be shown by tables and statistical graphics. Due to its low makespan values, IFRS benefits flow production, as does NEH. [ABSTRACT FROM AUTHOR]

Shop scheduling is deeply involved in manufacturing. In order to improve the efficiency of scheduling and fit dynamic scenarios, many Deep Reinforcement Learning (DRL) methods are studied to solve scheduling problems like job shop and flow shop. But most studies focus on using the latest algorithms while ignoring that the environment plays an important role in agent learning. In this paper, we design an effective, robust and size-agnostic environment for job shop scheduling. The proposed design of environment uses centralised training and decentralised execution (CTDE) to implement a multi-agent architecture. Together with the observation space we design, environmental information that is irrelevant to the current decision is eliminated as much as possible. The proposed action space enlarges the decision space of agents, which performs better than the traditional way. Finally, Soft Actor-Critic (SAC) algorithm is adapted to learning within this environment. By comparing with traditional scheduling rules, other reinforcement learning algorithms, and relevant literature, the superiority of the results obtained in this study is demonstrated. [ABSTRACT FROM AUTHOR]

The cloud-edge collaborative manufacturing system (CCMS) connects distributed factories to a cloud centre through cloud-edge collaborative communication, introducing both opportunities and challenges to conventional dynamic job scheduling. Enhancing each factory's scheduling performance by sharing general scheduling knowledge among heterogeneous factories under the consideration of data privacy protection remains challenging. To this end, this paper proposes to solve the dynamic job scheduling in the context of CCMS with a novel federated deep reinforcement learning (FDRL) approach. Within each factory, the scheduling objective involves minimising the makespan and energy consumption, accounting for machine warm-up procedures and real-time dynamics. To handle heterogeneous policy structures, we aggregate their hidden parameters through FDRL, with states, actions, and rewards designed to facilitate the aggregation. The two-phase algorithm, comprising iterative local training and global aggregation, trains the scheduling policies. Constraint items are introduced to the loss functions to smooth local training, and the global aggregation considers production scales and obtained objectives. The proposed approach enhances the solution quality and generalisation of each factory's scheduling policy without exposing original production data. Numerical experiments conducted on sixty scheduling instances validate the superiority of the proposed approach compared to twelve dynamic scheduling methods. Compared to independently trained DRL-based approaches, the proposed FDRL-based approach achieves up to an 8.9% reduction in makespan and a 22.3% decrease in energy consumption through knowledge sharing. [ABSTRACT FROM AUTHOR]

This paper addresses a real life scheduling problem characterised by multi-resource operations whose completion simultaneously requires more than one (renewable) resource of different types. Such problems arise in various companies not only in manufacturing but also in services. Solving such a problem needs to address two interconnected subproblems: a sequencing subproblem and a resource-allocation subproblem if more than one resource is available in some types. The resource-allocation subproblem consists of allocating to each operation the resources it requires while the sequencing subproblem consists of determining the order in which each resource performs the operations assigned to it. This paper focuses on the resource-allocation subproblem. It generalises the basic scheduling problems which consist of determining the operations' starting or completion times for a given processing sequence for every resource. We consider a cost function taking into account the makespan, the cost of resource utilisation, and the load imbalance among the resources of the same type. We first formulate the problem into a mixed-integer linear program (MILP). To efficiently solve it, even in practical-sized instances, an exact algorithm called BD (Benders decomposition with enhancing cuts) is developed where the master problem only considers integer variables. We prove that the slave problem can be transformed into finding the longest paths in a digraph and therefore can be solved with the Bellman–Ford algorithm. To enhance the efficiency of the method, equivalent solutions are limited in the master problem. The performance of the approach is evaluated by comparing it against CPLEX, a state-of-the-art commonplace MILP solver, used to directly solve the initial MILP. The computational results demonstrate that BD provides competitive solutions in all upper and lower bounds. In particular, it improves, compared with CPLEX, the upper and lower bounds by 5.07% and 4.63%, respectively, in solving practical-sized instances. The experiment also shows that considering load balancing can make more rational use of resources and avoid adverse effects caused by excessive workload of staff and imbalanced use of equipment, which is very important in real-world production. [ABSTRACT FROM AUTHOR]

In response to the challenges posed by economic globalisation and increasing customer demands, enterprises are compelled to adapt and refine their production models and operational objectives, which motivates this paper to address the integrated production scheduling and vehicle routing problem in the distributed manufacturing environment (IPSVRP-DME). The objective is to simultaneously minimise both total energy consumption and total earliness/tardiness. Initially, a mixed integer programming model is proposed to address small-scale problems using Gurobi. Considering the NP-hardness of the problem, a novel Self-adapted Gaussian Mutation-based Arithmetic Optimiser Algorithm (SGMAOA) is developed to handle medium-scale and large-scale instances. To address the complexity of decision-making, an innovative two-level encoding method that encompasses four decision dimensions is introduced. Additionally, an incremental repair strategy is devised to rectify infeasible solutions caused by unreasonable delivery batching, while a time relaxation strategy is proposed to further enhance service levels without compromising energy consumption. Comparative experiments are conducted to demonstrate the effectiveness of SGMAOA, which is benchmarked against five prominent metaheuristics. In addition, a specific example is applied for the discussion of managerial applications and to illustrate the practicality of the proposed model and solution method. [ABSTRACT FROM AUTHOR]

Rescheduling in a hybrid flowshop holds significant importance in modern industries that face uncertain events. Moreover, real-world manufacturing scenarios often utilise lot streaming to enhance market competitiveness. In light of escalating energy demands and their consequential environmental impacts, contemporary manufacturing companies are placing a heightened emphasis on energy efficiency. This study addressed a green hybrid flowshop rescheduling problem with consistent sublots (GHFRP_CS) in the context of urgent lot insertion. Initially, we establish an optimisation model aimed at minimising the makespan, total energy consumption, and system stability. To tackle this NP-hard multi-objective optimization problem, we develop a constructive heuristic generating promising solutions based on lot split, sequence, and local search rules. Further improvement is achieved through a multi-objective discrete artificial bee colony algorithm (MDABC). MDABC decomposes the problem into sub-problems, initiating solutions with the constructive heuristic and refining them through employed bee, onlooker bee, and scout bee phases. Computational experiments compare MDABC with other multi-objective evolutionary algorithms (MOEAs) on small- and large-scale problems. Results demonstrate MDABC's superiority, achieving fourfold accuracy and efficiency enhancement for small-scale instances and sixfold improvement for large-scale problems at low cost compared to other MOEAs. [ABSTRACT FROM AUTHOR]

One of the main challenges in operating multistate manufacturing systems (MMSs) is maintaining stable and robust production against various disruptions. Therefore, an urgent need exists for an operation and maintenance (O&M) method that optimises MMS resilience, i.e. the capability of withstanding or recover from disruptions of various sources. Consequently, this study proposes an integrated resilience-oriented production and maintenance scheduling approach for MMSs. This approach enhances MMS resilience by reinforcing its adaptivity to the variation in production requirements. Based on a conceptual investigation of operational uncertainty and its mechanism of disruption, this study devotes to (i) formulating a performance loss-based resilience measurement with consideration of operational uncertainties and (ii) proposing a reinforcement learning-based approach to schedule MMS operation and maintenance activities for MMS components of different performance states. An industrial case study of a ferrite phase shifter manufacturing system is subsequently conducted to validate the proposed approach. Results demonstrate the effectiveness of the proposed approach in the resilience optimisation of MMSs. [ABSTRACT FROM AUTHOR]

With the escalating integration of renewable energy sources (RESs) within the manufacturing sector, the synergy between energy and production management has gained paramount importance. To harmonise energy efficiency with production effectiveness, the concept of energy-aware scheduling, comprising off-line, on-line, and hybrid scheduling, has been introduced. While each approach has merits and drawbacks in handling unexpected disturbances, recovering optimal performance, and managing computational costs, their designs often tend to be ad hoc. Currently, there is a lack of a systematic design that effectively balances computational costs, robustness to unexpected disturbances, and optimal performance. Moreover, existing results do not fully leverage the flexibility in factories integrated with Renewable Energy Sources (RESs). In response, this study introduces the paradigm of event-triggered hybrid scheduling (ETHS) to achieve a balance among optimality, robustness, and computational cost by fully exploring the system's flexibility. The efficacy of ETHS is empirically demonstrated through a comprehensive case study involving a real-world manufacturing facility. Diverse scenarios are scrutinised, accompanied by sensitivity analyses pertaining to parameter choices. The outcomes conspicuously underscore the potency of ETHS in facilitating the harmonious alignment of energy and production management within the ambit of manufacturing industries. [ABSTRACT FROM AUTHOR]

Due to the severity of resource consumption and uncertainty in orders, new challenges have arisen for production scheduling in enterprises. This paper studies the scheduling problem of minimising the total weighted tardiness for jobs with fuzzy processing times and due dates on identical parallel machines with resource constraint. To address this research problem, we first propose methods to calculate the upper bound of resource consumption and the maximum number of machines that can be used, effectively reducing the search space and improving the algorithm's efficiency. Secondly, a local search algorithm based on job swapping is proposed to enhance the algorithm's performance. Then, repair algorithms based on job removal and job swapping are designed to repair infeasible solutions. Finally, we propose a fuzzy genetic algorithm (FGALS) to solve the problem based on the above elements. Through extensive simulation experiments, the effectiveness and efficiency of the FGALS algorithm are verified by comparing it with commercial solver Gurobi and several meta-heuristic algorithms. [ABSTRACT FROM AUTHOR]

Service-oriented manufacturing (SOM) is a new industrial model that combines manufacturing with service. To enhance the competitiveness of manufacturers in SOM systems, we investigate a coordinated production and delivery scheduling problem considering a third-party logistics (3PL) provider. The considered problem can be divided into two phases, including production phase and delivery phase. In the production phase, jobs are processed by multiple manufacturers located in different geographical zones. Jobs are with deteriorating processing time and set-up time. Several structural properties of the problem in the production phase are proposed, based on which a heuristic algorithm is designed to make decisions on job batching and batch sequencing. After being processed, the finished jobs are immediately delivered to a customer by manufacturers' own vehicles or the 3PL provider. A dynamic programming algorithm is developed to solve the problem in the delivery phase. The integrated scheduling problem is proved to be NP-hard. Hence, we develop a general variable neighbourhood search (GVNS) to solve the problem in a reasonable time. The basic variable neighbourhood descent (BVND) is used as a local search method in the GVNS. Finally, the computational experiments are conducted and the results verify the effectiveness and stability of the proposed approach. [ABSTRACT FROM AUTHOR]

We study scheduling problems on parallel dedicated machines. Thus, each job can be processed on one specific machine only. The option of job-rejection is considered, and the total permitted rejection cost of all the jobs is bounded. Six scheduling problems are solved: ( $ i $ i) minimising makespan, ( $ ii $ ii) minimising makespan with release-dates, ( $ iii $ iii) minimising total completion time, ( $ iv $ iv) minimising total weighted completion time, ( $ v $ v) minimising total load, and ( $ vi $ vi) minimising maximum tardiness. Pseudo-polynomial dynamic programming algorithms are introduced for all these NP-hard problems. [ABSTRACT FROM AUTHOR]

With increasing environmental concerns and energy crisis, a variety of renewable energy sources (RES) are being increasingly utilised worldwide. However, the integration of RES such as wind power and photovoltaics in large-scale can lead to increased load fluctuations, which can undermine the overall environmental benefits and pose risks to the secure and stable operation of the power system. To mitigate this challenge, a two-stage electricity production scheduling is developed incorporating energy storage system (ESS) and dynamic emission modelling (DEM). In the first stage, a multi-objective mixed integer programming model schedules the production of RES, increasing penetration rate and system stability. In the second stage, a data-driven dynamic emission model is developed to optimise the load allocation of thermal power unit to reduce the carbon emissions. Furthermore, a flexible operating reserve strategy is proposed to handle the uncertainty resulting from the intermittent character of RES. Experimental results demonstrate that the proposed method effectively schedules the production of RES thereby alleviating the contradiction between high RES utilisation and stable system operation. Compared to the benchmark model, the proposed method can reduce the carbon emissions and total cost of the system by 20.34% and 10.65%, respectively. [ABSTRACT FROM AUTHOR]

This paper presents an adaptive memetic algorithm based on a new neighbourhood structure (AMA) for solving the assembly job shop scheduling problem, with the aim of minimising the maximum completion time (makespan). To utilise the knowledge of problem, a theoretical analysis is conducted to explore the criteria for feasible and effective movement of operations under assembly constraints, and a multi-operation precise joint movement neighbourhood structure is proposed accordingly. In the AMA, to ensure the feasibility of solutions during the evolution process, a feasible encoding mechanism based on the constraint degree of operations is designed, a greedy active decoding method as well as feasible crossover operation based on independent operation chains are designed specifically for this encoding method. To avoid premature convergence of the population, a population update operator with diversity adaptive control is proposed. Finally, by comparing the results with five state-of-the-art algorithms, the superiority of AMA in terms of solution quality and stability is verified, particularly with the update of known optimal solutions for 11 instances. [ABSTRACT FROM AUTHOR]

Lot-sizing and scheduling in a job shop environment is a fundamental problem that appears in many industrial settings. The problem is very complex, and solutions are often needed fast. Although many solution methods have been proposed, with increasingly better results, their computational times are not suitable for decision-makers who want solutions instantly. Therefore, we propose a novel greedy heuristic to efficiently generate production plans and schedules of good quality. The main innovation of our approach represents the incorporation of a simulation-based technique, which directly generates schedules while simultaneously determining lot sizes. By utilising priority rules, this unique feature enables us to address the complexity of job shop scheduling environments and ensures the feasibility of the resulting schedules. Using a selection of well-known rules from the literature, experiments on a variety of shop configurations and complexities showed that the proposed heuristic is able to obtain solutions with an average gap to Cplex of 4.12%. To further improve the proposed heuristic, a cooperative coevolutionary genetic programming-based hyper-heuristic has been developed. The average gap to Cplex was reduced up to 1.92%. These solutions are generated in a small fraction of a second, regardless of the size of the instance. [ABSTRACT FROM AUTHOR]

In modern manufacturing and service industries, urgent orders and service tasks are common, and the speed of handling such urgent tasks is an important indicator of production and service efficiency. In this study, we consider scheduling jobs on two parallel machines with the random arrival of an emergency job. The objective is to minimise the makespan, subject to a given maximum waiting time of the emergency job. We first show that the worst-case ratio of the existing algorithm LPT $ _l $ l -SPT $ _{m-l} $ m − l is at least 3/2 when m = 2. We then analyse some properties of the optimal schedule and derive lower bounds on the optimal makespan. Finally, we present an improved approximation algorithm with a tight worst-case ratio of 4/3. We also provide numerical results showing that our proposed algorithm outperforms algorithm LPT $ _l $ l -SPT $ _{m-l} $ m − l . [ABSTRACT FROM AUTHOR]

This paper presents a novel solution approach for a variant of the job shop scheduling problem with machine unavailability due to both condition-based preventive maintenance and corrective maintenance following random breakdowns. We first provide an exact mathematical formulation of the problem under simplifying assumptions, namely that the number of breakdowns for each job position on each machine is known, the degradation rates are fixed, and the preventive and corrective maintenance durations are deterministic parameters. Moreover, to handle the more realistic case of stochastic machine degradation, random breakdowns, and uncertain maintenance durations, a simulation-optimisation algorithm is proposed. The real makespan function is first approximated using multiple surrogate measures, which are optimised through independent genetic algorithms. Then, the fittest solutions obtained from these surrogate measures are simulated, and the best among them is added to an elite list, which is included in the genetic algorithms' populations for the next iteration. Schedule robustness is ensured by using an objective function that consists of the weighted average of the expected makespan and its 90th percentile. Furthermore, to reduce the likelihood of falling into a local optimum, a stopping criterion based on simulated annealing is implemented. Numerical experimentation on extended benchmark instances confirmed the validity of the mathematical formulation and the favourable performance of the proposed simulation-optimisation algorithm in terms of computational time and solution quality. [ABSTRACT FROM AUTHOR]

This study uses an agent-based approach with a combinatorial auction mechanism to solve the joint order acceptance and assembly job shop scheduling problem. A set of jobs is offered. Each job has a revenue, ready time, due date, deadline, and consists of a set of operations with precedence relationships. Jobs that deviate from their due dates incur earliness/tardiness penalties. An operation may require several units of capacity per time unit and a resource could have multiple units of capacity. The manufacturer can reject any job to satisfy the capacity constraints and maximise the overall profit. We develop a mathematical model for the problem, then use an agent-based approach to solve it. First, the relaxed problem is decomposed into a set of job-level subproblems. Each job is optimised individually without considering the capacity constraints. Profitable jobs at the individual level submit their optimal schedules as combinatorial bids to an auctioneer to acquire combinations of resource capacity-time units. Then, the auctioneer records the profit upper bound, resolves capacity conflicts to reach a feasible solution, records the profit lower bound, and updates the dual variables. Experimental results show that the proposed methodology can solve large-sized problems in reasonable CPU times. [ABSTRACT FROM AUTHOR]

Given the high demand for energy in the manufacturing industry and the increasing use of renewable but volatile energy sources, it becomes increasingly important to coordinate production and energy availability. With the help of incentive-based programmes, grid operators can incentivise consumers to adjust power demand in critical situations such that grid stability is not threatened. On the consumer side, energy-efficient scheduling models can be used to make energy consumption more flexible. This paper proposes a bi-objective job-shop scheduling problem with variable machine speeds that aims on minimising the total energy consumption and total weighted tardiness simultaneously. We use a genetic algorithm to solve the model and derive Pareto frontiers to analyse the trade-off between both conflicting objectives. We gain insights into how incentive-based programmes can be integrated into machine scheduling models and analyse the potential interdependencies and benefits that result from this integration. [ABSTRACT FROM AUTHOR]

The paper presents a discrete-time mixed-integer linear programming (MILP) model for a generalised flexible job-shop scheduling problem as represented by a state-task network. The problem is characterised by reentrant flow, sequence-dependent changeover time, machine downtime, and skilled labour requirements. Two preprocessing procedures are proposed to reduce the size of the MILP model, and represent a major contribution of the research. The procedures reduce the number of assignment variables by exploiting job precedence and workforce qualifications. Machine availability for each task is determined as a function of possible start and end times, given duration, and maintenance schedule. The overall objective is to maximise the number of scheduled tasks while minimising their total finish time. Computational experiments are conducted with real and randomly generated instances. The results show that optimal solutions can be obtained for medium-size problems within a reasonable amount of time, primarily due to the use of the preprocessing procedures. [ABSTRACT FROM AUTHOR]

Nowadays, achieving higher levels of flexibility in manufacturing systems is necessary to maintain and enhance competitiveness. Accordingly, a new generation of production machine, namely Reconfigurable Machine Tool (RMT), has recently been introduced that can be effectively adapted to changes. Nevertheless, such systems are more worker-reliant, and neglecting workforce aspects results in suboptimal or even infeasible production schedules. In this regard, this study investigates an integrated lot-sizing and scheduling problem benefiting from RMTs under workforce constraints. First, a novel Mixed-Integer Linear Programming (MILP) model is provided to formulate the problem. Afterward, to confront the high complexity of the problem, an efficient Decomposition Heuristic (DH) empowered by a tailored feasibility cut is devised. A combination of MILP and Constraint Programming (CP) is employed in the DH to model the relevant master and sub-problems, respectively. Finally, the performance of the DH compared to the MILP model and an extended lower bound is evaluated. Moreover, the advantages of utilizing RMTs in the system are explored based on four defined key performance indicators. [ABSTRACT FROM AUTHOR]

A production plan gives the quantity of products to release on the shop floor in each period, where a period may represent a week or a month. The plan is the basis for negotiating order acceptance and delivery dates with customers and suppliers. The production plan must respect the available capacity on the shop floor, as underloading the shop floor leads to a loss of opportunity, and thus, a loss of competitiveness for the company. To properly manage the production capacity while negotiating with suppliers and customers, the production planners need a tool to accurately estimate the capacity consumption in each period. The computation of capacity consumption requires creating a detailed production schedule which is a complex task. Algorithms that find close to optimal schedules in a complex manufacturing environment are often time-consuming, which is impractical in a negotiation context. We investigate machine learning models to predict capacity consumption. We consider a flexible job-shop as commonly encountered in practice, and proposed several machine learning models. Namely, several variants of linear regression, decision trees, and artificial neural networks. Numerical experiments showed that our models outperform those found by both an exact approach and dispatching rules when computation time is short. [ABSTRACT FROM AUTHOR]

The transformation of production mode leads to the need to strictly ensure the order in-time delivery. The global control ability of manufacturing workshops has become a necessary capability for enterprises. The real-time accurate Order Remaining Completion Time (ORCT) prediction allows managers to master the production schedule fluctuation, which provides criteria for workshop management. Due to the widespread deployment of Internet of Things (IoT) devices in the workshop, the difficulty of systematic processing and analysis of multi-dimensional heterogeneous data has been the main pain point of ORCT prediction. To tackle these problems, a Manufacturing Big Data (MBD)-driven ORCT prediction method based on Salp Swarm Algorithm (SSA) and Bidirectional Long Short-Term Memory (BiLSTM) is proposed. An attribute selection algorithm combined with max-relevance and min-redundancy and regularisation is used to mine key data from MBD. An SSA-BiLSTM model is proposed to achieve efficient and accurate ORCT prediction. The prediction model is supported by BiLSTM, and the hyperparameters are optimised by SSA. Finally, a case study about ORCT prediction in the IoT-enabled manufacturing workshop is presented. The result verifies that the proposed ORCT prediction method has obvious advantages over the other three traditional methods in accuracy and efficiency. [ABSTRACT FROM AUTHOR]

Scheduling is a complex task due to the need to optimise multiple competing objectives and react to unpredictable events that may occur during production execution. The strategy of predictive-reactive scheduling can be used to reconcile the conflict between the original schedule and the current shop floor situation. This study seeks to present an inventory data-driven predictive-reactive production scheduling model that supports the evolving concepts of the Industry 4.0. Periodically, a machine learning technique provides predictive scheduling considering a best-case scenario according to an established Key Performance Indicator (KPI). Then, material non-availability causes disruptions in production, which triggers the Simulation-Based Optimization (SBO) method to handle these events. Thus, SBO provides a reactive schedule with the best set of priority rules to sequence jobs on each machine according to the data on the shop floor. This model was validated with a real case study using data collected from a metal-mechanical company. Considering the service level KPI, the results showed that the model is able to find a better solution in the compared scenarios. Therefore, even in a dynamic and stochastic scenario, with machine breakdowns, quality problems, raw material delays, and accuracy issues, the model proved efficient in mitigating these variations' effects. [ABSTRACT FROM AUTHOR]

Current studies on scheduling of machines and transporters assume that either a single transporter or an infinite number of homogeneous transporters such as AGVs or mobile robots are available to transport semi-finished jobs, which seems very restrictive in practice. This paper addresses this gap by studying a job-shop scheduling problem that incorporates a limited number of heterogeneous transporters, where the objective is to minimize the makespan. The problem is modelled using mixed-integer linear programming and constraint programming. Different structure-based branch-and-bound algorithms with two lower-bounding strategies are also developed. A comprehensive numerical study evaluates the proposed models and algorithms. The research demonstrates that the adjustment of the proposed MILP model outperforms the existing formulation when applied to the homogeneous case. The study also uncovers interesting practical implications, including the analysis of the impact of different transporter types in the system. It shows that utilizing a fleet of heterogeneous transporters can improve the overall performance of the job shop compared to a relevant homogeneous case. The importance of the study is emphasized by highlighting the negative consequences of disregarding transporters' differences during the scheduling phase. [ABSTRACT FROM AUTHOR]

This paper provides a systematic review of the Genetic Algorithm (GA)s proposed to solve planning and scheduling problems in Engineer-To-Order (ETO) contexts. Our review focuses on how the key characteristics of ETO projects affect both the problem studied and the GA algorithmic features. Typical ETO projects consist of one-of-a-kind products with complex structures and uncertain designs. A deep analysis of the papers published between 2000 and 2022 enables identifying 10 main characteristics of ETO projects, six activity types, 10 decision types, eight groups of constraints, and 10 optimisation objectives. Our study shows that none of the reported papers integrates all 10 ETO characteristics. The less studied ETO characteristics are incorporating design and engineering information in the problem definition and the design uncertainty. Our review also identifies 10 recurrent encoding formats and emphasises the most frequently used genetic operators. We observed that most planning and scheduling problems consider objectives and decisions related to product customisation or supply chain configuration yielding multi-objective problems. Most multi-objective GAs use a weighted sum or are based on NSGAII. Diversity maintenance methods, adaptive and parameter tunning mechanisms, or hybridisation with machine learning models are still not used in this context. A systematic review of genetic algorithms dedicated to industrial planning and scheduling Analysis on how the characteristics of ETO projects impact the design of genetic representation and operators Recommendation on approaches employed to reach high-quality solutions [ABSTRACT FROM AUTHOR]

In this work, we study the multi-product dynamic lot-sizing problem with capacity constraints and batch ordering. This problem arises in short to medium range production scheduling for several products over a finite number of periods to meet known demand. Each period has a capacity for placing orders, and every order for each product must have a fixed quantity, or batch size, though multiple orders can be placed for each product. We define three mixed-integer linear programming (MILP) models and apply Lagrangian relaxation to formulate the corresponding dual problems by relaxing the capacity constraints. The aim is to identify the dual problem that is the easiest to solve and provides the solution with the smallest duality gap. Subgradient optimisation is applied to solve the preferred Lagrangian dual model, which uses one of two heuristics to find good feasible solutions. We also show that the special case, where the batch sizes for all products are the same, can be modeled as a transportation problem. A set of numerical experiments is designed to compare the performance of the Lagrangian relaxation approach with a commercial MILP solver to identify the version of the subgradient algorithm and the MILP model that provide the best solutions. [ABSTRACT FROM AUTHOR]

In the maintenance optimisation framework, grouping maintenance is a promising solution for maintenance planning of multi-component systems, in which maintenance activities are performed together to reduce maintenance costs. One of the most widely identified challenges in real applications of grouping maintenance is that it may disturb the maintenance workload balance (smoothness), causing many difficulties in production and/or labour scheduling and inventory management. In this study, we propose a joint optimisation approach for maintenance grouping and workload balancing to address the above challenge. First, a mathematical model of the joint optimisation problem was derived. A multi-objective grouping optimisation approach based on the Weighted Sum model and Genetic Algorithm was implemented to determine the Pareto-optimal grouping solution. The proposed approach was applied to a real case study of an automotive plant comprising 40 production lines with 1090 components. The results highlighted the advantages, effectiveness, and flexibility of the proposed maintenance approach in real-world applications. [ABSTRACT FROM AUTHOR]

This work presents four mixed integer linear programming (MILP) models for the assembly flow shop problem in order to minimize the makespan. This production environment has two stages: production and assembly. The first stage consists of different machines designed to manufacture parts of a product. The second stage is intended for a final assembly. The performance measure considered is highly essential for industries from different segments, as it focuses on the best use of the time available for production. Statistical analysis with different tools was used to assess the performance and efficiency of mathematical models, emphasizing the analysis of performance profiles. Results showed that mathematical models are efficient, and the position-based model presented the best results for small and large instances during computational experimentation. All mathematical models can be used as direct tools in decision-making for the production sequencing problem in the approached environment. [ABSTRACT FROM AUTHOR]

We analyse the joint scheduling of spare parts production and service engineers in a multi-site maintenance system. In the system, for each failure, a service engineer with the required spare part needs to be allocated for on-site maintenance. If one of the required resources is not readily available, the maintenance task can be satisfied via an external channel with quick responsiveness but high involved costs. Service providers need to make an efficient plan, including production scheduling of spare parts, allocation of service engineers and outsourcing strategy. First, a mathematical model with the objectives of minimum total outsourcing costs and minimum weighted tardiness is formulated. Then, a novel and knowledge-based heuristic algorithm is developed, namely progressive Pareto algorithm based on step-size (PPAS). To verify the performance of PPAS, it is compared against other well-known algorithms, including NSGA-II, MOEA/D, NNIA, RIPG, MMOIG and MNNIA. Finally, the effectiveness of the joint scheduling mode is demonstrated by comparing it with the separate optimisation mode of spare parts production and workforce allocation. Highlights Analyse the joint scheduling of spare parts production and service engineers Construct a bi-objective optimisation model Develop a progressive Pareto algorithm based on step-size Verify the superiority of the proposed algorithm and joint scheduling mode [ABSTRACT FROM AUTHOR]

Planning and scheduling approaches in real manufacturing environments entail the need to cope with random attributes and variables to match the characteristics of real scheduling problems where uncertain events are frequent. Moreover, the capability of devising robust schedules, which are less sensitive to the disruptive effects of unexpected events, is a major request in real applications. In this paper, a branch-and-bound approach is proposed to solve the two-machine permutation flow shop scheduling problem with stochastic processing times. The objective is the minimisation of the value-at-risk of the makespan, to support decision-makers in the trade-off between the expected performance and the mitigation of the impact of extreme scenarios. A Markovian Activity Network (MAN) model is adopted to estimate the distribution of the makespan and assess the value-at-risk for both partial and complete schedules. Phase-type distributions are used to enable general distributions for processing times while maintaining the capability to exploit a Markovian approach. The effectiveness and performance of the proposed approach are demonstrated through a set of computational experiments. [ABSTRACT FROM AUTHOR]

Inspired by real-life applications, mainly in hand-intensive manufacturing, the incorporation of learning effects into scheduling problems has garnered attention in recent years. This paper deals with the flowshop scheduling problem with a learning effect, when minimising the makespan. Four approaches to model the learning effect, well-known in the literature, are considered. Mathematical models are providing for each case. A solver allows us to find the optimal solution in small problem instances, while a Simulated Annealing algorithm is proposed to deal with large problem instances. In the latter, the initial solution is obtained using the well-known Nawaz-Enscore-Ham algorithm, and two local search operators are evaluated. Computational experiments are carried out using benchmark datasets from the literature. The Simulated Annealing algorithm shows a better result for learning approaches with fast learning effects as compared to slow learning effects. Finally, for industrial decision makers, some insights about how the learning effect model might affect the makespan minimisation flowshop scheduling problem are presented. [ABSTRACT FROM AUTHOR]

Human–robot collaboration has been incorporated into production and assembly processes to promote system flexibility, changeability and adaptability. However, it poses new challenges to resource allocation and production scheduling due to its intrinsic uncertainty and also the increasing complexity of resources. This paper investigates a stochastic flow shop scheduling problem in the context of human–robot collaboration. The goal is to achieve efficient utilisation of flexible resources including human workers and cobots and take full advantage of human–robot collaboration in production scheduling. A stochastic Cobb–Douglas production function is utilised to evaluate the production efficiency of human–robot collaboration considering instabilities of human performance. A joint chance-constrained programming model is formulated to ensure that the required system performance can be achieved. A CVaR approximation-based approach is proposed to solve the formulated model with mixed-integer variables and a nonconvex constraint. The effectiveness of the formulated model and the efficiency of the proposed solution approach are evaluated via numerical experiments. Computational results show the superiority of our solution approach over three other approaches including Bonferroni approximation, scenario approach and individual chance-constrained programming. [ABSTRACT FROM AUTHOR]

This work extends the energy-efficient job shop scheduling problem with transport resources by considering speed adjustable resources of two types, namely: the machines where the jobs are processed on and the vehicles that transport the jobs around the shop-floor. Therefore, the problem being considered involves determining, simultaneously, the processing speed of each production operation, the sequence of the production operations for each machine, the allocation of the transport tasks to vehicles, the travelling speed of each task for the empty and for the loaded legs, and the sequence of the transport tasks for each vehicle. Among the possible solutions, we are interested in those providing trade-offs between makespan and total energy consumption (Pareto solutions). To that end, we develop and solve a bi-objective mixed-integer linear programming model. In addition, due to problem complexity we also propose a multi-objective biased random key genetic algorithm that simultaneously evolves several populations. The computational experiments performed have show it to be effective and efficient, even in the presence of larger problem instances. Finally, we provide extensive time and energy trade-off analysis (Pareto front) to infer the advantages of considering speed adjustable machines and speed adjustable vehicles and provide general insights for the managers dealing with such a complex problem. [ABSTRACT FROM AUTHOR]

Nowadays, the manufacturing sector needs higher levels of flexibility to confront the extremely volatile market. Accordingly, exploiting both machine and workforce reconfigurability as two critical sources of flexibility is advantageous. In this regard, for the first time, this paper explores an integrated production scheduling and workforce planning problem in a Reconfigurable Manufacturing System (RMS) benefiting from reconfigurable machines and human-robot collaboration. A new Mixed-Integer Linear Programming (MILP) model and an efficient Constraint Programming (CP) model are developed to formulate the problem, minimising the makespan as the performance metric. Due to the high complexity of the problem, the MILP model cannot handle large-sized instances. Hence, to evaluate the performance of the CP model in large-sized instances, a lower bound is derived based on the relaxation of the problem. Finally, extensive computational experiments are carried out to assess the performance of the devised MILP and CP models and provide general recommendations for managers dealing with such a complex problem. The results reveal the superiority of the CP model over the MILP model in small- and medium-sized instances. Moreover, the CP model can find high-quality solutions for large-sized instances within a reasonable computational time. [ABSTRACT FROM AUTHOR]

This paper studies the customer order scheduling problem in the context of additive manufacturing. The study discusses an integrated problem involving the nesting of parts as well as the scheduling of batches of nested parts onto unrelated parallel machines. A mixed-integer programming model is presented, based on existing formulations from the literature, that integrates different materials and sequence-dependent setup times. Additionally, a metaheuristic based on an iterated local search is proposed for the problem configuration under consideration. Focusing on minimizing the total weighted tardiness of orders, the efficiency of the heuristic approach is evaluated using comprehensive test data. Further, we show the importance of the considered order-related objective by using qualitative analysis. [ABSTRACT FROM AUTHOR]

We investigate a stochastic distributed appointment assignment and scheduling problem, which consists of assigning appointments to distributed service units and determining service sequences at each service unit. In particular, the service time duration and release time uncertainties are well-considered. The solution to this generic problem finds interesting applications in distributed production systems, healthcare systems, and post-disaster operations. We formulate the problem as a two-stage stochastic program to minimise the total transportation cost and expected makespan, idle time or overtime, and apply the sample average approximation method to make the problem tractable. We then develop a stochastic logic-based Benders decomposition method, decomposing the problem into a master problem and a subproblem. The master problem determines the appointment assignment variables, and the subproblem handles the sequence and service start time variables. Benders optimality cuts are generated from the subproblem's solution and added to the master problem. The developed stochastic logic-based method is advantageous since it can manage many scenarios in parallel. We further consider each appointment's due date, minimise the weighted earliness and tardiness, and adjust the developed method to solve this variant. Experiments on random instances demonstrate the excellent performance of the proposed model and methods. [ABSTRACT FROM AUTHOR]

According to [Dolgui, Alexandre, and Jean Marie Proth. 2010. Supply Chain Engineering: Useful Methods and Techniques. Vol. 539. Springer.], advancing tactical levels in production systems has led to the disappearance of static scheduling in favour of dynamic scheduling. Additionally, the evolving challenges in the supply chain paradigm have significantly impacted the organisation of production systems. This shift has moved scheduling issues from the tactical to the strategic level, resulting in linear organisations encompassing scheduling decisions. [Proth, Jean Marie. 2007. "Scheduling: New Trends in Industrial Environment." Annual Reviews in Control 31 (1): 157–166. .] emphasised that real-time scheduling in production systems has become a pivotal area of research. He presented several open problems for researchers to address in this context, including (1) the development of real-time algorithms capable of handling multiple operations on the same product and unrelated resources, (2) adapting previous schedules with certain modifications, (3) addressing unforeseen actions that arise randomly in real-time planning, and (4) exploring cyclic scheduling problems with size limits as alternative solutions to heuristic approaches. This paper reviews the evolving trends in light of J.M. Proth's predictions and advice within the aforementioned domains. [ABSTRACT FROM AUTHOR]

Increased flexibility in job shops leads to more complexity in decision-making for shop floor engineers. Partial Flexible Job Shop Scheduling (PFJSS) is a subset of Job shop problems and has substantial application in the real world. Priority Dispatching Rules (PDRs) are simple and easy to implement for making quick decisions in real-time. The present study proposes a novel method of integrating Multi-Criteria Decision Making (MCDM) methods and the Discrete Event Simulation (DES) Model to define job priorities in large-scale problems involving multiple criteria. DES approach is employed to model the PFJSS to evaluate Makespan, Flow Time, and Tardiness-based measures considering static and dynamic job arrivals. The proposed approach is implemented in a benchmark problem and large-scale PFJSS. The integration of MCDM methods and simulation models offers the flexibility to choose the parameters that need to govern the ranking of jobs. The solution given by the proposed methods is tested with the best-performing Composite Dispatching Rules (CDR), combining several PDR, which are available in the literature. Proposed MCDM approaches perform well for Makespan, Flow Time, and Tardiness-based measures for large-scale real-world problems. The proposed methodology integrated with the DES model is easy to implement in a real-time shop floor environment. [ABSTRACT FROM AUTHOR]

In this paper, we address a Stochastic-Demand Assembly Job Shop Scheduling Problem (SD-AJSSP) in the presence of the commonality of sub-assemblies across products. We propose a new production methodology, named Assemble-to-Order with Commonality of Sub-Assemblies (ATO-CS) to not only solve the SD-AJSSP, but also, achieve a successful implementation of a mass customisation system by collectively aiming to (1) keep the production costs low by leveraging upon commonality of sub-assemblies in products' BOM and producing sub-assemblies on a mass scale during one of the two stages of production, (2) minimise the loss due to excess inventory build-up in anticipation of stochastic demand of products by postponing the production of certain apex sub-assemblies in products' BOM until the actual demand is realised, and (3) reduce the time of the products' delivery to customers. The ATO-CS method determines optimum production levels as well as schedules assembly operations/jobs over the machines at each stage of production, where the second stage is an assembly job shop and is shown to outperform commonly-used production methodologies. We also develop an algorithm for its implementation and show its efficacy over the use of the state-of-the-art commercial solver CPLEX® in obtaining a lower solution cost and smaller optimality gap. [ABSTRACT FROM AUTHOR]

Autonomous vehicle storage and retrieval systems (AVS/RSs) are widely used in e-commerce warehouses due to their high throughput and flexibility. In such systems, storage and retrieval transactions are performed by lifts and vehicles. This paper focuses on the sequencing retrievals problem in an AVS/RS, which is an important problem for daily operations. We formulate this sequencing problem as a mixed-integer program to determine a retrieval sequence for the lift and the vehicles, one that minimises the makespan. A dynamic programming approach is proposed to solve the sequencing problem to optimality. However, the solution time of the dynamic programming method is exponentially increasing in the number of retrieval requests. To be more practical, we present a beam search heuristic that can solve large-sized instances in reasonable time. Computational experiments verify that near-optimal solutions can be found by the beam search heuristic. Compared to commonly used heuristics and straightforward heuristics, the beam search decreases the makespan by up to 15%. Finally, we analyse how vehicle modes impact the makespan, showing evidence that a small makespan can be achieved when considering a realistic mode of vehicles. [ABSTRACT FROM AUTHOR]

In this paper, a variant of the open shop scheduling problem is considered in which the intermediate storage is forbidden among two adjacent production stages (zero buffer or machine blocking constraint). The performance measure is to minimise the maximal completion time of the jobs (makespan). Since this is an NP-hard problem, a two-stage constraint programming approach is proposed as a new exact method. Computational experiments were carried out on 222 literature problem instances in order to test the performance of the proposed algorithm. The relative deviation is adopted as the performance criteria. Computational results point to the ability of the proposed method to solve large-sized instances in comparison with the developed mixed-integer linear programming model and a simple constraint programming model, both with user cuts. In all set of instances, the proposed two-stage method performed better than benchmarking methods and integer programming models, with average relative deviation regarding objective values as lower as 12%. In addition, the results point to a competitive efficiency in computational times of the proposed method with less than 200 s in the most instances to obtain the optimal solution, in comparison to competitive metaheuristics from literature of the problem, for the tested test instances. [ABSTRACT FROM AUTHOR]

Additive manufacturing (AM) introduces a set of technology-specific problems, such as the proper orientation of parts or the placement of several heterogeneous parts in the same build cycle, which are not addressed by traditional approaches to production planning and scheduling. Although these new production subproblems have been implicitly addressed by several works according to generic nesting and scheduling concepts, a literature review revealed that there is no uniformity in identifying and, thus, solving all these subproblems. For this reason, and as a result of an in-depth analysis of the existent literature on AM production planning and an analogy with classic cutting and packing typologies, the present paper offers a framework to formalise the production planning problem in AM at the operational level. This framework can be used as a reference to focus on and address these AM-related problems for efficient production planning. It is designed at the subproblem level and centres on production order processing in AM. A coding strategy is specifically developed for the framework, which is applied to a review of relevant works that propose models for the production planning of AM systems. Finally, the review results are discussed and possible extensions of the framework are proposed. [ABSTRACT FROM AUTHOR]

Production planning and scheduling for companies with divergent processes, where a single component can be transformed into several finished products, are challenging as planners might face material misallocation issues. In this paper, we address the problem of managing a divergent process with DDMRP stock buffers, where different finished products are bottled with the same component having a fixed batch size. An allocation decision needs to be made to determine the quantities of finished products to be bottled. This study is motivated by a real-life problem faced by a dermo-cosmetic company. We compare and analyze by simulation nine different policies triggering allocation decisions. The first policy is the classic DDMRP rule, while the others are new policies, including a virtual buffer of a generic finished product and ConWIP loops, delaying the allocation decision. Our results show that the policy combining the classic DDMRP rule and a ConWIP loop surrounding a part of the process reduces the work-in-process by 34% compared to the classic DDMRP while ensuring high customer service rates and control of flow times. [ABSTRACT FROM AUTHOR]

This paper introduces the Cyclic Production Routing Problem (CPRP). The CPRP is an extension of the well-known NP-hard Production Routing Problem (PRP), which is a hard-to-solve combinatorial optimisation problem with numerous practical applications in the field of freight transportation, logistics and supply chain management. Under the PRP setting, a manufacturer is responsible for determining production decisions, as well as the timing and quantity of replenishment services offered to a set of geographically dispersed customers over a multi-period time horizon. The problem calls for jointly optimising the production, inventory, distribution and routing decisions. In this paper, the basic PRP model is modified to generate repeatable cyclic production and delivery schedules. A two-commodity flow formulation is proposed along with valid inequalities. Extensive comparisons between the basic PRP and the proposed cyclic variant on well-known benchmark instances are provided. The new variant is significantly harder to solve, especially when the vehicle fleet is limited. From a managerial perspective, the generation of cyclic production-routing schedules significantly increases all costs, whereas the number of vehicle routes required to implement a cyclic schedule is higher. [ABSTRACT FROM AUTHOR]

Lot splitting is one of the effective technologies of time-based strategy and has been widely studied in a variety of production environments. Nevertheless, the literature on its application in seru production has been highly scarce until now. Seru system is composed of simple equipment and multi-skilled workers, which can be quickly converted from the traditional assembly line to seru units. As an innovative production mode, seru production inevitably allows applying lot splitting in the real world. Therefore, a multi-objective model is studied for line–cell conversion with lot splitting, aiming at determining the trade-off among makespan, inter-seru system balancing, and intra-seru system balancing. Due to the proposed model's NP-hard nature, an improved NSGA-II was developed to solve it. Finally, extensive numerical simulations are conducted. Compared to no lot splitting, lot splitting is improved by 4.2% and 3.7% in terms of inter-seru system balancing and makespan respectively. The better efficiency and effectiveness of the improved NSGA-II are proved by comparisons with other state-of-the-art algorithms. Additionally, a sensitivity analysis is conducted to ascertain the degree of contribution of the model parameters towards the value of objectives, which provides management implications to support the decision-making of seru production for the enterprise. [ABSTRACT FROM AUTHOR]

Multi-variety and small-batch production mode enables manufacturing industries to expeditiously satisfy customers' personalised demands, where a large amount of identical jobs can be split into several sublots, and be processed by reconfigurable machines with multiple machining technics. However, such highly flexible manufacturing environments bring some intractable problems to the production scheduling. Mathematical programming and meta-heuristic methods become less efficient when a scheduling problem contains both discrete and continuous optimisation attributes. Therefore, matheuristic, which combines advantages of the two methodologies, is regarded as a promising solution. This paper investigates a flexible job shop scheduling problem with lot-streaming and machine reconfigurations (FJSP-LSMR) for the total weighted tardiness minimisation. First, a monolithic mixed integer linear programming (MILP) model is established for the FJSP-LSMR. Afterwards, a matheuristic method with a variable neighbourhood search component (MH-VNS) is developed to address the problem. The MH-VNS adopts the classical genetic algorithm (GA) as the framework, and introduces two MILP-based lot-streaming optimisation strategies, LSO1 and LSO2, to improve lot-sizing plans with varying degrees. Four groups of instances are extended from the well-known Fdata benchmark to evaluate the performance of proposed MILP model, LSO1 and LSO2 components, and MH-VNS. Numerical experimental results suggest that LSO1 and LSO2 are efficient in different scenarios, and the proposed MH-VNS can well balance the solution quality and computational costs for reasonably integrating the GA- and MILP-based local search strategies. In addition, a complicated FJSP-LSMR case is abstracted from a real-world shop floor for processing large-sized structural parts to further validate the MH-VNS. [ABSTRACT FROM AUTHOR]

In this article, maintenance operations were incorporated to the sequence-dependent setup blocking flow shop to minimise total completion time subject to total maintenance costs. A mixed integer linear programming and procedures to incorporate maintenance to job sequence were developed. A constructive heuristic and three metaheuristics, greedy randomised adaptative search procedure (GRASP), discrete artificial bee colony (DABC), variable block insertion heuristic (VBIH) and iterated greedy algorithm (IG), designed to the blocking flow shop with total completion time minimisation were adapted to minimise total maintenance costs and the hierarchical function, respectively.All the methods were applied to solve small and medium and large size instance sets, with respective 1920 and 2200 problems. Experimental results shows that for small size instances set, DABC with α = 20 (DABC(20)) obtained the best trade-off between effectiveness and efficiency. For medium and large size instances set, DABC(20) VBIH with α = 20 (VBIH(20)) generated the best trade-off between quality of solution and computational time. Considering both instances set together, both DABC(20) and VBIH(20) obtained the best performance between quality of solution and computational time. [ABSTRACT FROM AUTHOR]

A set of jobs has to be processed on identical machines. Every job may be processed on any available machine without preemptions. The criterion is to minimise the makespan (i.e. the completion time of the last job in a schedule). During the realisation of a schedule, durations of some jobs may deviate from the initial values estimated before scheduling. Other jobs have fixed durations that are known before scheduling. We conduct a stability analysis of the optimal semi-active schedule. First, we derive necessary and sufficient conditions for an optimal schedule to be unstable with respect to infinitely small variations of the non-fixed durations (the stability radius of an unstable schedule is equal to zero). Second, we show that the stability radius of an optimal schedule could be infinitely large. Furthermore, several lower and upper bounds on the stability radius have been established. Third, we derive a formula and develop an algorithm for calculating stability radii. [ABSTRACT FROM AUTHOR]