The problem of sequencing jobs on a single machine to minimize total cost (earliness and tardiness) is nowadays not just important due to traditional concerns but also due to its importance in the context of Collaborative Networked Organizations and Virtual Enterprises, where precision about promptly responses to customers’ requests, along with other important requirements, assume a crucial role. In order to provide a contribution in this direction, in this paper the authors contribute with an applied constructive heuristics that tries to find appropriate solutions for single machine scheduling problems under different processing times and due dates, and without preemption allowed. In this paper, two different approaches for single-machine scheduling problems, based on external and internal performance measures are applied to the problem and a comparative analysis is performed. Computational results are presented for the problem under Just-in-Time and agile conditions on which each job has a due date, and the objective is to minimize the sum of holding costs for jobs completed before their due date and tardiness costs for jobs completed after their due date. Additional computational tests were developed based on different customer and enterprise oriented performance criteria, although preference is given to customer-oriented measures, namely the total number of tardy jobs and the maximum tardiness.