A GRASP for simultaneously assigning and sequencing product families on flexible assembly lines

This paper introduces a new model and solution methodology for a real-world production scheduling problem arising in the electronics industry. The production environment is a high volume, just-in-time, make-to-order facility with volatile demand over many product families that are assembled on flexible lines. A distinguishing characteristic of the problem is the presence of non-traditional sequence-dependant setup costs, which complicate our ability to find high-quality solutions. The scheduling problem arose when product variety exceeded the mix that the existing lines could accommodate. A nonlinear integer programming formulation is presented for the problem of minimizing setup costs, and a greedy randomized adaptive search procedure (GRASP) is developed to find solutions. To select the GRASP parameter values, an efficient, space-filling experimental design method is used based on nearly orthogonal Latin hypercubes. The proposed methodology is tested on actual factory data and compared to a prior heuristic presented in the literature; our heuristic provides a cost savings in 7 out of the 10 cases examined, and an average improvement of 17.39 % which is shown to be highly statistically significant. This improvement is due in part to the introduction of a pre-processing step to determine preferential and non-preferential line assignment information.     

A search heuristic for the sequence-dependent economic lot scheduling problem

Almost all of the research on the economic lot scheduling problem (ELSP) has assumed that setup times are sequence-independent even though sequence-dependent problems are common in practice. Furthermore, most of the solution approaches that have been developed solve for a single optimal schedule when in practice it is more important to provide managers with a range of schedules of different length and complexity. In this paper, we develop a heuristic procedure to solve the ELSP problem with sequence-dependent setups. The heuristic provides a range of solutions from which a manager can choose, which should prove useful in an actual stochastic production environment. We show that our heuristic can outperform Dobson's heuristic when the utilization is high and the sequence-dependent setup times and costs are significant.     

Algorithms for single machine total tardiness scheduling with sequence dependent setups

We consider the problem of scheduling a single machine to minimize total tardiness with sequence dependent setup times. We present two algorithms, a problem space-based local search heuristic and a Greedy Randomized Adaptive Search Procedure (GRASP) for this problem. With respect to GRASP, our main contributions are—a new cost function in the construction phase, a new variation of Variable Neighborhood Search in the improvement phase, and Path Relinking using three different search neighborhoods. The problem space-based local search heuristic incorporates local search with respect to both the problem space and the solution space. We compare our algorithms with Simulated Annealing, Genetic Search, Pairwise Interchange, Branch and Bound and Ant Colony Search on a set of test problems from literature, showing that the algorithms perform very competitively.     

Heuristics for the flow line problem with setup costs

This paper presents two new heuristics for the flowshop scheduling problem with sequence-dependent setup times (SDSTs) and makespan minimization objective. The first is an extension of a procedure that has been very successful for the general flowshop scheduling problem. The other is a greedy randomized adaptive search procedure (GRASP) which is a technique that has achieved good results on a variety of combinatorial optimization problems. Both heuristics are compared to a previously proposed algorithm based on the traveling salesman problem (TSP). In addition, local search procedures are developed and adapted to each of the heuristics. A two-phase lower bounding scheme is presented as well. The first phase finds a lower bound based on the assignment relaxation for the asymmetric TSP. In phase two, attempts are made to improve the bound by inserting idle time. All procedures are compared for two different classes of randomly generated instances. In the first case where setup times are an order of magnitude smaller than the processing times, the new approaches prove superior to the TSP-based heuristic; for the case where both processing and setup times are identically distributed, the TSP-based heuristic outperforms the proposed procedures.     

Greedy Randomized Adaptive Search Procedures

Today, a variety of heuristic approaches are available to the operations research practitioner. One methodology that has a strong intuitive appeal, a prominent empirical track record, and is trivial to efficiently implement on parallel processors is GRASP (Greedy Randomized Adaptive Search Procedures). GRASP is an iterative randomized sampling technique in which each iteration provides a solution to the problem at hand. The incumbent solution over all GRASP iterations is kept as the final result. There are two phases within each GRASP iteration: the first intelligently constructs an initial solution via an adaptive randomized greedy function; the second applies a local search procedure to the constructed solution in hope of finding an improvement. In this paper, we define the various components comprising a GRASP and demonstrate, step by step, how to develop such heuristics for combinatorial optimization problems. Intuitive justifications for the observed empirical behavior of the methodology are discussed. The paper concludes with a brief literature review of GRASP implementations and mentions two industrial applications.     

