Optimal leadtimes planning in serial production systems with earliness and tardiness costs

We consider a production system consisting of N processing stages. The actual leadtimes at the stages are stochastic. The objective is to determine the planned leadtimes at each stage so as to minimize the expected total inventory costs, tardiness penalties, and a backlog penalty for not meeting demand due date at the last stage. Recursive relationships are used for automatic generation and efficient computation of the objective function. The efficiency of the proposed algorithms allows us to obtain new insights regarding operating policies, leadtime delivery reliability, and production line design. The problem is formulated as a convex non-linear programming problem. The latter is then solved using classical convex optimization algorithms. For the special case of exponentially distributed leadtimes, the objective function is derived in a closed form.     

Stochastic Leadtimes in Two-Level Assembly Systems

Shortages of assembly parts often arise from late arrivals of one or more batches of components. We address the problem of determining planned leadtimes in two-level assembly systems with stochastic leadtimes, with the objective of minimizing the sum of inventory holding costs and tardiness costs. An algorithm is developed which exploits properties of the objective function to find optimal solutions. Computational results indicate that optimal solutions often have negative safety times for at least one of the components, as well as substantial safety times for the assembly stage.     

Rescheduling parallel machines with stepwise increasing tardiness and machine assignment stability objectives

Nervousness in machine assignments during rescheduling can cause problems for the implementation of a scheduling system. This paper examines rescheduling due to the arrival of new jobs to the system. Parallel machine scheduling problems with stepwise increasing tardiness cost objectives, non-zero machine ready times, constraints that limit machine reassignments, and machine reassignment costs are considered. Simulation experiments and individual scheduling problems indicate that nervousness can be controlled at a low cost in some parallel machine scheduling environments. The rescheduling problems in the simulation are solved with a branch-and-price algorithm. Significant gains in schedule stability can be achieved by selecting the alternative optimal solution with the fewest machine reassignments.     

Production rescheduling for machine breakdown at a job shop

Rescheduling is a procedure to repair a production plan affected by unexpected disruptions. It is important because a production schedule released to a shop floor is subject to unexpected disruptions. This paper develops two novel heuristic rescheduling procedures, AWI-J and AWI-O, to minimise mean tardiness of jobs in a job shop. The procedures are based on an active schedule-generation procedure and Wilkerson–Irwin algorithm, which is well known for minimising mean tardiness of a schedule. The performances of the new procedures are compared with those of the Affected Operations Rescheduling (AOR) procedure, which is popular in the rescheduling literature. Efficiency measures such as mean tardiness, mean flowtime, and makespan, and a stability measure, deviation of new operation start times from the original start times, are used for comparison. Test results show that AWI-J improves efficiency over AOR, and AWI-O improves efficiency and stability as well.     

A comparison of rescheduling policies for online flow shops to minimize tardiness

In practical situations, flow shops usually have some policies on rescheduling previously scheduled jobs. This article compares three of these rescheduling policies: an unrestricted one where previously scheduled jobs can be moved freely, one where jobs can only be moved forward in the schedule, and one where jobs that have already been scheduled cannot be moved at all. The comparison is performed by considering the minimization of tardiness. While unrestricted rescheduling should generally give the best solution, moving jobs only forward can be more practical as in general production, material orders can be delayed but seldom advanced. This article points out that moving jobs only forward is not significantly worse than the unrestricted scheduling. When cases with small numbers of jobs and machines are analysed both policies give similar tardiness. Numerical experiments show that the differences between these two rescheduling policies are rather small in larger problems as well.     

SETTING SAFETY LEADTIMES FOR PURCHASED COMPONENTS IN ASSEMBLY SYSTEMS

We consider the problem of setting appropriate safety leadtimes in an assembly system where all components are purchased and the only manufacturing operation is final assembly. First, we describe two formulations of this problem: (1) minimize total inventory carrying and tardiness costs and (2) minimize inventory carrying costs subject to a service constraint. Second, we discuss how these formulations sometimes fail to adequately provide a decision maker with sufficient information to establish leadtimes when applied independently but how they can be used together to provide a useful decision support system. Finally, we describe a procedure similar to ABC analysis that allows us to solve a much smaller related problem whose solution provides a good approximation to the solution of the original problem. We conclude the paper with numerical examples and a discussion of an actual implementation.     

