Optimization of FJSSP using MILP
MILP (May 2018)
1 Problem Formulation-
• Sets and Indices:
- E: set of jobs
- i: job i
- di: due date of job i
- j: operation number
- Oi: operations of job i
- Oij: operation j of job i
- M = M1 U M2: set of machines
- M1 = set of teams × stands
- M2 = set of mechanics × tools
• Decision Variables:
- Sijk : starting time of operation j on machine k
- tijk : processing time of operation j on machine k
- Cijk : completion time of operation j on machine k
- Ci: completion time of job i (aka full job completed)
- Xijk = 1 if Oij is assigned to machine k, 0 otherwise
- Yiji0j0k = 1 if operation Oij precedes operation Oi0j0 on machine k
• Parameters:
- L a large number (> 0)
Objective function: minimize δ; δ 2 R
• Constraints:
- Ci − di ≤ δ; 8i 2 E
- Pk2Mj Xijk = 1; 8i 2 E; 8j 2 Oi ( = only 1 operation is allowed per machine).
- Sijk +Cijk ≤ XijkL; 8i; 8j 2 Oi; 8k 2 Mj ( = is operation ij is not assigned to a machine k then starting and completion times are set to 0).
- Cijk ≥ Sijk + tijk − (1 − Xijk); 8i; 8j 2 Oi; 8k 2 Mj ( = the completion time of an operation of a job is at least as the starting time plus the processing time on that machine).
- Si0j0k ≥ Cijk − (1 − Yiji0j0k)L8i < i0; 8j 2 Oi; 8j0 2Oi0; 8k 2 Mj \ Mj0 ( = different-job operation precedence on the same machine)
- Pk2Mj Sijk ≥ Pk2Mj Cij−1k; 8i 2 E; 8j 2 Oi − fO1g ( = precedence of operations of the same job)
- Ci = Pk2Mj CiOl(i)k = Pk2M(SiOl(i)k + tiOl(i)k; 8i 2 E, where Ol(i) is the last operation of job i. ( = definition of job completion time).
- jEj = n ≤ 50 (ignore)
- X a.m. ≤ Sijk; Cijk ≤ Y p.m. (ignore)