Car sequencing versus mixed-model sequencing: A computational study

The paper deals with the two most important mathematical models for sequencing products on a mixed-model assembly line in order to minimize work overload the mixed-model sequencing (MMS) model and the car sequencing (CS) model. Although both models follow the same underlying objective, only MMS directly addresses the work overload in its objective function. CS instead applies a surrogate objective using so-called sequencing rules which restrict labor-intensive options accompanied with the products in the sequence. The CS model minimizes the number of violations of the respective sequencing rules, which is widely assumed to lead to minimum work overload. This paper experimentally compares CS with MMS in order to quantify the gap in the solution quality between both models. The paper studies several variants of CS with different sequencing rule generation approaches and different objective functions from the literature as well as a newly introduced weighting factor. The performance of the different models is evaluated on a variety of random test instances. Although the objectives of CS and MMS are positively linearly correlated, results show that a sequence found by CS leads to at least 15% more work overload than a solution found by MMS. For none of the considered test instances and for none of the three different objective functions, CS is able to produce competitive results in terms of solution quality (work overload) compared to MMS. The results suggest that decision makers using CS should investigate whether MMS would lead to better sequencing orders for their specific instances.     

Solving the car sequencing problem via Branch & Bound

In a mixed-model assembly line, varying models of the same basic product are to be produced in a facultative sequence. This results to a short-term planning problem where a sequence of models is sought which minimizes station overloads. In practice – e.g. the final assembly of cars – special sequencing rules are enforced which restrict the number of models possessing a certain optional feature k to r_k within a subsequence of s_k successive models. This problem is known as car sequencing. So far, employed solution techniques stem mainly from the field of Logic and Constraint Logic Programming. In this work, a special Branch & Bound algorithm is developed, which exploits the problem structure in order to reduce combinatorial complexity.     

Optimization framework for process scheduling of operation-dependent automobile assembly lines

Productivity, cost, and completion time are regarded as performance measures for assembly production management. The traditional decomposition of Assembly Line Balancing (ALB) and Car sequencing (CS) does not work well, especially when operations belonging to different car types are sequence-dependent and time overlap between two successive workstations is allowed. In this paper, we first use a motivating industrial-scale example to demonstrate that the traditional ALB/CS decomposition method could not satisfy modern continuous production demands in a flexible assembly line. Then, we present a new optimization objective to scale the Operation Process Precision (OPP) that relates to the operation assignment sequence. Lastly, we propose a two-stage hierarchical optimization framework to solve the CS, the operation allocation, and the operation sequence problems. This framework consists of (a) a new Mixed Integer Linear Programming (MILP) model for sequencing automobiles and allocating their operations to each station, and (b) a novel MILP model for determining the operation sequence and timing of each car type. The motivating industrial case is revisited with the proposed framework to illustrate its validity and efficiency.     

A scatter search based hyper-heuristic for sequencing a mixed-model assembly line

We address a mixed-model assembly-line sequencing problem with work overload minimization criteria. We consider time windows in work stations of the assembly line (closed stations) and different versions of a product to be assembled in the line, which require different processing time according to the work required in each work station. In a paced assembly line, products are feeded in the line at a predetermined constant rate (cycle time). Then, if many products with processing time greater than cycle time are feeded consecutively, work overload can be produced when the worker has insufficient time to finish his/her job. We propose a scatter search based hyper-heuristic for this NP-hard problem. In the low-level, the procedure makes use of priority rules through a constructive procedure. Computational experiments over a wide range of instances from the literature show the effectiveness of the proposed hyper-heuristics when compared to existing heuristics. The relevance of the priority rules was evaluated as well.     

A hybrid heuristic for a multi-objective real-life car sequencing problem with painting and assembly line constraints

We address a multi-objective version of the car sequencing problem, which consists in sequencing a given set of cars to be produced in a single day, minimizing the number of violations of assembly constraints and the number of paint color changes in the production line. We propose a set of heuristics for approximately solving this problem, based on the paradigms of the VNS and ILS metaheuristics, to which further intensification and diversification strategies have been added. Computational results on real-life test instances are reported. The work presented in this paper obtained the second prize in the ROADEF challenge 2005 sponsored by Renault.     

Car sequencing is NP-hard: a short proof

In this note, a new proof is given that the car sequencing (CS) problem is NP-hard. Established from the Hamiltonian Path problem, the reduction is direct while closing some gaps remaining in the previous NP-hardness results. Since CS is studied in many operational research courses, this result and its proof are particularly interesting for teaching purposes.     

Iterated tabu search for the car sequencing problem

This paper introduces an iterated tabu search heuristic for the daily car sequencing problem in which a set of cars must be sequenced so as to satisfy requirements from the paint shop and the assembly line. The iterated tabu search heuristic combines a classical tabu search with perturbation operators that help escape from local optima. The resulting heuristic is flexible, easy to implement, and fast. It has produced very good results on a set of test instances provided by the French car manufacturer Renault.     

