Optimal solution and heuristic methods for earliness and tardiness production scheduling and planning problems

A demand-centred enumerating method with a branch and bound algorithm has been proposed for solving earliness and tardiness production scheduling and planning problems. This method can obtain an optimal solution for small-scale problems within a practical computation time. For larger-scale problems, a decomposition heuristic method has been proposed, which divides the problem into several partial problems in terms of the planning horizon. The partial problems are sequentially connected by the inventory at the end of the planning horizon. The validity of the optimal solution method and heuristic method is verified in a large-scale numerical experiment.