Hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints

One of the common assumptions in the field of scheduling is that machines are always available in the planning horizon. This may not be true in realistic problems since machines might be busy processing some jobs left from previous production horizon, breakdowns or preventive maintenance activities. Another common assumption is the consideration of setup times as a part of processing times, while in some industries, such as printed circuit board and automobile manufacturing, not only setups are an important factor but also setup magnitude of a job depends on its immediately preceding job on the same machine, known as sequence-dependent setup times. In this paper, we consider hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints caused by preventive maintenance. The optimization criterion is the minimization of makespan. Since this problem is NP-hard in the strong sense, we propose three heuristics, based on SPT, LPT and Johnson rule and two metaheuristics based on genetic algorithm and simulated annealing. Computational experiments are performed to evaluate the efficiencies of the algorithms.     

An effective heuristic for flexible job-shop scheduling problem with maintenance activities

Most production scheduling problems, including the standard flexible job-shop scheduling problem (FJSP), assume that machines are continuously available. However, in most realistic situations, machines may become unavailable during certain periods due to preventive maintenance (PM). In this paper, a flexible job-shop scheduling problem with machine availability constraints is considered. Each machine is subject to preventive maintenance during the planning period and the starting times of maintenance activities are either flexible in a time window or fixed beforehand. Moreover, two cases of maintenance resource constraint are considered: sufficient maintenance resource available or only one maintenance resource available. To deal with this variant FJSP problem with maintenance activities, a filtered beam search (FBS) based heuristic algorithm is proposed. With a modified branching scheme, the machine availability constraint and maintenance resource constraint can be easily incorporated into the proposed algorithm. Simulation experiments are conducted on some representative problems. The results demonstrate that the proposed filtered beam search based heuristic algorithm is a viable and effective approach for the FJSP with maintenance activities.     

Use of (max, +) algebra for scheduling and optimization of HVLV systems subject to preventive maintenance

High-Variety, Low-Volume (HVLV) manufacturing systems are built to produce parts of several types in small quantities and under multiple production objectives. They relate to job-shop systems well known by researchers. One of the most studied assumptions of HVLV systems scheduling is considering that machines may be periodically unavailable during the production scheduling. This article deals with an analytical integrating method using (max, +) algebra to model HVLV scheduling problems subject to preventive maintenance (PM) while considering machines availability constraints. Each machine is subject to PM while maintaining flexibility for the start time of the maintenance activities during the planning period. The proposed model controls the placement of maintenance activities along the production operations. Indeed, the sequencing of maintenance activities on the machines depends on the criteria to minimize and may be different for each criteria value. For preventive maintenance, the proposed model aims to generate the best sequencing between activities while respecting the planning program that satisfy the optimal criteria values. In order to illustrate the performance of the proposed methodology, a simulation example is given.     

Two-machine flow shop scheduling integrated with preventive maintenance planning

This paper investigates an integrated optimisation problem of production scheduling and preventive maintenance (PM) in a two-machine flow shop with time to failure of each machine subject to a Weibull probability distribution. The objective is to find the optimal job sequence and the optimal PM decisions before each job such that the expected makespan is minimised. To investigate the value of integrated scheduling solution, computational experiments on small-scale problems with different configurations are conducted with total enumeration method, and the results are compared with those of scheduling without maintenance but with machine degradation, and individual job scheduling combined with independent PM planning. Then, for large-scale problems, four genetic algorithm (GA) based heuristics are proposed. The numerical results with several large problem sizes and different configurations indicate the potential benefits of integrated scheduling solution and the results also show that proposed GA-based heuristics are efficient for the integrated problem.     

New integration of preventive maintenance and production planning with cell formation and group scheduling for dynamic cellular manufacturing systems

This paper proposes a new integration method for cell formation, group scheduling, production, and preventive maintenance (PM) planning problems in a dynamic cellular manufacturing system (CMS). The cell formation sub-problem aims to form part families and machine groups, which minimizes the inter-cell material handling, under-utilization, and relocation costs. The production planning aspect is a multi-item capacitated lot-sizing problem accompanied by sub-contracting decisions, while the group scheduling problem deals with the decisions on the sequential order of the parts and their corresponding completion times. The purpose of the maintenance sub-problem is to determine the availability of the system and the time when the noncyclical perfect PM must be implemented to reduce the number of corrective actions. Numerical examples are generated and solved by Bender’s decomposition pack in GAMS to evaluate the interactions of the proposed model. Statistical analysis, based on a nonparametric method, is also used to study the behavior of the model’s cost components in two different situations. It is shown that by adding the PM planning decisions to the tactical decisions of the dynamic CMS, the optimal configuration and production plans of the system are heavily affected. The results indicate that omitting the PM actions increases the number of sudden failures, which leads to a higher total cost. Finally, it is concluded that the boost in the total availability of the dynamic CMS is one of the main advantages of the proposed integrated method.     