The choice of dispatching rules in a shop using internally set due-dates with quoted leadtime and tardiness costs

Setting due-dates poses a dilemma for the manufacturing manager. If the duedates extend the quoted leadtimes to ensure delivery reliability, the shop incurs the customer's ire for having such long leadtimes. If they shorten its quoted leadtimes, it faces the prospect of incurring the customer's wrath for poor delivery reliability. This study examines the trade-offs involved in choosing a dispatching rule in a shop that can set due-dates subject to penalties for the length of the quoted leadtime and tardiness. The results of this study indicate that the shortest processing time rule works well for modest tardiness penalties. As the penalty for tardiness increases, dispatching rules such as first-come, first-serve and first-in-system first-serve, work well. The earliest due-date rule generally does not perform well in this study because of the interaction between the earliest duedate rule and the parameters of the due-date assignment rule. The paper concludes with the discussion of possible extensions of this work.     

Minimising earliness and tardiness by integrating production scheduling with shipping information

Minimisation of earliness and tardiness is known to be critical to manufacturing companies because it may induce numerous tangible and intangible problems, i.e. extra storage cost, spacing, risk of damages, penalty, etc. In literature, earliness and tardiness is usually determined based on order due date, generally regarded as the time of delivering the finished products to the customers. In many papers, delivery time and cost required are usually simplified during the production scheduling. They usually assume that transportation is always available and unlimited. However, transportation usually constructs a critical portion of the total lead time and total cost in practice. Ignoring that will lead to an unreliable schedule. This is especially significant for electronic household appliances manufacturing companies as the studied company in this paper. In general, they usually rely on sea-freight transportation because of the economic reasons. As different sea-freight forwarders have different shipments to the same destination but with different shipping lead time, cost and available time. Adequately considering this shipping information with the production scheduling as an integrated model can minimise the costs induced by earliness and tardiness and the reliability of the schedule planned. In this paper, a two-level genetic algorithm (TLGA) is proposed, which is capable of simultaneously determining production schedule with shipping information. The optimisation reliability of the proposed TLGA is tested by comparing with a simple genetic algorithm. The results indicated that the proposed TLGA can obtain a better solution with lesser number of evolutions. In addition, a number of numerical experiments are carried out. The results demonstrate that the proposed integrated approach can reduce the tardiness, the storage cost, and shipping cost.     

Dynamic response to demand variability for precast production rescheduling with multiple lines

Production scheduling plays a crucial role in the prefabricated construction productivity and on-time delivery of precast components (PCs). However, previous studies mainly focused on the static scheduling of single production line without considering the demand variability in practice. To achieve dynamic production planning, a Two-level Rescheduling Model for Precast Production with multiple production lines is developed to minimise the rescheduling costs based on genetic algorithm, from the two levels of (1) selection of production line and (2) rescheduling of jobs based on PCs’ priority. Further, two scenarios of different and shared mould types are investigated to represent real-world production environments. Finally, a real case study is conducted to test the validity of proposed rescheduling model. 58.1 and 48.5% cost savings are achieved by comparison to no response to changes and heuristic rescheduling methods, respectively. This research contributes to the precast production theory by expanding the insight into dynamic rescheduling with multiple production lines. The methodology will promote the on-time delivery of PCs and enhance the dynamic precast production management.     

Analytical models to predict the performance of a single-machine system under periodic and event-driven rescheduling strategies

This article presents initial results in the search for analytical models that can predict the performance of one-machine systems under periodic and event-driven rescheduling strategies in an environment where different job types arrive dynamically for processing and set-up must incur when production changes from one product type to another. The scheduling algorithm considered uses a first-in firstout dispatching rule to sequence jobs and it also groups jobs with similar types to save set-up time. The analytical models can estimate important performance measures like average flow time and machine utilization, which can then be used to determine optimal rescheduling parameters. Simulation experiments are used to show that the analytical models accurately predict the performance of the single machine under the scheduling algorithm proposed.     

MRP performance effects due to lot size and planned lead time settings

The effects of lot size and planned lead time settings are evaluated in a shop producing assembled products with common components. Material requirements planning (MRP) logic is used for production planning. A framework for the analysis of delays within the production system is presented. These delays are evaluated using spreadsheet-based MRP software linked to a simulation package that emulates shopfloor activity. Results show that by selecting the proper lot sizes and then using the planned leadtimes to control delivery performance, the required inventory levels can be minimized.     

