Serial machining lines are considered. Such lines consist of a sequence of unit head machines (stations). The operations to manufacture a product are grouped into blocks at every station. The blocks are executed sequentially and the operations within each block are performed simultaneously by the same spindle head. The inclusion and exclusion constraints for combining operations into blocks and stations as well as the precedence constraints are given. The problem is to assign the operations to blocks and the blocks to workstations minimizing the total line cost. The solution must provide a desired productivity (cycle time), it must also satisfy all technological constraints. In this paper a hybrid approach is proposed, which tries to improve a feasible solution obtained by a heuristic. The approach is based on decomposition of the initial problem into several sub-problems in accordance with a heuristic solution and solving the obtained sub-problems by a shortest path algorithm. Computational tests show the efficiency of the proposed approach for large-scale problems in comparison with simple heuristic algorithms