Nowadays, globalization and its impact on the growing competitive markets andimportance of customer satisfaction have promoted customer-oriented systems in companies. One such approach is the Just-In-Time (JIT) production system. This concept has induced a new type of scheduling problems in which both earliness and tardiness are penalized. Minimizing the sum of maximum earliness and tardiness is a recently proposed criterion. This study first addresses the problem of minimizing the sum of maximum earliness and tardiness on a single machine with equal release times. An effective heuristic method has been developed for this problem. Furthermore, a branch and bound algorithm with backward approach was developed which draws upon efficient lower and upper bounds andew dominance rules. A set of 1280 instances with job sizes vary from small to large, were randomly generated. All of the instances were solved in less than 700 seconds, showing the high efficiency of our proposed algorithm. Second, the problem was considered with unequal release times. The 3-partition problem was taken to determine the complexity of the problem and it was shown to be “NP-hard in the strongly sense”. Then, the problem was considered for the two scenarios of with and without idle inserts. In the first scenario, a branch and bound algorithm with forward approach is developed as an exact method. In the algorithm, modified dispatching rules were proposed as upper bound while a procedure considering preemption is used for obtaining a good lower bound. Also, dominance rules based on no-unforced idle timeand the base problem are used to fathom the nodes. In order to evaluate the efficiency of proposed algorithm, 4860 instances were randomly generated varying from 7 to 1000 jobs. We showed that the branch and bound algorithm was capable of optimally solving 94.1% of the instances, showing its efficiency in solving all problem sizes. In the second scenario, a polynomial time algorithm was proposed to obtain the best values of idle insert in a known sequence. Then, the scheduling problem was studied and efficient lower and upper bounds were used to propose a branch and bound scheme, instead, as an exact method. In this problem, three new dominance rules based on problem assumptions were developed. This algorithm was capable of solving problems with up to 20 jobs. Large sizes problems were solved by two evolutionary meta-heuristic algorithm, genetic algorithm and particle swarm optimization. Computational results showed that the proposed genetic algorithm improved the solutions in terms of both quality and time efficiency.
