Scheduling parallel dedicated machines with the speeding-up resource

We consider a problem of scheduling jobs on m parallel machines. The machines are dedicated, i.e., for each job the processing machine is known in advance. We mainly concentrate on the model in which at any time there is one unit of an additional resource. Any job may be assigned the resource and this reduces its processing time. A job that is given the resource uses it at each time of its processing. No two jobs are allowed to use the resource simultaneously. The objective is to minimize the makespan. We prove that the two-machine problem is NP-hard in the ordinary sense, describe a pseudopolynomial dynamic programming algorithm and convert it into an FPTAS. For the problem with an arbitrary number of machines we present an algorithm with a worst-case ratio close to 3/2, and close to 3, if a job can be given several units of the resource. For the problem with a fixed number of machines we give a PTAS. Virtually all algorithms rely on a certain variant of the linear knapsack problem (maximization, minimization, multiple-choice, bicriteria). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008

Two-machine shop scheduling: Compromise between flexibility and makespan value

In this paper, we consider the problem of providing flexibility to solutions of two-machine shop scheduling problems. We use the concept of group-scheduling to characterize a whole set of schedules so as to provide more choice to the decision-maker at any decision point. A group-schedule is a sequence of groups of permutable operations defined on each machine where each group is such that any permutation of the operations inside the group leads to a feasible schedule. Flexibility of a solution and its makespan are often conflicting, thus we search for a compromise between a low number of groups and a small value of makespan. We resolve the complexity status of the relevant problems for the two-machine flow shop, job shop and open shop. A number of approximation algorithms are developed and their worst-case performance is analyzed. For the flow shop, an effective heuristic algorithm is proposed and the results of computational experiments are reported.

Time-reversal ultrawideband breast imaging: pulse design criteria considering multiple tumors with unknown tissue properties

Pulse design is investigated for time-reversal (TR) imaging as applied to ultrawideband (UWB) breast cancer detection. Earlier it has been shown that a suitably-designed UWB pulse may help to improve imaging performance for a single-tumor breast phantom with predetermined lesion properties. The current work considers the following more general and practical situations: presence of multiple malignancies with unknown tumor size and dielectric properties. Four pulse selection criteria are proposed with each focusing on one of the following aspects: eliminating signal clutter generated by tissue inhomogeneities, canceling mutual interference among tumors, improving image resolution, and suppressing artifacts created by sidelobe of the target response. By applying the proposed criteria, the shape parameters of UWB waveforms with desirable characteristics are identified through search of all the possible pulses. Simulation example using a numerical breast phantom, comprised of two tumors and structured clutter distribution, demonstrates the effectiveness of the proposed approach. Specifically, a tradeoff between the image resolution and signal-to-clutter contrast (SCC) is observed in terms of selection of the excitation waveforms.