Review and comparison of three methods for the solution of the car sequencing problem

The car sequencing problem is the ordering of the production of a list of vehicles which are of the same type, but which may have options or variations that require higher work content and longer operation times for at least one assembly workstation. A feasible production sequence is one that does not schedule vehicles with options in such a way that one or more workstations are overloaded. In variations of the problem, other constraints may apply. We describe and compare three approaches to the modeling and solution of this problem. The first uses integer programming to model and solve the problem. The second approaches the question as a constraint satisfaction problem (CSP). The third method proposes an adaptation of the Ant Colony Optimization for the car sequencing problem. Test-problems are drawn from CSPLib, a publicly available set of problems available through the Internet. We quote results drawn both from our own work and from other research. The literature review is not intended to be exhaustive but we have sought to include representative examples and the more recent work. Our conclusions bear on likely research avenues for the solution of problems of practical size and complexity. A new set of larger benchmark problems was generated and solved. These problems are available to other researchers who may wish to solve them using their own methods.     

Algorithms for Toyota's goal of sequencing mixed models on an assembly line with multiple workstations

Toyota's goal of sequencing mixed models on an assembly line is to keep the constant usage rate of every part used in the assembly line. This paper deals with Toyota's goal of sequencing mixed models on an assembly line with multiple workstations. A sequencing problem with Toyota's goal is formulated. Two algorithms based on different mechanisms, respectively modified goal chasing and simulated annealing, are developed for solving the sequencing problem. A number of numerical experiments are carried out for evaluating the efficiency of the algorithms. Computational results show that one of the algorithms generates good sub-optimal solutions with very short CPU times, while the other can reach optimal solutions with longer, but acceptable, CPU times.     

Job sequencing rules for minimizing the expected makespan in flexible machines

We consider scheduling of a deteriorating flexible machine that is capable of processing a number of diverse jobs with negligible setup times between jobs. Specifically, we develop rules for sequencing N jobs on such a machine such that its expected makespan (sum of all job processing times and machine down-time) is minimized. Using the Weibull distribution to characterize machine failures in our model, we permit different jobs to contribute to machine deterioration (and hence its failure) at different failure rates, and do not require these rates to remain constant with machine-use time. We validate the effectiveness of these job sequencing rules for different cases, using extensive simulation tests.     

On games corresponding to sequencing situations with ready times

This paper considers the special class of cooperative sequencing games that arise from one-machine sequencing situations in which all jobs have equal processing times and the ready time of each job is a multiple of the processing time.By establishing relations between optimal orders of subcoalitions, it is shown that each sequencing game within this class is convex.This author is financially supported by the Dutch Organization for Scientific Research (NWO).     

Multi-Skilled Workforce Optimisation

This paper describes a problem faced by CS Energy's Swanbank Power Station in the Australian state of Queensland. It involved the personnel scheduling (rostering) of staff with multiple skill levels at the power station. Such a problem can be classified using the six stage construction process proposed by Ernst et al. We assume that the three processes of ‘demand modelling,’ ‘shift starting times’ and ‘task scheduling’ are specified. We are concerned with the essential processes of ‘day off scheduling,’ ‘line of work construction’ and ‘shift assignment to staff’ with requirements to maintain multiple skills. Several other authors have reported results for staff with hierarchical skills while the methods proposed in this paper are for non-hierarchical skill sets. The paper describes a set covering approach to the multi-skilled rostering problem. We propose a number of solution strategies for the set covering approach and give a comparison of the results.     

Job selection and sequencing on a single machine in a random environment

We examine a single machine scheduling problem with random processing times and deadline. Given a set of independent jobs having specified initiation costs and terminal revenues, the objective is to select a subset of the jobs and sequence the selected jobs such that the expected profit is maximized. The job selection aspect considered by us marks a clear departure from the pure sequencing focus found in the traditional scheduling literature. In this paper, we assume an exponentially distributed deadline and do not allow preemption. Even under these conditions, the selection and sequencing problem remains quite difficult (unlike its pure sequencing counterpart); we in fact conjecture that the problem is NP-hard. However, we show that the problem can be efficiently solved as long as the cost parameter is agreeable or an approximate solution is acceptable. To this end, we describe several solution properties, present dynamic programming algorithms (one of which exhibits a pseudo-polynomial time worst-case complexity), and propose a fully-polynomial time approximation scheme. In addition, we study a number of special cases which can be solved in polynomial time. Finally, we summarize our work and discuss an extension where the jobs are precedence related.     

Traditional heuristic versus Hopfield neural network approaches to a car sequencing problem

