Scheduling
Generally speaking, scheduling consists of planning and prioritizing activities that need to be performed in an orderly sequence of operations. The objectives of scheduling can be classified into two broad categories (Shanker & Modi, 1999): (1) job related objective – tardiness, makespan, waiting time, flow time, work-in-process and costs; (2) resource related objectives – utilization, idle time, and costs.
Typically, in a scheduling problem, the things to be accomplished are called “jobs”, and each job may require one or more segments called “operations”. Each of these operations requires some resources such as machines and tools for a certain amount of time. When several jobs are to be executed together, the composition of their resource requirements implies additional ordering constraints that prohibit simultaneous demands on non sharable resources. Consequently, a scheduler satisfies both the explicit ordering constraints imposed by the plans and the implicit ordering constraints derived from the availabilities of the resources. Giffler and Thomson (1960) developed an enumerative procedure to generate all active schedules for the general “n” job “m” machine problem. In a similar vein, in (Toker, Kondakci, & Erkip, 1994), the authors proposed an approximation algorithm for the “n” job “m” machine resource constraint job shop problem; while Stafford and Tseng (2002) developed two general models for a family of “m” machines, “n” jobs flowshop sequencing problems.