Discrete harmony search algorithm for scheduling and rescheduling the reprocessing problems in remanufacturing: a case study

In this article, scheduling and rescheduling problems with increasing processing time and new job insertion are studied for reprocessing problems in the remanufacturing process. To handle the unpredictability of reprocessing time, an experience-based strategy is used. Rescheduling strategies are applied for considering the effect of increasing reprocessing time and the new subassembly insertion. To optimize the scheduling and rescheduling objective, a discrete harmony search (DHS) algorithm is proposed. To speed up the convergence rate, a local search method is designed. The DHS is applied to two real-life cases for minimizing the maximum completion time and the mean of earliness and tardiness (E/T). These two objectives are also considered together as a bi-objective problem. Computational optimization results and comparisons show that the proposed DHS is able to solve the scheduling and rescheduling problems effectively and productively. Using the proposed approach, satisfactory optimization results can be achieved for scheduling and rescheduling on a real-life shop floor.     

Capacity requirements planning—optimal work station capacities

The How of work through a work station is analysed in terms of planned input from previous stations, planned output to subsequent stations, planned work-in-process waiting for processing and the planned queue of unprocessed work delayed for processing during sonic subsequent period. The planner is assumed to have some leeway in determining the maximum throughput during each period7mdash; the planned capacity—and is thus interested in determining the optimal capacity, to be maintained at some constant value throughout the planning horizon. This paper presents a methodology for finding the optimal planned capacity of a work station, which minimizes total costs over the planning horizon. These costs are of three types: costs of establishing and maintaining the capacity level; costs of work processing; and costs of hoi ding up work in the queue owing to insufficient capacity at any period.

Various constraints are considered when characterizing the operating environment of the work station: minimum and maximum permissible queue lengths, delays, work-in-process amounts, lead times, underloading and backlogging. It is shown that these restrictions may be transformed into minimum and maximum bounds on allowable capacity levels, so that the problem becomes one of constrained optimization in a single decision variable—the planned capacity. For complex cost functions or when underloading is permissible, complete enumeration of all feasible solutions provides the simplest approach. For linear or quadratic cost functions and no underloading, the shape and smoothness of the total cost curve indicates that set of feasible capacities within which the optimal capacity lies.     

Single operation earliness–tardiness scheduling with machine activation costs

We consider a static, single operation, non-pre-emptive, deterministic scheduling problem in which a set of n jobs is to be processed on k identical machines. Jobs assigned to each machine have a common due date. The number of machines (k) is unknown. Activating a machine will require additional costs to be incurred. The objective is to find an optimal sequence, the optimal number of machines (k), and the respective due dates to minimize the weighted sum of earliness, tardiness, and machine activation costs. We propose a polynomial time algorithm to solve the problem.     

A dispatching rule and a random iterated greedy metaheuristic for identical parallel machine scheduling to minimize total tardiness

This paper addresses a real-life production scheduling problem with identical parallel machines, originating from a plant producing Acrylonitrile-Butadiene-Styrene (ABS) plate products. In the considered practical scheduling problem, ABS plate has some specific specifications and each specification has several different levels. Because there is at least one different level of specification between two ABS plate products, it is necessary to make a set-up adjustment on each machine whenever a switch occurs from processing one ABS plate product to another product. As tardiness leads to extra penalty costs and opportunity losses, the objective of minimising total tardiness has become one of the most important tasks for the schedule manager in the plant. The problem can be classified as an identical parallel machine scheduling problem to minimise the total tardiness. A dispatching rule is proposed for this problem and evaluated by comparing it with the current scheduling method and several existing approaches. Moreover, an iterated greedy-based metaheuristic is developed to further improve the initial solution. The experimental results show that the proposed metaheuristic can perform better than an existing tabu search algorithm, and obtain the optimal solution for small-sized problems and significantly improve the initial solutions for large-sized problems.     

Solving comprehensive dynamic job shop scheduling problem by using a GRASP-based approach

