Transformations in optics: Novel perspectives,approaches, applications and implementations

This paper summarizes a set of novel techniques for obtaining optical transformations, which are useful tools for signal processing. Then the paper focuses on deriving several interesting discrete transformations. The discussed transforms include continuous fractional transformations, hybrid transforms and discrete transform kernels.     

Bicriteria problems to minimize maximum tardiness and due date assignment cost in various scheduling environments

We study bicriteria problems of minimizing maximum tardiness and total due date assignment cost in various scheduling environments. We assume that each job can be assigned a different due date without any restriction, and that each due date assignment cost is a non-decreasing function of the quoted due date. We settle the complexity of most of the problems studied by either proving that they are NP-hard or finding a polynomial time solution for them. We also include approximation and non-approximability results for several parallel-machine problems.     

Optimal synthesis of three-dimensional complex amplitude distributions

The synthesis of three-dimensional (3-D) light distributions is important for many applications. For example, in scanning applications it is preferable that the scanning beam preserve its characteristics over a large distance to yield elongated scanning range. It is evident that any 3-D light distribution must satisfy the wave equation or, in second-order approximation, the Fresnel diffraction formula. Thus many desirable 3-D light distributions may not be realizable. We propose a single optical element (OE) that synthesizes a physical beam within a certain 3-D region. The OE provides the optimal physical beam in comparison with a desired one in the sense of minimal mean-square error.     

Optoelectronic implementation of the triple correlation

The auto triple correlation has several fundamental advantages over the ordinary autocorrelation of second order. We present an optoelectronic processor for the computation of the auto triple correlation.     

Proportionate flow-shop scheduling with rejection

In many heavily loaded manufacturing systems, managers routinely make use of outsourcing options in order to maintain reasonable Quality of Service for customers. Thus, there is a strong need to provide tools for managers to economically coordinate sourcing and scheduling decisions. Our main aim is to provide such tools for an important set of flow-shop scheduling problems where rejection (outsourcing) is allowed and processing times are machine-independent. Our scheduling problems are essentially bicriteria problems, which combine a scheduling objective and the total outsourcing cost. We study several problems which differ according to the scheduling criterion considered. Moreover, each problem is divided into four different variations depending on the way the two criteria are dealt with. For example, in one variation the two criteria are aggregated into a single objective function; in two other variations the aim consists of minimizing one criterion subject to ensuring that the value of the other criterion will not exceed a predefined threshold. From a theoretical point of view, a computational complexity classification is provided for all variations of the problems under consideration. Moreover, optimization algorithms have been constructed to solve all problem variations, and approximation schemes have been developed for solving hard variations. Those schemes enable managers to solve large instances of hard variations while controlling the maximal gap between the obtained solution and the (unknown) optimal solution.     

A survey of scheduling with controllable processing times

In classical deterministic scheduling problems, the job processing times are assumed to be constant parameters. In many practical cases, however, processing times are controllable by allocating a resource (that may be continuous or discrete) to the job operations. In such cases, each processing time is a decision variable to be determined by the scheduler, who can take advantage of this flexibility to improve system performance. Since scheduling problems with controllable processing times are very interesting both from the practical and theoretical point of view, they have received a lot of attention from researchers over the last 25 years. This paper aims to give a unified framework for scheduling with controllable processing times by providing an up-to-date survey of the results in the field.     

The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times

We study the earliness-tardiness scheduling problem on a single machine with due date assignment and controllable processing times. We analyze the problem with three different due date assignment methods and two different processing time functions. For each combination of these, we provide a polynomial-time algorithm to find the optimal job sequence, due date values and resource allocation minimizing an objective function which includes earliness, tardiness, due date assignment, makespan and total resource consumption costs.     

An asymptotically optimal online algorithm to minimize the total completion time on two multipurpose machines with unit processing times

In the majority of works on online scheduling on multipurpose machines the objective is to minimize the makespan. We, in contrast, consider the objective of minimizing the total completion time. For this purpose, we analyze an online-list scheduling problem of $n$ jobs with unit processing times on a set of two machines working in parallel. Each job belongs to one of two sets of job types. Jobs belonging to the first set can be processed on either of the two machines while jobs belonging to the second set can only be processed on the second machine. We present an online algorithm with a competitive ratio of ${\rho }_{LB}+O\left(\frac{1}{n}\right)$, where ${\rho }_{LB}$ is a lower bound on the competitive ratio of any online algorithm and is equal to $1+{\left(\frac{?\alpha +\sqrt{4{\alpha }^3?{\alpha }^2+2\alpha ?1}}{2{\alpha }^2+1}\right)}^2$ where $\alpha =\frac{1}{3}+\frac{1}{6}{(116?6\sqrt{78})}^{1/3}+\frac{{(58+3\sqrt{78})}^{1/3}}{3{\left(2\right)}^{2/3}}\approx 1.918$. This result implies that our online algorithm is asymptotically optimal.     

A unified approach for scheduling with convex resource consumption functions using positional penalties

We provide a unified model for solving single machine scheduling problems with controllable processing times in polynomial time using positional penalties. We show how this unified model can be useful in solving three different groups of scheduling problems. The first group includes four different due date assignment problems to minimize an objective function which includes costs for earliness, tardiness, due date assignment, makespan and total resource consumption. The second group includes three different due date assignment problems to minimize an objective function which includes the weighted number of tardy jobs, due date assignment costs, makespan and total resource consumption costs. The third group includes various scheduling problems which do not involve due date assignment decisions. We show that each of the problems from the first and the third groups can be reduced to a special case of our unified model and thus can be solved in O(n³)$O(n^3)$ time. Furthermore, we show how the unified model can be used repeatedly as a subroutine to solve all problems from the second group in O(n⁴)$O(n^4)$ time. In addition, we also show that faster algorithms exist for several special cases.     

Synthesis of spatial coherence

The mutual intensity function plays a major role in characterizing quasi-monochromatic, partially coherent optical signals. We propose to use the mutual intensity as a carrier of information to avoid speckle noise in coherent illumination systems and to permit the use of complex functions that are prohibited spatially incoherent sources. To do this we require methods for encoding the information as a coherence function. An optical system for synthesizing a beam with a given mutual intensity function is proposed. The optical system permits the synthesis of any desired mutual intensity function. The illumination is supplied by a quasi-monochromatic, spatially incoherent source. Experimental results demonstrate the performance of this system for several cases.