Author’s Accepted Manuscript

Step 3: Fixing the solution.

Select the item _min that has the minimum of _rest. Fix the solution of the _min with (27) -(31).

rest ^← rest ^{∖ {} min^{} .}

Step 4: Check if all items are fixed. If _rest ≠ ∅, go to Step 3.
Step 5: Evaluation of the upper bound.
The upper bound derived by the fixed solutions is compared with the one derived from LDC algorithm at Step 2 and obtain a better upper bound.
7 A large scale neighborhood search based on decomposition structure
In Section 6, the better feasible solutions and the upper bound are obtained in a short time. In this section, we further improve the LDC algorithm by using the neighbourhood search. The idea of the search is to locally optimize subproblem, once a solution of the problem is available. This is based on the POPMUSIC (Taillard and Voß (2002), Alvim et al. (2009), Ostertag et al. (2009)). These local optimizations are repeated until no improvements are found. The main point is the definition of the subproblem. The definition of the subproblem is presented in the next section.

7.1. The definition of the subproblem
The original problem is decomposed into I subproblems by removing the coupling constraints (2), (4), (5) and (15). Several subproblems are chosen randomly. They are aggregated to build a subproblem by adding extended

(2), (4), (5) and (15). The formulation of the subproblem is the following when r parts are chosen. Let ∈

	∑ ,(pop) + ∑ ,(fixpop) ≤ 1,			∀ , ∀
	∈	∈ ∖
∑∑		+ ∑ ∑		≤ , ∀
	,(fixpop)		,(fixpop)
∈ =1		∈ ∖ =1

If the solution of ASP_r is updated, the current tentative solution is also updated.