There are many dynamic events like new order arrivals, machine breakdowns, changes in due dates, order cancellations, arrival of urgent orders etc. that makes static scheduling approaches very difficult. A dynamic scheduling strategy should be adopted under such production circumstances. In the present study an event driven dynamic job shop scheduling mechanism under machine capacity constraints is proposed. The proposed method makes use of the greedy randomised adaptive search procedure (GRASP) by also taking into account orders due dates and sequence-dependent set-up times. Moreover, order acceptance/rejection decision and Order Review Release mechanism are integrated with scheduling decision in order to meet customer due date requirements while attempting to execute capacity adjustments. We employed a goal programming-based logic which is used to evaluate four objectives: mean tardiness, schedule unstability, makespan and mean flow time. Benchmark problems including number of orders, number of machines and different dynamic events are generated. In addition to event-driven rescheduling strategy, a periodic rescheduling strategy is also devised and both strategies are compared for different problems. Experimental studies are performed to evaluate effectiveness of the proposed method. Obtained results have proved that the proposed method is a feasible approach for rescheduling problems under dynamic environments.     

Setting planned job release times in stochastic assembly systems with resource constraints

This paper considers a stochastic assembly system operating on a make-to-order basis with complex product structure and resource constraints. The problem is to find the optimal planned job release times by minimizing the expected sum of the work-in-progress holding cost, product earliness cost and product tardiness cost. A perturbation analysis algorithm is developed to derive the gradient estimate of the cost function with respect to the job release times. This gradient estimate is shown to be unbiased and may lead to the optimal solution by using a stochastic approximation method. Moreover, a procedure is presented to adjust planned job release times to meet service level constraint for each individual job. Numerical examples, which use manufacturing and assembly data from a capital goods company, are given to demonstrate the results.     

Extending capacity planning by positive lead times and optional overtime,earliness and tardiness for effective master production scheduling

In this paper we consider the problem of improving the Master Production Schedule (MPS) in make-to-order production systems when demand exceeds available resource capacity. Due to the complexity of the problem, in practice solutions are usually obtained manually. We propose an algorithm that offsets production orders guided by tardiness, earliness and overtime penalties. The intermediate tool used to determine resource utilization is Rough Cut Capacity Planning (RCCP) extended by positive lead times and options for overtime, earliness and tardiness. This approach leads to a more realistic resource loading calculation, similar to CRP but without its computational burden. The discrete optimization model is solved by a Genetic Algorithm (GA); within the GA, delays or early deliveries of each order are represented as genes of a chromosome. The method is tested against systematically developed benchmark problems and real industrial data. Improvements over the traditional RCCP procedure and an ERP's embedded routines are demonstrated by the computational results and support the applicability of the proposed approach for real-life make-to-order environments.     

Flow shop rescheduling under different types of disruption

Almost all manufacturing facilities need to use production planning and scheduling systems to increase productivity and to reduce production costs. Real-life production operations are subject to a large number of unexpected disruptions that may invalidate the original schedules. In these cases, rescheduling is essential to minimise the impact on the performance of the system. In this work we consider flow shop layouts that have seldom been studied in the rescheduling literature. We generate and employ three types of disruption that interrupt the original schedules simultaneously. We develop rescheduling algorithms to finally accomplish the twofold objective of establishing a standard framework on the one hand, and proposing rescheduling methods that seek a good trade-off between schedule quality and stability on the other.     

Predictable scheduling of a single machine with breakdowns and sensitive jobs

Production schedules released to the shop floor have two important functions: allocating shop resources to different jobs to optimize some measure of shop performance and serving as a basis for planning external activities such as material procurement, preventive maintenance and delivery of orders to customers. Schedule modification may delay or render infeasible the execution of external activities planned on the basis of the predictive schedule. Thus it is of interest to develop predictive schedules that can absorb disruptions without affecting planned external activities while maintaining high shop performance. We present a predictable scheduling approach, that inserts additional idle time into the schedule to absorb the impacts of breakdowns. The effects of disruptions on planned support activities are measured by the deviations of job completion times in the realized schedule from those in the predictive schedule. We apply our approach to minimizing total tardiness on a single machine with stochastic machine failures. We then extend the procedure to consider the case where job processing times are affected by machine breakdowns, and provide specialized rescheduling heuristics. Extensive computational experiments show that this approach provides high predictability with minor sacrifices in shop performance.