Research on due date-oriented objectives in the parallel machine environment is at best scarce compared to objectives such as minimizing the makespan or the completion time-related performance measures. Moreover, almost all existing work in this area is focused on the identical parallel machine environment. In this study, we leverage on our previous work on the single machine total weighted tardiness (TWT) and total weighted earliness/tardiness (TWET) problems and develop a new preemptive relaxation for both problems on a bank of unrelated parallel machines. The key contribution of this paper is devising a computationally effective Benders decomposition algorithm to solve the preemptive relaxation formulated as a mixed-integer linear program. The optimal solution of the preemptive relaxation provides a tight lower bound. Moreover, it offers a near-optimal partition of the jobs to the machines. We then exploit recent advances in solving the nonpreemptive single-machine TWT and TWET problems for constructing nonpreemptive solutions of high quality to the original problem. We demonstrate the effectiveness of our approach with instances of up to five machines and 200 jobs.

We consider source-initiated broadcast session traffic in an ad hoc wireless network operating under a hard constraint on the end-to-end delay between the source and any node in the network. We measure the delay to a given node in the number of hops data travels from the source to that node, and our objective in this paper is to construct an energy-efficient broadcast tree that has a maximum depth Δ, where Δ; represents the end-to-end hop constraint in the network. We characterize the optimal solution to a closely related problem in massively dense networks using a dynamic programming formulation. We prove that the optimal solution can be obtained by an algorithm of polynomial time complexity O(Δ²). The solution to the dynamic program indicates that there is a single optimal policy applicable to all massively dense networks. Elaborating on the insights provided by the structure of the problem in massively dense networks, we design an algorithm for finding a solution to the hop constrained minimum power broadcasting problem in general networks. By extensive simulations, we demonstrate that our proposed optimization-based algorithm generates broadcast trees within 20% of optimality for general dense networks.