Heuristics-PRO5826

Based on the "Iterated local search based on multi-type perturbation for single-machine earliness/tardiness scheduling" by Qin et al. 2015. Tailored to tackle Biskup's 2001 "Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates".

Scheduling Problem with Weighted Tardiness and Earliness

$$\text{f.o. } min \quad \sum_{i=1}^n \alpha_i\cdot E_i + \sum_{i=1}^n \beta_i \cdot T_i$$

$$ \text{s.t. }T_i \geq s_i + p_i - d $$

$$E_i \geq d - s_i = p_i $$

$$s_i + p_i \leq s_k + R\cdot(1 - x_{ik}) $$

$$s_k + p_k \leq s_i + R\cdot x_{ik} $$

$$T_i, E_i, s_i \geq 0 $$

$$x_{ik} \in {0,1}$$

$\alpha $ = earliness weight
$\beta $ = tardiness weight
E = earliness
T = tardiness
s = starting time
p = processing time
d = common due date
i, k = jobs
x = whether the job i preceds k
R = large constant

V-Shape property: the best solutions are ordered so that the ratios of the jobs $\cfrac{p_i}{a_i}$ are in decreasing order in the early jobs set and in increasing $\cfrac{p_i}{b_i}$ order in the late jobs set.

Usage

Run the main.ipynb and change the path of the job_data_biskup.csv for the job data or the result_heuristic99_BA.csv for the initial sequence if needed. Run the cases and results will be saved in the main directory as a csv file containg the early and late job sets, as well as the costs and time to run the instances. Alternatively, it is possible to test a single case inputing the jobs list and the jobs sets on the BiskupILS.py file.

Inputs

According to the problem formulated, it is required a common due date which is the target time for completion of all jobs and a list of jobs containing the processing time, earliness penalty and lateness penalty.

This heuristic also admits as input lists of early (A) and late (B) jobs (with indexes corresponding to the order of the jobs in the jobs list), already sorted in the V-Shape. Thus, the algorithm ideally admits an initial solution generated by a constructive heuristic.

Parameters

The following parameters must be decided before the run:

threshold_swaps: maximum neighborhood size for swaps
threshold_inserts: maximum neighborhood size for inserts
insert_probability: probability of applying insert move over swap

stop_iter: maximum iterations without improvement to stop

alpha_1: tabu list size deterministic parameter
alpha_2: tabu list size probabilistic parameter

L1: number of moves for tabu perturbation
L2: number of moves for construction perturbation 
L3: number of moves for random perturbation

P: probability of applying tabu perturbation
Q: probability of applying construction over random perturbation

General procedure

The ILS algorithm operates as evidenced on the following pseudocodes:

Iterated Local Search

1.  A_best, B_best -> A, B
2.  best_cost = cost(A,B)
3.  iter_no_improv -> 0
4.  while iter_no_improv < stop_iter do:
5.     A, B = local_search(A,B)
6.     if cost(A,B) < best_cost:
7.         A_best, B_best -> A, B
8.         best_cost = cost(A,B)
9.         iter_no_improv = 0
10.     else:
11.        iter_no_improv += 1
12.     endif
13.     x, y = random(0,1), random(0,1)
14.     if x < P:
15.        A, B = tabu_perturbation(A,B,L1)
16.     else if y < (1 - P) * Q:
17.        A, B = construction_perturbation(A,B,L2)
18.     else:
19.        A, B = random_perturbation(A,B,L3)
20.     endif
21. endwhile
22. return A_best, B_best, best_cost, time

V-Shape candidates

This function returns the feasible candidate(s) for insertion or swap, given a job, the early and late jobs sequences already in v-shape. To do so, it verifies whether:

(1) The position where the job is inserted does not break the v-shape property. (2) The sum of processing times in the early jobs set does not exceed the common due date. (3) In case of swaps, if the swapped job insertion doen not break the v-shape property.

Furthermore, to contemplate all possible insertions, the job -1 can outputed, which indicates insertion after the last element of the sequence.

Local Search

The evaluate_move function simply computest the total cost of the sequece after the move. This local search makes the best move until there are no improving moves left.

1.  move_type -> random(insert,swap)
2.  moves -> Ø
3.  sequence -> A + B
4.  best_cost = cost(A,B)
5.  while True
6.      for job in sequence do:
7.          candidates = vshape_candidates(A,B,job,threshold)
8.          cost = evaluate_move(job,candidates,move_type).cost
9.          if cost < best_cost:
10.             append evaluate_move(job,candidates,move_type) to moves
11.         endif
12.      endfor
13.      if moves == Ø:
14.         break
15.     else:
16.         best_move -> move[x], x with minimum cost
17.         implement_move(best_move, move_type)
18.     endif
19. endwhile
20. return A, B

Tabu-perturbation

Similar to local search, but the goal is to make the move that minimizes cost degradation, even if it leads to a worse solution. The search is conducted through L1 iterations and if there is improvement, the move is made and the solution is stored.

1.  move_type -> random(insert,swap)
2.  A_best, B_best = A, B
3.  best_cost = cost(A,B)
4.  moves -> Ø
5.  improved -> False
6.  tabu_list_size = int(alpha_1 * threshold + random(0,alpha_2*threshold)) 
7.  sequence -> A + B
8.  for i from 1 to L1:
9.      for job in sequence do:
10.          candidates = vshape_candidates(A,B,job,threshold)
11.          cost = evaluate_move(job,candidates,move_type).cost
12.          if cost < best_cost
13.              A_best -> A
14.              B_best -> B
15.              best_cost -> cost
16.              improved -> True
17.          endif
18.          append evaluate_move(job,candidates,move_type) to moves
19.      endfor
20.      if moves == Ø:
21.         break
22.      else:
23.         best_move -> move[x], x with minimum cost
24.         implement_move(best_move, move_type)
25.     endif
26. endfor
27. if improved:
28.     return A_best, B_best
29. else:
30.     return A, B
31. endif

Construction perturbation

This perturbation ranks the feasible moves for all the jobs in increasing order of cost then chooses the job at the kth position following the harmonic probability function $VF = \frac{1}{n} \sum_{k=1}\frac{1}{k}$

1.  move_type -> insert
2.  sequence = A + B
3.  moves -> Ø
4.  for job in sequence:
5.     candidates = vshape_candidates(A,B,job,threshold)
6.     append evaluate_move(job,candidates,move_type) to moves
7.  sort move in moves in increasing cost
8.  chosen_move -> harmonic_select(moves)
9.  implement_move(best_move, move_type)
10. return A, B

Random perturbation

Perform random swap/insertion among the fesible candidates of a randomly selected job.