Stochastic procedures for scheduling minimum job sets on mixed model assembly lines

In this article, we address the problem of how to sequence the jobs defined by a set of operations so that a well balanced Mixed Model Assembly Line is utilized efficiently. The objective depends on the management philosophy for completing the remaining work that cannot be done within the predefined boundaries of stations. We adopt the US philosophy and consider minimising the total amount of work to be completed by utility workers. Since the optimum solution procedures are found to be computationally intractable, most of the attention has been devoted to developing efficient heuristics. We propose stochastic algorithms which are combinations of Simulated Annealing and problem specific knowledge methods. Posterior and prior formulas are developed to determine lower bounds on the optimal objective values. Extended computational experiments indicate that very good results and often optimal ones can be obtained for most practical problems.