Integrating the lot-sizing and sequencing decisions for scheduling a capacitated flow line

In this paper we consider a general problem of scheduling a single flow line consisting of multiple machines and producing a given set of jobs. The manufacturing environment is characterized by sequence dependent set-up times, limited intermediate buffer space, and capacity constraints. In addition, jobs are assigned with due dates that have to be met. The objectives of the scheduling are: (1) to meet the due dates without violating the capacity constraints, (2) to minimize the makespan, and (3) to minimize the inventory holding costs. While most of the approaches in the literature treat the problem of scheduling in flow lines as two independent sub-problems of lot-sizing and sequencing, our approach integrates the lot-sizing and sequencing heuristics. The integrated approach uses the Silver-Meal heuristic (modified to include lot-splitting) for lot-sizing and an improvement procedure applied to Palmer's heuristic for sequencing, which takes into account the actual sequence dependent set-up times and the limited intermedite buffer capacity. We evaluate the performance of the integrated approach and demonstrate its efficacy for scheduling a real world SMT manufacturing environment.     

Optimisation of PM scheduling for multi-component systems – a simulated annealing approach

Proper planning of preventive maintenance (PM) is crucial in many industries such as oil transmission pipelines, automotive and food industries. A critical decision in the PM plans is to determine frequencies and types of maintenance actions in order to achieve a certain level of system availability with a minimum total cost. In this paper, we consider the problem of obtaining availability-based non-periodic optimal PM planning for systems with deteriorating components. The objective is to sustain a certain level of availability with the minimal total maintenance-related costs. In the proposed approach, the planning horizon is divided into some inspection periods of equal intervals. For any given interval, a decision must be made to perform one of the three actions on each component; inspection, preventive repair and preventive replacement. Any of these activities has different effects on the reliability of the components and the corresponding distinct costs based on the required recourses. The cost function includes the cost for repair, replacement, system downtime and random failures. System availability and PM resources are the main constraints considered. Since the proposed model is combinatorial in nature involving non-linear decision variables, a simulated annealing algorithm is employed to provide good solutions within a reasonable time.     

Capacitated lot sizing and sequence dependent setup scheduling: an iterative approach for integration

We consider here the lot sizing and scheduling problem in single-level manufacturing systems. The shop floor is composed of unrelated parallel machines with sequence dependent setup times. We propose an integer programming model embedding precise capacity information due to scheduling constraints in a classical lot-sizing model. We also propose an iterative approach to generate a production plan taking into account scheduling constraints due to changeover setup times. The procedure executes two decision modules per iteration: a lot-sizing module and a scheduling module. The capacitated lot-sizing problem is solved to optimality considering estimated data and aggregate information, and the scheduling problem is solved by a GRASP heuristic. In the proposed scheme the information flow connecting the two levels is managed in each iteration. We report a set of computational experiments and discuss future work.     

A hybrid Lagrangian-simulated annealing-based heuristic for the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times

This paper examines the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times, time windows, machine eligibility and preference constraints. Such problems are quite common in the semiconductor manufacturing industry. In particular, this paper pays special attention to the chipset production in the semiconductor Assembly and Test Manufacturing (ATM) factory and constructs a Mixed Integer Programming (MIP) model for the problem. The primal problem is decomposed into a lot-sizing subproblem and a set of single-machine scheduling subproblems by Lagrangian decomposition. A Lagrangian-based heuristic algorithm, which incorporates the simulated annealing algorithm aimed at searching for a better solution during the feasibility construction stage, is proposed. Computational experiments show that the proposed hybrid algorithm outperforms other heuristic algorithms and meets the practical requirement for the tested ATM factory.     

Solving distributed FMS scheduling problems subject to maintenance: Genetic algorithms approach

In general, distributed scheduling problem focuses on simultaneously solving two issues: (i) allocation of jobs to suitable factories and (ii) determination of the corresponding production scheduling in each factory. The objective of this approach is to maximize the system efficiency by finding an optimal planning for a better collaboration among various processes. This makes distributed scheduling problems more complicated than classical production scheduling ones. With the addition of alternative production routing, the problems are even more complicated. Conventionally, machines are usually assumed to be available without interruption during the production scheduling. Maintenance is not considered. However, every machine requires maintenance, and the maintenance policy directly affects the machine's availability. Consequently, it influences the production scheduling. In this connection, maintenance should be considered in distributed scheduling. The objective of this paper is to propose a genetic algorithm with dominant genes (GADG) approach to deal with distributed flexible manufacturing system (FMS) scheduling problems subject to machine maintenance constraint. The optimization performance of the proposed GADG will be compared with other existing approaches, such as simple genetic algorithms to demonstrate its reliability. The significance and benefits of considering maintenance in distributed scheduling will also be demonstrated by simulation runs on a sample problem.     

