A Book Of Open Shop Scheduling

This book provides an in-depth presentation of algorithms for and complexity of open shop scheduling. Open shops allow operations of a job to be executed in any order, contrary to flow and job shops where the order is pre-specified. The author brings the field up to date with more emphasis on new and recent results, and connections with graph edge coloring and mathematical programming. The book explores applications to production and operations management, wireless network scheduling, and timetabling. The book is addressed to researchers, graduate students, and practitioners in Operations Research, Operations Management, computer science and mathematics, who are developing and using mathematical approaches to applications in manufacturing, services and distributed wireless network scheduling.

This book is not only meant for the people having the knowledge of Scheduling but is also beneficial for Operations Research fraternity, Industrial units like Repair Workshops, semiconductors manufacturing, quality Control Centres etc. It is designed to offer the basic ideas of two stage Open Shop Scheduling problems. It covers not only Scheduling models with different concepts such as transportation time, break down interval, weights of job but also put emphasis to their relevance to Practical situation. Hence all the examples throughout the book help the readers to formulate the real world problems easily.

The problem of scheduling n jobs each of which must be processed by m machines with shop dependent processing order is examined. If the order in which a given job is processed on the machine is not fixed, the system is called an open shop. This situation might occur in testing components of an automobile. The computational difficulty of solving most open shop problem is known with the majority being NP- hard. In shop scheduling problem, a combination of machine order and job order is represented by a shop graph or by the corresponding rank matrix pair (MO, JO). A task is to determine an optimal feasible sequence. Various models of mathematics have been presented to solve different shop scheduling problems. Here, the disjunctive graph model, block matrices model without preemption and with preemption and linear programming models are studied. Some problems have also been represented by Gantt charts. Polynomial time algorithms have been presented with complexity analysis. Some NP- hard problems are also discussed in both cases with preemption and without preemption.