Analizando tu plan de ejecución, por lo menos para la primera parte vemos varias cosas:
Aunque existen índices en las tablas, estos no parecen usarse adecuadamente, ya que todas las operaciones realizadas en el plan son INDEX SCAN. Dichas operaciones SCAN son consecuencia de que las operaciones de JOIN se hagan con HASH.
En el caso de la tabla RollosEmbarque probablemente no se pueda evitar hacer el JOIN con HASH, y es probablemente la mejor opción si la tabla es muy muy grande, pero podemos restringir la cantidad de registros en juego en la operación ejecutando primero los JOINS que no dependen de dicha tabla.
Podemos agrupar dbo.Remisiones, dbo.RemisionesDetalle, dbo.Consignatarios y dbo.Operadores en una subconsulta para obtener IDRollo. Ya que este es el vínculo con RollosEmbarque, y suponiendo que los IDRollo obtenidos sean menos que los que existen en RollosEmbarque, se podría ganar tiempo de ejecución.
El último paso sería vincular los datos del self-join de la tabla Clientes. Estos no limitan la búsqueda, son meramente informativos. Pero podríamos evitar hacer un HASH JOIN que aunque eficaces para tablas muy grandes, son inadecuados para tablas pequeñas como parece serlo esta tabla. Deberíamos esperar un LOOP JOIN como mejor opción.
Sin embargo, el tiempo total de respuesta no será mejor nunca que el tiempo total que tarde en devolver de la tabla RollosEmbarque los registros donde IDRollo coincida con los registros IDRollo de RemisionesDetalle.
Según parece, defines el cluster index en función del PK de las tablas asi que...
Remisiones debería tener un índice en Fecha y Estatus.
CREATE NONCLUSTERED INDEX IX_Remisiones_K_Fecha_Estatus
ON dbo.Remisiones(Fecha, Estatus)
RemisionesDetalle debería tener un índice en NoRemision (ya lo tiene si NoRemision es el primer campo del cluster index)
En ese caso, Operadores no debería tener problemas.
Debería haber un índice en la columna IDGrupo de Clientes. En esta consulta puede resultar benéfico incluir CodigoCliente en el índice(Fat Index):
CREATE NONCLUSTERED INDEX IX_CLIENTES_K_IDGrupo_CCodigoCliente
ON dbo.Clientes(IDGrupo)
INCLUDE(CodigoCliente)
RollosEmbarque ya tiene un indice adecuado en IDRollo (es la clave del cluster index)
Código:
SELECT ro.IDPlanta, cl.Grupo, ro.IDMolino, cl.Cliente,
ro.IDRollo, ro.NoMaster, ro.NoCase, ro.NoInspeccion,
ro.NoProcesador, ro.NoParte, ro.Revision,
ro.IDEspecificacion AS Spec, ro.Dimension, ro.Peso,
CONVERT(varchar, ro.Posicion) + '/' + CONVERT(varchar, ro.Cortes) AS Corte,
ro.FechaRecepcion, ro.FechaCorte, ro.FechaEntrega,
CONVERT(varchar, re.NoRemision) AS NoRemision,
ro.Barco, ro.NoViaje, ro.NoFacturaCompra, ro.CostoMXP, ro.CostoUSD,
CAST(re.NoFacturaVenta AS varchar) AS NoFacturaVenta,
ro.Espesor, ro.Ancho, ro.Largo, ro.Proceso,
ro.IDCliente, ro.RolloPadre, ro.IDMaterial,
re.IDUsuario, re.TimeStamp, ro.Pedimento,
ro.FechaPedimento, ro.Fraccion, ro.Piezas,
re.IDConsignatario, re.NombreConsignatario,
re.Tipo, re.Operador, re.Observaciones,
ro.IDProveedor, ro.CostoFactura, ro.FechaFacturaCompra, ro.Lote
FROM dbo.RollosEmbarque AS ro
INNER JOIN (
SELECT z.IDRollo,
z.IDUsuario,
z.TimeStamp,
y.NoRemision,
y.NoFacturaVenta,
y.IDConsignatario,
y.Tipo,
y.Observaciones,
x.NombreCorto AS NombreConsignatario,
w.Nombre AS Operador
FROM dbo.Remisiones AS y
INNER JOIN dbo.RemisionesDetalle AS z
ON y.NoRemision = z.NoRemision
LEFT JOIN dbo.Consignatarios AS x
ON y.IDConsignatario = x.IDConsignatario
LEFT JOIN dbo.Operadores AS w
ON y.IDOperador = w.IDOperador
WHERE y.Estatus = 'C'
AND y.Fecha >= '20070101'
AND y.Fecha < '20090101'
) AS re
ON ro.IDRollo = re.IDRollo
INNER JOIN (
SELECT u.IDCliente,
u.CodigoCliente AS Cliente,
v.CodigoCliente AS Grupo
FROM dbo.Clientes AS v
INNER JOIN dbo.Clientes AS u
ON u.IDGrupo = v.IDCliente
) AS cl
ON ro.IDCliente = cl.IDCliente
WHERE ro.IDPlanta NOT IN ('APRAMOS', 'APSLP', 'LAGERMEX-PUE', 'LAGERMEX-SAL')
Espero que te pueda servir, checa que el plan de ejecución cambie. Y que se hayan reducido las operaciones IO.