Earliness–tardiness minimization on a single machine to schedule preventive maintenance tasks: metaheuristic and exact methods

In this paper, we consider the problem of scheduling a set of M preventive maintenance tasks to be performed on M machines. The machines are assigned to execute production tasks. We aim to minimize the total preventive maintenance cost such that the maintenance tasks have to continuously be run during the schedule horizon. Such a constraint holds when the maintenance resources are not sufficient. We solve the problem by two exact methods and meta-heuristic algorithms. As exact procedures we used linear programming and branch and bound methods. As meta-heuristics, we propose a local search approach as well as a genetic algorithm. Computational experiments are performed on randomly generated instances to show that the proposed methods produce appropriate solutions for the problem. The computational results show that the deviation of the meta-heuristics solutions to the optimal one is very small, which confirms the effectiveness of meta-heuristics as new approaches for solving hard scheduling problems.     

Lot-sizing decisions for material requirements planning with hybrid uncertainties in a smart factory

Material requirements planning (MRP) is a kind of medium-term production planning, which aims to plan the end item requirements of the master production schedule over a finite planning horizon. In a smart factory, the customer requirements and the production status are varying in time, which increases the uncertainties in making lot-sizing decisions for MRP. In this study, a hybrid chance-constrained programming (HCCP) model is developed for solving an MRP problem with hybrid uncertainties, in which both randomness and fuzziness exist in a lot-sizing decision process. The objective of the HCCP model is to determine the lot sizes of all items while satisfying the stochastic demands and the fuzzy capacity constraints. The credibility and probability are incorporated into the proposed model to measure the fuzziness and randomness, respectively. In order to solve the model, relevant approaches for converting the probability-based and credibility-based constraints into the equivalent deterministic forms are proposed. Decision makers can set different confidence levels according to their own risk preferences to get different results. Finally, an example is presented to verify that the approach proposed in this paper is feasible for solving MRP problems with hybrid uncertainties.     

A two-stage heuristic for single machine capacitated lot-sizing and scheduling with sequence-dependent setup costs

This paper considers a single machine capacitated lot-sizing and scheduling problem. The problem is to determine the lot sizes and the sequence of lots while satisfying the demand requirements and the machine capacity in each period of a planning horizon. In particular, we consider sequence-dependent setup costs that depend on the type of the lot just completed and on the lot to be processed. The setup state preservation, i.e., the setup state at the end of a period is carried over to the next period, is also considered. The objective is to minimize the sum of setup and inventory holding costs over the planning horizon. Due to the complexity of the problem, we suggest a two-stage heuristic in which an initial solution is obtained and then it is improved using a backward and forward improvement method that incorporates various priority rules to select the items to be moved. Computational tests were done on randomly generated test instances and the results show that the two-stage heuristic outperforms the best existing algorithm significantly. Also, the heuristics with better priority rule combinations were used to solve case instances and much improvement is reported over the conventional method as well as the best existing algorithm.     

An approximate nondominated sorting genetic algorithm to integrate optimization of production scheduling and accurate maintenance based on reliability intervals

With the development of intelligent manufacturing, production scheduling and preventive maintenance are widely applied in industry to enhance production efficiency and machine reliability. Therefore, according to the different processing states and the physical degradation phenomena of the machine, this paper proposes an accurate maintenance (AM) model based on reliability intervals, which have different maintenance activities in diverse intervals and overcome the shortcoming of the single reliability threshold maintenance model used in the past. Combining the flexible job-shop scheduling problem (FJSP), an integrated multiobjective optimization model is established with production scheduling and accurate maintenance. To strengthen the ability of the evolutionary algorithm to solve the presented model/problem, we propose a novel genetic algorithm, named the approximate nondominated sorting genetic algorithm III (ANSGA-III), which is inspired by NSGA-III. To improve the performance of the Pareto dominance principle, the local search, the elite storage for the original algorithm, the approximate dominance principle, the variable neighborhood search, and the elite preservation strategy are proposed. Then, we employ a scheduling example to verify and evaluate the availability of the above three improved operations and the proposed algorithm. Next, we compare ANSGA-III against five recently proposed algorithms, representing the state-of-the-art on similar problems. Finally, we apply ANSGA-III to solve the integrated optimization model, and the results reveal that the machine can maintain higher availability and reliability when compared to other models in our experiments. Consequently, the superiority of the proposed model based on accurate maintenance of reliability intervals is demonstrated, and the optimal reliability threshold between the yellow and red areas is found to be 0.82.     