Minimizing total tardiness in parallel machine scheduling with setup times: An adaptive memory-based GRASP approach

This paper deals with the problem of scheduling jobs in uniform parallel machines with sequence-dependent setup times in order to minimize the total tardiness relative to job due dates. We propose GRASP versions that incorporate adaptive memory principles for solving this problem. Long-term memory is used in the construction of an initial solution and in a post-optimization procedure which connects high quality local optima by means of path relinking. Computational tests are carried out on a set of benchmark instances and the proposed GRASP versions are compared with heuristic methods from the literature.     

Grasp with memory-based mechanisms for minimizing total tardiness in single machine scheduling with setup times

This paper addresses the problem of scheduling jobs in a single machine with sequence dependent setup times in order to minimize the total tardiness with respect to job due dates. We propose variants of the GRASP metaheuristic that incorporate memory-based mechanisms for solving this problem. There are two mechanisms proposed in the literature that utilize a long-term memory composed of an elite set of high quality and sufficiently distant solutions. The first mechanism consists of extracting attributes from the elite solutions in order to influence the construction of an initial solution. The second one makes use of path relinking to connect a GRASP local minimum with a solution of the elite set, and also to connect solutions from the elite set. Reactive GRASP, which probabilistically determines the degree of randomness in the GRASP construction throughout the iterations, is also investigated. Computational tests for instances involving up to 150 jobs are reported, and the proposed method is compared with heuristic and exact methods from the literature.     

GRASP and path relinking for project scheduling under partially renewable resources

Recently, in the field of project scheduling problems the concept of partially renewable resources has been introduced. Theoretically, it is a generalization of both renewable and non-renewable resources. From an applied point of view, partially renewable resources allow us to model a large variety of situations that do not fit into classical models, but can be found in real problems in timetabling and labor scheduling. In this paper, we develop some preprocessing techniques and several heuristic algorithms for the problem. Preprocessing significantly reduces the dimension of the problems, therefore improving the efficiency of solution procedures. Heuristic algorithms based on GRASP and Path relinking are then developed and tested on existing test instances, obtaining excellent results.     

The two-group heuristic to solve the multi-product,economic lot sizing and scheduling problem in flow shops

This paper presents a new and efficient heuristic to solve the multi-product, economic lot sizing and scheduling problem in flow shops. The problem addressed is that of making sequencing, lot sizing and scheduling decisions for a number of products so as to minimize the sum of setup costs, work-in-process inventory holding costs and final-products inventory holding costs while a given demand is fulfilled without backlogging. The proposed heuristic, called the two-group method (TG), assumes that the cycle time of each product is an integer multiple of a basic period and restricts these multiples to take either the value 1 or K where K is a positive integer. The products to be produced once each K basic period are then partitioned into K sub-groups and each sub-group is assigned to one and only one of the K basic periods of the global cycle. This method first determines a value for K and a feasible partition. Then, a production sequence is determined for each sub-group of products and a non-linear program is solved to determine lot sizes and a feasible schedule. We also show how to adapt our method to the case of batch streaming (transportation of sub-batches from one machine to the next). To evaluate its performance, the TG method was compared to both the common cycle method and a reinforced version of El-Najdawi’s job-splitting heuristic. Numerical results show that the TG method outperforms both of these methods.     

Dynamic repositioning for vehicle sharing with setup costs

This study considers a multi-period two-region repositioning problem with setup repositioning costs involved for vehicle sharing systems. We find that incorporating such costs can influence the total cost significantly and complicate the structure of the optimal policy. Moreover, we manage to partially characterize the optimal policy, and then develop an easy-to-implement heuristic policy. The performance of the heuristic policy and the influence of setup repositioning costs on policies are assessed numerically.     

