Heuristic algorithms for a delivery workload balancing problem in an assembly plant

摘要

In this paper, a delivery workload balancing problem in an assembly plant is considered. The problem is first described as a special case of the unrelated parallel machine scheduling problem of minimizing the makespan. Then, a polynomial time heuristic algorithm is proposed, which is regarded as a dynamic programming procedure to compute a linear partition of a specified list of given jobs. In addition, a simple improvement procedure based on local search technique is discussed. Numerical results indicate that from the viewpoints of solution quality and execution time both, the proposed heuristic is applicable in the practical situation.