Some problems in sequencing and scheduling utilizing branch and bound algorithms

Abstract

This dissertation deals with branch and bound algorithms which are applied to the two-machine flow-shop problem with sparse precedence constraints and the optimal sequencing and scheduling of multiple feedstocks in a batch type digester problem . The common characteristic of these problems is that they are combinatorial optimization problems of the sequencing and scheduling class. Branch and bound methods are the natural approaches for these problems classes. The objective of this research is to derive efficient branch and bound algorithm s for these problems. An efficient solution of the problem with parallel-chain precedence constraints was developed by Kurisu in 1976. The problem studied here is to find a schedule which minimizes the maximum flowtime with the requirement that the schedule does not violate a set of sparse precedence constraints. This research provides a branch and bound algorithm which employs a lower bounding rule and is based on an adjustment of the sequence obtained by applying Johnson's algorithm. It is demonstrated that this lower bounding procedure in conjunction with Kurisu's branching rule is effective for the sparse precedence constraints problem class. Biomass to methane production systems have the potential of supplying 25% of the national gas demand. The production systems associated with this conversion process axe anaerobic digestion facilities. The economic viability of these systems depends a great deal on cost effective production methods and facilities. The optimal operation of a batch digester system requires the sequencing and scheduling of all batches from multiple feedstocks during a fixed time horizon. A significant characteristic of these systems is that the feedstock decays in storage before use in the digester system. The operational problem is to determine the time to allocate to each batch of several feedstocks and then sequence the individual batches so as to maximize biogas production for a single batch type digester over a fixed planning horizon. This research provides a branch and bound algorithm for sequencing and a two-step hierarchical dynamic programming procedure for time allocation scheduling. An efficient heuristic algorithm is developed for large problems and demonstrated to yield excellent results.