Neste trabalho, abordamos o problema de sequenciamento de pedidos (order scheduling), no qual os pedidos dos clientes (compostos por diferentes tarefas individuais) são agendados, em que a função objetivo a ser minimizada é o atraso total (total tardiness) dos pedidos. Na literatura revisada, o problema de sequenciamento de pedidos de clientes, encontramos menos referência que em comparação com outros ambientes de produção, como, por exemplo, máquinas paralelas ou flow shop. Neste trabalho, apresentamos uma nova variante para o problema, na qual são considerados explicitamente os tempos de preparação (setups) das máquinas dependentes da sequência de produção, sendo pertencente à classe NP-difícil. Propomos uma nova formulação de programação linear inteira, uma adaptação da heurística OMDD (denotado OMMD-S) e uma heurística denominada Modelo com Permutação Fixa (Model with fixed permutaion - MFP). A extensiva experiência computacional realizada mostra que a heurística MFP é o mais eficiente para as instâncias avaliadas.