The authors study Fredholm properties for a certain class of elliptic problems. The operators corresponding to these problems form an algebra closed relative to adjoints, and are obtained as the elements of an extension of the set of pseudodifferential operators via a special class of nonlocal operators. These last operators are the Fourier integral operators associated with some fixed smooth bundle.