9522938 Pinedo This research addresses the problem of job scheduling in a job shop environment. Some special features of this research are (1) the consideration of flexible routing for the jobs to be scheduled, and (2) the consideration of multiple objectives. The development of procedures for parametric analysis of schedule quality will also be undertaken. The outcome of the algorithmic developments will be incorporated into prototype scheduling software that has been developed at Columbia University over the past four years. The term "routing flexibility" as used in this research is given two meanings. In the first case, routing flexibility refers to scheduling scenarios in which each workstation in the shop is populated with multiple machines. A job visiting a workstation can only be processed by one machine at the station. In the second case scenario, each job is characterized by an ordered sequence of operations or processing steps to be performed. Each operation or process step can be performed by a subset of all the machines in the shop. Subsets of machines that can perform the various process steps required by a job may overlap. In all the scheduling scenarios considered, the jobs may recirculate. Depending on the scheduling objective pursued, several modeling and solution approaches exist for solving scheduling problems. Most existing algorithms are focused on traditional production scenarios in which each job follows a fixed, prescribed route. Although, these earlier algorithms can serve the needs of many production situations, they fail to function effectively when flexible routing exists for jobs. The work done in this research will serve the needs of the modern day flexible shops as typified by flexible manufacturing systems (FMS). The outcome of the research will be a major contribution to scheduling theory and the expansion of the domain of applicability of scheduling algorithms in production shops.
