Abstarct One of the important issues in scheduling problems is considering realistic assumptions based on actual manufacturing environments in order to approach manager’s decisions and presenting just in time productions. Setup time separated from processing time and depended on job sequences is one of these assumptions. Sequence- dependent setup time was either overlooked in scheduling problems or integrated with processing times for simplifying in years, but considering setup time as a separate parameter is really notable in reducing costs and also enhancing performance of production planning, Therefore it attracted attraction recently. In many industries, considering this assumption can make the production plans, actual and more efficient. In this study, first the problem of minimizing the sum of maximum earliness and tardiness, based on Just-In-Time (JIT) systems, on a single machine with sequence dependent setup time is addressed. For achieving optimal solution a branch and bound algorithm with forward approach was developed including effective dominance and bounding rules. Also a heuristic method has been proposed which was utilized as an upper bound in branch and bound algorithm. In following, the problem of minimizing the sum of maximum earliness and tardiness with family sequence dependent setup time as a notable assumption in increasing efficiency of production systems is considered. Optimal solution is gained through a branch and bound algorithm. This algorithm includes appropriate dominance rules and lower bound and also a heuristic method as an upper bound. Key Words Sequence-dependent Setup time, Earliness, Tardiness, Scheduling