A GRASP heuristic for the manufacturing cell formation problem

In this work, we address the Manufacturing Cell Formation Problem (MCFP). Cellular Manufacturing is a production strategy that has emerged to reduce materials handling and set up times in order to reduce lead times in production systems and to improve customer??s service levels while reducing costs. We propose a GRASP heuristic to obtain lower bounds for the optimal solution of the problem. To evaluate the performance of the proposed method, we test the heuristic with different instances from the literature and compare the results obtained with those provided by other heuristic methods from the literature. According to the obtained results, the proposed GRASP procedure provides good quality lower bounds with reasonable computational effort.     

Dynamic scheduling to minimize lost sales subject to set-up costs

We consider scheduling a shared server in a two-class, make-to-stock, closed queueing network. We include server switching costs and lost sales costs (equivalently, server starvation penalties) for lost jobs. If the switching costs are zero, the optimal policy has a monotonic threshold type of switching curve provided that the service times are identical. For completely symmetric systems without set-ups, it is optimal to serve the longer queue. Using simple analytical models as approximations, we derive a heuristic scheduling policy. Numerical results demonstrate the effectiveness of our heuristic, which is typically within 10% of optimal. We also develop and test a heuristic policy for a model in which the shared resource is part of a series network under a CONWIP release policy. This revised version was published online in June 2006 with corrections to the Cover Date.     

Carryover sequence-dependent group scheduling with the integration of internal and external setup times

This paper addresses a group scheduling problem in a two-machine flow shop with a bicriteria objective and carryover sequence-dependent setup times. This special type of group scheduling problem typically arises in the assembly of printed circuit boards (PCBs). The objective is to sequence all board types in a board group as well as board groups themselves in a way that the objective function is minimized. We introduce the carryover sequence-dependent setup on machines, and call it internal setup. As an opportunity for manufacturers to decrease the costs, the focus is to completely eliminate the role of the kitting staff. Thus, we introduce the external setup (kitting) time for the next board group and require it to be performed by the machine operator during the time he is idle. Consequently, the internal and external setup times are integrated in this research, and to the best of our knowledge it is for the first time a research on PCB group scheduling is performed by integrating both setups. In order to solve this problem, first a mathematical model is developed. Then a heuristic together with two other meta-heuristic algorithms (one based on tabu search and the other based on genetic algorithm) are proposed and their efficiency and effectiveness on several problems are tested. Also a statistical experimental design is performed in order to evaluate the impact of different factors on the performance of the algorithms.     

Economic lot sizes and vehicle scheduling

In this paper a relationship between the vehicle scheduling problem and the dynamic lot size problem is considered. For the latter problem we assume that order quantities for different products can be determined separately. Demand is known over our n-period production planning horizon. For a certain product our task is to decide for each period if it should be produced or not. If it is produced, what is its economic lot size? Our aim here is to minimize the combined set-up and inventory holding costs. The optimal solution of this problem is given by the well-known Wagner-Whitin dynamic lot size algorithm. Also many heuristics for solving this problem have been presented. In this article we point out the analogy of the dynamic lot size problem to a certain vehicle scheduling problem. For solving vehicle scheduling problems the heuristic algorithm developed by Clark and Wright in very often used. Applying this algorithm to the equivalent vehicle scheduling problem we obtain by analogy a simple heuristic algorithm for the dynamic lot size problem. Numerical results indicate that computation time is reduced by about 50% compared to the Wagner-Whitin algorithm. The average cost appears to be approximately 0.8% higher than optimum.     

Complexities and algorithms for synchronized scheduling of parallel machine assembly and air transportation in consumer electronics supply chain

