Scheduling with Setup Time Matrix for Sequence
Dependent Family
Senthilvel Nataraj1,
Umamaheshwari Sankareswaran2, Hemamalini Thulasiram3, and
Senthiil Varadharajan4
1Department of Computer Science, Anna University,
India
2Department of Electronics and Communication
Engineering, Coimbatore Institute of Technology, Affiliated to Anna University,
India
3Department of Mathematics, Government
Arts and Science College, Bharathiar University, India
4Production
Engineering Department, Saint Peter's University, India
Abstract: We consider a problem of scheduling n
jobs in k families on a single machine subjected to family set-up time to
minimize the overall penalty. This paper proposes three heuristic approaches
based on neighbourhood structures using setup time matrix. These three
approaches minimize the maximum penalty which in turn minimizes the total
penalty. Inserting the Idle Time initially (ITF approach) or between the
families perform efficiently on large instances. The computational results
prove the efficiency of the algorithm.
Keywords: Scheduling, sequence dependent scheduling,
heuristic algorithm, idle time insertion.