Isotropic treatment of EMF effects in advanced photomasks
Jaione Tirapu Azpiroz, Alan E. Rosenbluth, et al.
SPIE Photomask Technology + EUV Lithography 2009
We present a new linear programming relaxation for the problem of minimizing the sum of weighted completion times of precedence-constrained jobs. Given a set of n jobs, each job j has processing time pj and weight wj. There is also a partial order<on the execution of the jobs: if j<k, job k may not start processing before job j has been completed. For Cj representing the completion time of job j, the objective is to minimize the weighted sum of completion times, ΣjwjCj. The new relaxation is simple and compact, has exactly two variables per inequality and half-integral extreme points. An optimal solution can be found via a minimum cut computation, which provides a new 2-approximation algorithm in the complexity of a minimum cut on a graph. As a by-product, we also introduce another new 2-approximation algorithm for the problem.
Jaione Tirapu Azpiroz, Alan E. Rosenbluth, et al.
SPIE Photomask Technology + EUV Lithography 2009
Elizabeth A. Sholler, Frederick M. Meyer, et al.
SPIE AeroSense 1997
Donald Samuels, Ian Stobert
SPIE Photomask Technology + EUV Lithography 2007
R.B. Morris, Y. Tsuji, et al.
International Journal for Numerical Methods in Engineering