We formulate and analyze the following problem of scheduling dependent batching tasks on a common resource. Each task is associated with an execution time window. Some can be executed simultaneously in batch, while others need exclusively use of the resource. A task may depend on a set of tasks such that it becomes executable only if all its ancestor tasks are completed. We look for a task scheduling policy maximizing the system reward. We investigate both the offline and online settings by focusing on a typical scenario where the task dependency forms a tree or a forest. In both settings, we formally establish the hardness of the scheduling problem by showing that the offline scheduling is NP-hard and the online counterpart admits no scheduling policy with finite competitive ratio. We then develop approximation scheduling algorithms for both cases with deterministic worst-case performance guarantee in terms of system utility. We further conduct numeric experiments to evaluate our algorithms under a variety of parameter settings to demonstrate the effectiveness of our scheduling algorithms.

We investigate the following batching task scheduling problem. There is a set of tasks to be executed on a number of machines. Some tasks can be executed simultaneously on a single machine, while others require exclusive use of an entire machine. The scheduler needs to find a schedule giving optimum system utility. We develop an algorithmic framework for this batching task scheduling by investigating four formulations of the problem, the bounded and unbounded batching, depending on whether the number of simultaneously executable tasks is bounded, the synchronous and asynchronous batching, depending on whether the batched tasks need to start synchronously. For each formulation, we develop our approximation algorithm whose approximation ratio outperforms the best existing result. We further perform numerical simulations in a wide variety of system settings to complement our theoretical analysis and demonstrate the effectiveness of our scheduling algorithms.

We formulate and analyze a fundamental downlink transmission scheduling problem in a wireless communication system, composed of a base station and a set of users, each requesting a packet to be served within a time window. Some packets are requested by several users and can be served simultaneously due to the broadcast nature of the wireless medium. The base station can choose from a set of transmission strategies, e.g., in terms of combination of data rate and coding scheme, to serve the users. Each request can be served by a subset of transmission strategies. We seek a downlink transmission scheduling algorithm generating maximum aggregated system-wide utility. In this paper, we develop approximation algorithms for the formulated downlink transmission scheduling problem in both offline and online settings. We first establish the NP-hardness of the offline scheduling problem and the approximation hardness and bound of the online scheduling problem in non-preemptive and preemptive-restart models, respectively. We then design approximation algorithms and derive the approximation and competitive ratios of our online and offline scheduling algorithms. Numerical simulations are performed to further evaluate our algorithms in a wide range of network settings.

We formulate and analyze a generic task scheduling problem: a set of tasks need to be executed on a pool of continuous resource such as spectrum and memory, each requiring a certain amount of time and contiguous resource; some tasks can be executed simultaneously in batch by sharing the resource, while others requiring exclusive use of the resource. We seek an optimal resource allocation and the related scheduling policy maximizing the overall system utility. This problem, termed as the contiguous-resource batching task scheduling problem, arises in a variety of engineering fields, where communication and storage resources are potential bottlenecks and thus need to be carefully scheduled. Two motivating examples are the spectrum bonding problem in dynamic spectrum access systems and the dynamic storage allocation problem in computer systems. In this paper, we investigate both offline and online scheduling settings. We first establish the NP-hardness of the offline setting and the inapproximability of the online setting in its generic form. Given the theoretical performance limit, we then develop approximation algorithms with mathematically proven performance guarantee in terms of approximation and competitive ratios for the offline and online settings.