In this paper, we study the problem of synchronized scheduling of assembly and air transportation to achieve accurate delivery with minimized cost in consumer electronics supply chain. This problem was motivated by a major PC manufacturer in consumer electronics industry. The overall problem is decomposed into two sub-problems, which consist of an air transportation allocation problem and an assembly scheduling problem. The air transportation allocation problem is formulated as an integer linear programming problem with the objective of minimizing transportation cost and delivery earliness tardiness penalties. The assembly scheduling problem seeks to determine a schedule ensuring that the orders are completed on time and catch the flights such that the waiting penalties between assembly and transportation is minimized. The problem is formulated as a parallel machine scheduling problem with earliness penalties. The computational complexities of the two sub-problems are investigated. The air transportation allocation problem with split delivery is shown to be solvable. The parallel machine assembly scheduling problem is shown to be NP-complete. Simulated annealing based heuristic algorithms are presented to solve the parallel machine problem.     

Upper and lower bounding procedures for the minimum caterpillar spanning problem

A spanning caterpillar in a graph is a tree composed by a path such that all vertices not in the path are leaves. In the Minimum Spanning Caterpillar Problem (MSCP) each edge has two costs: a path cost when it belongs to the path and a connection cost when it is incident to a leaf. The goal is to find a spanning caterpillar minimizing the sum of all path and connection costs. In this paper we formulate the as a minimum Steiner arborescence problem. This reduction is the basis for the development of an efficient branch-and-cut algorithm for the MSCP. We als developed a GRASP heuristic to generate primal bounds. Experiments carried out on instances adapted from TSPLIB 2.1 revealed that the exact algorithm is capable to solve to optimality instances with up to 300 vertices in reasonable time. They also showed that our heuristic yields very high quality solutions.     

Scheduling parallel machines with single vehicle delivery

We investigate the integrated production and distribution scheduling problem in a supply chain. The manufacturer’s production environment is modeled as a parallel machine system. A single capacitated vehicle is employed to deliver products in batches to multiple customers. The scheduling problem can also be viewed as either parallel machines with delivery considerations or a flexible flowshop. Different inventory holding costs, job sizes (volume or storage space required in the transportation unit), and job priorities are taken into account. Efficient mathematical modeling and near-optimal heuristic approaches are presented for minimizing total weighted completion time.     

A coupling cutting stock-lot sizing problem in the paper industry

An important production programming problem arises in paper industries coupling multiple machine scheduling with cutting stocks. Concerning machine scheduling: how can the production of the quantity of large rolls of paper of different types be determined. These rolls are cut to meet demand of items. Scheduling that minimizes setups and production costs may produce rolls which may increase waste in the cutting process. On the other hand, the best number of rolls in the point of view of minimizing waste may lead to high setup costs. In this paper, coupled modeling and heuristic methods are proposed. Computational experiments are presented.     

Multiple machine continuous setup lotsizing with sequence-dependent setups

We address the short-term production planning and scheduling problem coming from the glass container industry. A furnace melts the glass that is distributed to a set of parallel molding machines. Both furnace and machine idleness are not allowed. The resulting multi-machine multi-item continuous setup lotsizing problem with a common resource has sequence-dependent setup times and costs. Production losses are penalized in the objective function since we deal with a capital intensive industry. We present two mixed integer programming formulations for this problem, which are reduced to a network flow type problem. The two formulations are improved by adding valid inequalities that lead to good lower bounds. We rely on a Lagrangian decomposition based heuristic for generating good feasible solutions. We report computational experiments for randomly generated instances and for real-life data on the aforementioned problem, as well as on a discrete lotsizing and scheduling version.     

A Lagrangian relaxation approach to the mixed-product assembly line sequencing problem: A case study of a door-lock company in Taiwan

In mixed-product assembly line sequencing, the production resources required for the assembly lines should be scheduled to minimize the overall cost and meet customer demand. In this paper, we study an assembly line sequencing problem for the door-lock industry in Taiwan and develop an integer programming formulation with realistic constraints. The complex solution space makes the resulting program difficult to solve using commercial optimization packages. Therefore, a heuristic based on the Lagrangian relaxation principle is developed to solve this problem efficiently. We evaluate the efficiency of the developed Lagrangian relaxation heuristic by comparing its solutions with those obtained using a commercial optimization package: the computational results show that the developed heuristic solves the real-world problem faster than the optimization package by almost 15 times in CPU time at a comparable solution quality.