Iterated local search for single machine total weighted tardiness batch scheduling
- PDF / 812,624 Bytes
- 86 Pages / 439.37 x 666.142 pts Page_size
- 12 Downloads / 231 Views
Iterated local search for single machine total weighted tardiness batch scheduling Eduardo Queiroga1 · Rian G. S. Pinheiro2 · Quentin Christ3 · Anand Subramanian4 · Artur A. Pessoa5 Received: 18 March 2020 / Revised: 17 July 2020 / Accepted: 19 October 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract This paper presents an iterated local search (ILS) algorithm for the single machine total weighted tardiness batch scheduling problem. To our knowledge, this is one of the first attempts to apply ILS to solve a batching scheduling problem. The proposed algorithm contains a local search procedure that explores five neighborhood structures, and we show how to efficiently implement them. Moreover, we compare the performance of our algorithm with dynamic programming-based implementations for the problem, including one from the literature and two other ones inspired in biased random-key genetic algorithms and ILS. We also demonstrate that finding the optimal batching for the problem given a fixed sequence of jobs is N P-hard, and provide an exact pseudo-polynomial time dynamic programming algorithm for solving such problem. Extensive computational experiments were conducted on newly proposed benchmark instances, and the results indicate that our algorithm yields highly competitive results when compared to other strategies. Finally, it was also observed that the methods that rely on dynamic programming tend to be time-consuming, even for small size instances. Keywords Batch scheduling · Total weighted tardiness · Iterated local search · Metaheuristics
1 Introduction Let J = {1, 2, . . . , n} be a set of jobs to be processed by a single machine. Each job j ∈ J has the following attributes: processing time p j , size s j , release date r j (earliest time that job j can begin to be processed), due date d j and a positive weight w j . The single machine total weighted tardiness batch scheduling problem (TWTBSP) involves two significant decisions: partitioning the jobs into batches (each job must be in exactly one of the batches) and sequencing the batches. A batch-
Extended author information available on the last page of the article
123
E. Queiroga et al. Table 1 A small TWTBSP instance
Job
pj
dj
sj
wj
rj
1
2
3
1
1
4
2 3 4
2 1 2
2 3 4
1 2 2
1 2 2
0 2 1
5 6
3 1
2 1
3 1
1 3
0 1
Q=4
processing machine (or batching machine) can process several jobs simultaneously as a batch, and the processing time of an each of them is equal to the longest processing time among all jobs in the corresponding batch. For a given sequence of m batches B = (B1 , B2 , . . . , Bm ), the jobs in Bi are processed together and therefore such batch can only start to be processed at time r (Bi ) = max j∈Bi {r j }, and has a processing time p(Bi ) = max j∈Bi { p j }. In addition, C(B1 ) = r (B1 ) + p(B1 ) denotes the completion time of the first batch and C(Bi ) = max{r (Bi ), C(Bi−1 )} + p(Bi ) the completion time of Bi , for i = 2, 3, . . . , m. The machine has a capacity Q which must be sat
Data Loading...
