entails the occupation of the latter one during a processing time, noted The Mk µM pi; j;k. problem is thus to both determine an assignment scheme and a sequence of the operations on all machines that minimize some criteria. A set of independent jobs. J • Each job is characterized by the earliest starting time and the latest finishing time • r j dj. Denote by and respectively the processing time and the ready date of the operation pti; j ri; j • Oi; j. The represent the processing time with the machine pi; j;k pti; j Mk. A started operation can not be interrupted. • Each machine can not perform more than one operation at the same time. • The objective is to find an operation ordering set satisfying a cost function under problem • constraints. The considered objective is to minimize the makespan Cmax. ACO and Tabu search for FJSP Scheduling In this stage, the application of the combined ant systems with tabu search techniques in the resolution of FJSP problem are described. Construction Graph and Constraints Generally, the FJSP can be represented by a bipartite graph with two categories of nodes: Oi; j and A task is mapped to a node; a machine is mapped to a There is an edge Mk. Oi; j Mk. between the node and the node if and only if the corresponding task can be assigned to Oi; j Mk the corresponding machine while respecting the availability of the machine and the precedence
Mk µM entails the occupation of the latter one during a processing time, noted pi; j;k. The problem is thus to both determine an assignment scheme and a sequence of the operations on all machines that minimize some criteria. • A set of J independent jobs. • Each job is characterized by the earliest starting time r j and the latest finishing time dj. • Denote by pti; j and ri; j respectively the processing time and the ready date of the operation Oi; j. The pi; j;k represent the processing time pti; j with the machine Mk. • A started operation can not be interrupted. • Each machine can not perform more than one operation at the same time. • The objective is to find an operation ordering set satisfying a cost function under problem constraints. The considered objective is to minimize the makespan Cmax. ACO and Tabu search for FJSP Scheduling In this stage, the application of the combined ant systems with tabu search techniques in the resolution of FJSP problem are described. Construction Graph and Constraints Generally, the FJSP can be represented by a bipartite graph with two categories of nodes: Oi; j and Mk. A task is mapped to a Oi; j node; a machine is mapped to a Mk. There is an edge between the Oi; j node and the Mk node if and only if the corresponding task can be assigned to the corresponding machine while respecting the availability of the machine and the precedence
ANT_COLONY_OPTIMISATION_APPLIED_TO_JOB_SHOP_SCHEDULING_PROBLEM.docx