Mathematical modeling of scheduling problems

The purpose of scheduling is to disaggregate the general production plan into time phased activities and determine a time table for activities which will optimize pre-determined criteria. Minimizing flow times, keeping close conformance to deadlines and efficient utilization of resources are the three broad classes of decision making criteria used in scheduling. In this paper, important criteria commonly used for evaluating scheduling decision are identified. A scheduling cost model is developed for evaluating the cost of the schedule generated. Further, mathematical models are developed for generating optimal schedules in single machine, parallel machine, flow shop, flow shop with multiple processors and job shop scheduling environment. The objective function in the mathematical models may consist of a single goal of minimizing the cost based upon a comprehensive scheduling cost model, or may consist of a set of goals composed of different scheduling criteria, both of which are modeled in this research. The paper concludes with a discussion on the use of the Lagrangian relaxation method for solving mixed integer programming models for optimal or near optimal solution.