A Mathematical Model for the Single Machine Scheduling Considering Sequence Dependent Setup Costs and Idle Times


1 Department of Industrial Engineering, Najafabad Branch, Islamic Azad University, Isfahan, Iran

2 Department of Industrial Engineering, Lenjan Branch, Islamic Azad University, Isfahan, Iran


Planning and scheduling are among the most important parts of the management’s duties. Development of an efficient scheduling method can results in productivity improvement of an organization. Given the importance of production scheduling in an organization, this research seeks to propose a solution for one of the important problems for the production managers. This problem occurs if a considerable percentage of available production times is allocated to machine setup times. The objective of this research is to find a scheduling method to reach minimum of total production time, earliness and tardiness times. In previous researches not all effective factors on this scheduling method such as machine idle times and machine setup costs have been studied simultaneously. A mathematical model for the optimization of multi-product single-machine scheduling problem have been developed which considered sequence dependent setup costs, costs due to delay in delivery, holding costs, and costs related to machine idle time. Comparative results for the random small size test cases show that the proposed mathematical model can obtained an optimal solution in a relatively low computation time, however, for the large-scale cases this model is not efficient and an approximate method is required for these cases.


Allahverdi, A. Ng, C.T. Cheng, T.C.E. Kovalyov, M.Y. 2008. A survey of scheduling problems with setup times or costs, European Journal of Operational Research, Vol. 187, pp. 985–1032.

Alhaboubi, M.H. and Selim, S.Z. 1993. A sequencing problem in the weaving industry, European Journal of Operational Research, Vol. 66, No.1, pp. 65–71.

Bigras, L.F., Gamache, M. and Savard, G. 2008. The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times, Discrete Optimization, Vol. 5, pp. 685–699.

Choobineh, F.F., Mohebbi, E. and Khoo, H. 2006. A multi-objective tabu search for a singlemachine scheduling problem with sequence-dependent setup times, European Journal of Operational Research, Vol. 175, pp. 318–337.

Georgios, M., Kopanos, L. and Puigjaner 2009. Multi-Site Scheduling/Batching and Production Planning for Batch Process Industries, Computer Aided Chemical Engineering, Vol. 27, pp. 2109-2114.

Hajinejad, D., Salmasi, N. and Mokhtari, R. 2011. A fast hybrid particle swarm optimization algorithm for flow shop sequence dependent ,group scheduling problem, Scientia Iranica, Vol. 3, pp. 759-764.

Karimi-Nasab, M., Haddad, H., Feili, H. and Babaie, M.H. 2013, Solving a Batching-Scheduling Problem on a Multi-Operational Parallel Machine Using Two Meta Heuristic Algorithms. International Journal of Industrial Engineering & Production Management, Vol. 24, No. 2, pp. 225-236 (In Persian).

Khowala, K., Fowler, J., Keha, A., and Balasubramanian, H. 2014, Single machine scheduling with interfering job sets. Computers & Operations Research, Vol. 45, pp. 97-107.

Lee, S.M., Asllani, A.A. 2004. Job scheduling with dual criteria and sequence-dependent setups: mathematical versus genetic programming, Omega, Vol.32, pp.145 – 153.

Mokhtari, H., Nakhaei-Kamalabadi, A. and Zogerdi, S. 2012. Development of upper bound and Heuristic methods for order scheduling problem aiming to minimize machine idle time, Journal of Operations and Production Management, Vol. 3, pp. 41-58.

Naderi, B., Fatemi Ghomi, S.M.T. and Aminnayeri, M. 2010. A high performing metaheuristic for job shop scheduling with sequence-dependent setup times, The Applied Soft Computing, Vol. 10, pp. 703-710.

Rabadi, G., Georgios, M. and Anagnostopoulos, C. 2004. A branch-and-bound algorithm for the early/tardy machine scheduling problem with a common due-date sequence-dependent setup time, Computers & Operations Research, Vol. 31, pp.1727 – 1751.

Subramanian, A., Battarra, M. and Potts C.N. 2014. An Iterated Local Search heuristic for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times, International Journal of Production Research, Vol. 52, No. 9, pp. 2729 – 2742.

Tan, K.C. and Narasimhan, R. 1997. Minimizing Tardiness on a Single Processor with Sequencedependent Setup Times: a Simulated Annealing Approach, Omega, Vol. 25, No. 6, pp. 619 – 634.

Tavakkoli Moghaddam, R., Moslehi, G., Vaseia, M. and Azaronc, A. 2005. Optimal scheduling for a single machine to minimize the sum of maximum earliness and tardiness considering idle insert, Applied Mathematics and Computation, Vol. 167, pp. 1430–1450.

Vanchipura, R., Sridharan, R. and Subash Babu, A. 2014. Improvement of constructive heuristics using variable neighbourhood descent for scheduling a flow shop with sequence dependent setup time, Journal of Manufacturing Systems, Vol. 33, pp. 65– 75.

Yin, Y., Wu, W. H., Cheng, T. C. E., & Wu, C. C. 2014. Single-machine scheduling with timedependent and position-dependent deteriorating jobs. International Journal of Computer Integrated Manufacturing, Vol. 28, No. 7, pp. 781-790.

Zhu, X., and Wilhelm, W.E. 2006. Scheduling and lot sizing with sequence-dependent setup: A literature review, IIE Transactions, Vol. 38, No. 1, pp. 987–1007.