The job shop scheduling problem (JSP) is a resource allocation problem where the resources are called machines. The problem involves finding an assignment (schedule) for a set of jobs to the machines so that the jobs can be completed “optimally.” Each job may consist of several tasks, and each task must be processed on a particular machine. Furthermore, the tasks in each job are subject to precedence constraints. A schedule is, then, an arrangement of all tasks on the machines that satisfies the precedence constraints. Usually the number of constraints is very large, which makes JSP one of the hardest combinatorial problems (an NP-complete problems, [99] and [57]. The flow shop problem (FSP), a much restricted version of JSP, can be reduced to the traveling salesman problem (TSP) [137].