A binary search algorithm for the general coupled task scheduling problem
- PDF / 420,794 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 1 Downloads / 189 Views
A binary search algorithm for the general coupled task scheduling problem Mostafa Khatami1 · Amir Salehipour1 Received: 18 April 2020 / Revised: 20 September 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract The coupled task scheduling problem aims to schedule a set of jobs, each with at least two tasks and there is an exact delay period between two consecutive tasks, on a set of machines to optimize a performance criterion. We study the problem of scheduling a set of coupled jobs to be processed on a single machine with the objective of minimizing the makespan, which is known to be strongly NP-hard. We obtain competitive lower bounds for the problem through different procedures, including solving 0-1 knapsack problems. We obtain an upper bound by applying a heuristic algorithm. We then propose a binary search heuristic algorithm for the coupled task scheduling problem. We perform extensive computational experiments and show that the proposed method is able to obtain quality solutions. The results also indicate that the proposed solution method outperforms the standard exact solver Gurobi. Keywords Coupled task scheduling · Single machine · Minimizing makespan · Binary search · Heuristic · Bounds Mathematics Subject Classification 90 Operations research, mathematical programming · 68 Computer science
1 Introduction We study the problem of minimizing the makespan for scheduling a set J = {1, . . . , n} of “coupled task” jobs on a single machine. A coupled task job consists of two separated tasks where there is an “exact” delay period between them. The second (completion) task of job j ∈ J must be processed after the completion of
B
Amir Salehipour [email protected] Mostafa Khatami [email protected]
1
School of Mathematical and Physical Sciences, University of Technology Sydney, Sydney, Australia
123
M. Khatami, A. Salehipour Fig. 1 A coupled-task job
its first (initial) task plus an exact duration of the delay. A job j is shown by a triple (a j , L j , b j ), where parameters a j , L j and b j take positive integer values and denote the processing time of the initial task, the duration of the delay and the processing time of the completion task (see Fig. 1). Using the three-field notation of Graham et al. (1979), minimizing the makespan for the single machine coupled task scheduling problem is commonly denoted as 1|(a j , L j , b j )|Cmax (Khatami et al. 2020). The coupled task scheduling problem has various real-world applications. Shapiro (1980) introduced the coupled task scheduling problem to model a pulsed radar system, where a pulse of electromagnetic energy is utilized to track an object. The transmission of the pulse and the reception of its reflection after a period of time help to measure the size and/or the shape of the tracking object. Therefore, the initial task includes transmission of the pulse and the completion task deals with the reception of its reflection. The system aims at detecting as many objects as possible, which is equivalent to
Data Loading...
