Abstract:
This thesis deals with the lower level of decision in a hierarchical approach to the planning and scheduling of production for two-stage manufacturing facilities. It is concerned with the short term scheduling of the item lot sizes output from the higher level. The plants concerned consist of two stages of activities: at the first stage, the products are manufactured, at the second stage, the manufactured products axe packed in different formats. Between the two stages, there are intermediate storage facilities. In the approach adopted, the problem is decomposed into two subproblems, solved sequentially: the first is concerned with the scheduling of the lot sizes on the packing lines, the second is concerned with the scheduling of the manufacturing units and intermediate storage and has as input the packing lines schedule.At the packing lines level, the lot sizes are to be loaded onto the packing lines so that changeover and packing costs axe minimised. Due to connectivity constraints and shared manpower resources, the packing lines are interdependent. The problem is formulated as a pure integer problem and a branch and bound algorithm is proposed. Lower bounds are computed from a relaxation that decouples the problem into two subproblems: a machine loading subproblem, formulated as a general assignment problem and a pure sequencing subproblem formulated as the problem of finding the shortest arborescence through a certain graph. In order to improve the bound obtained, penalties are computed.At the manufacturing units and intermediate storage level, the demand arising from the packing lines schedule is to be satisfied while minimising production and set-up costs. A tree search procedure that uses a Lagrangean relaxation of the original problem for computing lower bounds is proposed.There is no guarantee that there will be a feasible manufacturing units schedule that satisfies the demand arising from the first optimal packing lines schedule. Thus a one pass procedure is not feasible. In this respect, a coordination device is introduced that allows the user to obtain overall feasibility by reconsidering one or the other schedule. The method can be seen as a multi-pass procedure whose overall target is feasibility rather than optimality.Computation results are first reported for the packing lines algorithm only and then for the overall algorithm.