A methodology to solve single-model, stochastic assembly line balancing problem and its extensions

Abstract

A methodology for the solution of single-model, stochastic assembly line balancing problem is developed for the objective of minimizing the total labor cost (dictated by the number of stations on the line) and expected incompletion cost arising from tasks not completed within the prespecified cycle time.

The proposed procedure is an approximation procedure that divides the problem into subproblems. For each subproblem, an approximate solution is obtained using the dynamic programming procedure developed for the problem. This procedure is incorporated with a special bounding strategy to overcome the rapidly increasing storage and computational requirements as the size of the problem increases. These approximate solutions are further improved by a branch-and-bound type of procedure called the improvement procedure. This procedure uses approximate costs, instead of lower bounds, to fathom the nodes of the enumeration tree constructed; thus, it is not, in the true sense of the word, the branch-and-bound technique. Consequently, the procedure is not guaranteed to result in the optimal solution; however, it is shown to generate solutions within (1 + ε) of the optimal solution. The improvement procedure either improves the approximate solutions obtained using the dynamic programming procedure or determines that they are quite close to the optimal ones. The improved solutions of the subproblems are then appended to each other to produce the solution of the original problem.

Some dominance properties that contribute to the effectiveness of the improvement procedure and help in reducing the size of the enumeration tree are developed. Some sequencing and scheduling problems related to the node evaluation scheme of the improvement procedure are also investigated. A single-machine sequencing procedure is developed for the objective of minimizing the expected incompletion cost with tasks having a common due date and stochastic processing times. This procedure is extended to construct a schedule on M parallel machines. In these procedures, in-completion costs of the tasks are independent of their expected performance times; it can be interpreted as relaxing the precedence relations among the tasks. Solution procedures are also developed for the above sequencing and scheduling problems for the case in which the incompletion costs of the tasks are proportional to their expected performance times. Computational results and analyses made indicate that these procedures result in almost optimal solutions.