Balancing and cyclical scheduling of asynchronous mixed-model assembly lines with parallel stations

This paper considers two optimization problems commonly associated to mixed-model assembly lines: balancing task-station assignments and sequencing/scheduling different product models in a cyclical manner. Cyclical scheduling for this particular problem variant is challenging, and multiple approaches have been previously employed by different authors. This paper presents a new mixed-integer linear programming formulation to optimize the steady-state of these lines. Tests on a 36-instance benchmark demonstrated that the proposed model significantly outperformed the previous literature formulation. Furthermore, it is shown that common scheduling rules (often used in simulators) do not necessarily converge to optimal cyclical schedules even when the optimal launch order is used. Tests have also demonstrated that parallelism can allow a marginally increasing value for workstations: doubling (tripling) stations in a line with parallelism can often offer more than double (triple) the optimal throughput of lines without parallelism.