This paper considers the problem of optimally sequencing different car models along an assembly line according to some contiguity constraints, while ensuring that the demands for each of the models are satisfied. This car sequencing problem (CSP) is a practical NP-hard combinatorial optimisation problem. The CSP is formulated as a nonlinear integer programming problem and it is shown that exact solutions to the problem are difficult to obtain due to the indefinite quadratic form of the CSP objective function. Two traditional heuristics (steepest descent and simulated annealing) are employed to solve the CSP approximately. Several Hopfield neural network (HNN) approaches are also presented. The process of mapping an optimisation problem onto a HNN is demonstrated explicitly, and modifications to the existing neural approaches are presented which guarantee feasibility of solutions. Further modifications are proposed to improve the solution quality by permitting escape from local minima in an attempt to locate the global optimum. Results from all solutions techniques are compared on a set of instances of the CSP, and conclusions drawn.     

An efficient implementation of a VNS/ILS heuristic for a real-life car sequencing problem

The car sequencing problem consists in sequencing a given set of cars to be produced in a single day. We address one of the variants of this problem, in which the objective of minimizing the number of violations of assembly constraints has a stronger weight than the minimization of the number of paint color changes. We present and describe in details a VNS/ILS approach for approximately solving this problem. Computational results on real-life test instances are reported. The work presented in this paper obtained the second prize in the challenge ROADEF’2005 sponsored by Renault.     

Generate gene expression profile from high-throughput sequencing data

This work presents two methods, the Least-square and Bayesian method, to solve the multiple mapping problem in extracting gene expression profiles through the next-generation sequencing. We parallel the tag sequences to genome, and partition them to improving the methods’ efficiency. The essential feature of these methods is that they can solve the multiple mapping problem between genes and short-reads, while generating almost the same estimation in single-mapping situation as the traditional approaches. These two methods are compared by simulation and a real example, which was generated from radiation-induced lung cancer cells (A549), through mapping short-reads to human ncRNA database. The results show that the Bayesian method, as realized by Gibbs sampler, is more efficient and robust than the Least-square method.     

A heuristic for minimizing the expected makespan in two-machine flow shops with consistent coefficients of variation

The paper deals with the classical problem of minimizing the makespan in a two-machine flow shop. When the job processing times are deterministic, the optimal job sequence can be determined by applying Johnson’s rule. When they are independent and exponential random variables, Talwar’s rule yields a job sequence that minimizes the makespan stochastically.Assuming that the job processing times are independently and Weibull distributed random variables, we present a new job sequencing rule that includes both Johnson’s and Talwar’s rules as special cases. The proposed rule is applicable as a heuristic whenever the job processing times are characterized by their means and the same coefficient of variation. Simulation results show that it leads to very encouraging results when the expected makespan is minimized.     

Family sequencing and cooperation

This paper analyzes a single-machine scheduling problem with family setup times both from an optimization and a cost allocation perspective. In a family sequencing situation jobs are processed on a single machine, there is an initial processing order on the jobs, and every job within a family has an identical cost function that depends linearly on its completion time. Moreover, a job does not require a setup when preceded by another job from the same family while a family specific setup time is required when a job follows a member of some other family.     

A simulation analysis of sequencing rules in a flexible flowline

The paper concerns a flexible flowline scheduling problem, which arises in the footwear industry. Flexibility of the line allows for manufacturing simultaneously more products in lower quantities, but it also increases the complexity of the task of balancing the line, specially because the mix of products changes everyday. A simulation model to deal with the flexible line is developed and several job sequencing rules and different part input criteria are implemented. The impact of each rule on the quality of the schedules is measured, namely, according to makespan, productivity and average machine utilisation. Computational results concerning a real application are also presented. SIMPLE++ is the simulation language used.     

Two local search approaches for solving real-life car sequencing problems

The NP-hard problem of car sequencing appears as the heart of the logistic process of many car manufacturers. The subject of the ROADEF’2005 challenge addressed a car sequencing problem proposed by the car manufacturer RENAULT, more complex than the academic problem generally addressed in the literature. This paper describes two local search approaches for this problem. In the first part, a new approach by very large-scale neighborhood search is presented. This approach, designed during the qualification stage preceding the final, is based on an original integer linear programming formulation. The second part is dedicated to the approach which enabled us to win the ROADEF’2005 challenge. Inspired by the latest works on the subject, this one is based on very fast explorations of small neighborhoods. Our contribution here is mainly algorithmic, in particular by showing how much exploiting invariants speeds up the neighborhood evaluation and contributes to the diversification of the search. Finally, the two approaches are compared and discussed through an extensive computational study on RENAULT’s benchmarks. The main conclusion drawn at this point is that sophisticated metaheuristics are useless to solve car sequencing problems. More generally, our victory on ROADEF’2005 challenge demonstrates that algorithmic aspects, sometimes neglected, remain the key ingredients for designing and engineering high-performance local search heuristics.