Maintenance scheduling incorporating dynamics of production system and real-time information from workstations

In this paper, a new approach to maintenance scheduling for a multi-component production system which takes into account the real-time information from workstations including remaining reliability of equipments as well as work-in-process inventories in each workstation is proposed. To model dynamics of the system, other information like production line configuration, cycle times, buffers’ capacity and mean time to repair of machines are also considered. Using factorial experiment design the problem is formulated to comprehensively monitor the effects of each possible schedule on throughput of the production system. The optimal maintenance schedule is searched by genetic algorithm-based optimization engine implemented in a simulation optimization platform. The proposed approach exploits all of makespans of planning horizon to find the best opportunity to perform maintenance actions on degrading machines in a way that maximizes the system throughput and mitigates the production losses caused by imperfect traditional maintenance strategies. Finally the proposed method is tested in a real production line to magnify the accuracy of proposed scheduling method. The experimental results indicate that the proposed approach guarantees the operational productivity and scheduling efficiency as well.     

Integrating simulation and optimization to schedule a hybrid flow shop with maintenance constraints

The scheduling problems have been discussed in the literature extensively under the assumption that machines are continuously available. However, in most real life industrial settings a machine can be unavailable for many reasons, such as unforeseen breakdowns (stochastic unavailability) or due to a scheduled preventive maintenance where the periods of unavailability are known in advance (deterministic unavailability). In this paper, we deal with the hybrid flow shop scheduling problem under maintenance constraints to optimize several objectives based on flow time and due date. In this model, we take also on consideration setup, cleaning and transportation times. This paper has three goals. The first is to show how we can integrate simulation and optimization to tackle this practical problem which is NP-hard on the strong sense. The second is to illustrate by an experimentation study that the performance of heuristics applied to this problem can be affected by the percentage of the breakdown times. The last is to show that this approach can perform better than NEH heuristics under certain conditions.     

Considering scheduling and preventive maintenance in the flowshop sequencing problem

The aim of this paper is to propose tools in order to implicitly consider different preventive maintenance policies on machines regarding flowshop problems. These policies are intended to maximize the availability or to keep a minimum level of reliability during the production horizon. It proposes a simple criterion to schedule preventive maintenance operations to the production sequence. This criterion demonstrates the significance of taking into consideration preventive maintenance together with sequencing and the consequences of not doing so. The optimization criterion considered consists in minimizing the makespan of the sequence or _Cmax$C_{\max }$. In total, six adaptations of existing heuristic and metaheuristic methods are evaluated for the consideration of preventive maintenance and they are applied to a set of 7200 instances. The results and experiments carried out indicate that modern Ant Colony and Genetic Algorithms provide very effective solutions for this problem.     

Scheduling activities at oil wells with resource displacement

Before promising locations at petroliferous basins become productive oil wells, it is necessary to complete development activities at these locations. The scheduling of such activities must satisfy several conflicting constraints and attain a number of goals. Moreover, resource displacements between wells are important and must also be taken into account. The problem is NP‐hard, as can be seen by a simple poly‐time reduction from the Job Shop problem. This paper describes Greedy Randomized Adaptive Search Procedures (GRASPs) for the scheduling of oil well development activities with resource displacement. The heuristics were tested on real instances from a major oil company, recognized for its expertise in offshore oil exploration. Computational experiments over real instances revealed that the GRASP implementations are competitive, outperforming the software currently being used by the company.     

Scheduling two-stage hybrid flow shop with availability constraints

Most of the literature on scheduling assumes that machines are always available. However, in real life industry, machines may be subject to some unavailability periods due to maintenance activities such as breakdowns (stochastic case) and preventive maintenance (deterministic case). In this paper we investigate the two-stage hybrid flow shop scheduling problem with only one machine on the first stage and m machines on the second stage to minimize the makespan. We consider that each machine is subject to at most one unavailability period. The start time and the end time of each period are known in advance (deterministic case) and only the non-resumable case is studied. First we discuss the complexity of the problem. Afterwards, we give the Branch and Bound model for this problem. Last, we calculate the worst-case performances of three heuristics: LIST algorithm, LPT algorithm and H-heuristic.