Solving assembly scheduling problems with tree-structure precedence constraints: A Lagrangian relaxation approach

In this paper, we consider an assembly scheduling problem (ASP) with tree-structured precedence constraints. In our problem, there are a number of work centers. Each work center contains a number of machines of the same functionality. The job to be processed via this system is a job with tree-structure precedence constraints. Each operation in the job has a designated work center. We propose a mixed integer linear programming formulation and solve the problem with a Lagrangian relaxation (LR) approach. We solve the subproblems of the LR problem via a heuristic method and generate feasible solutions via a randomized list scheduling algorithm. Near-optimal results are obtained and the computational time is within a few seconds for problems with size up to 20 machines and 300 operations.