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.

References

[1] Ababneh M., Hassan S., and Bani-Ahmad S., “On Static Scheduling of Tasks in Real Time Multiprocessor Systems: An Improved GA- Based Approach,” The International Arab Journal of Information Technology, vol. 11, no. 6, pp. 560-572, 2014.

[2] Allahverdi A., Gupta J., and Aldowaisan T., “A Review of Scheduling Research Iinvolving Setup Considerations,” Omega, vol. 27, no. 2, pp. 219- 239, 1999.

[3] Allahverdi A., Ng C., Cheng T., and Kovalyov M., “A Survey of Scheduling Problems with Setup Times or Costs,” European Journal of Operational Research, vol. 187, no. 3, pp. 985- 1032, 2008.

[4] Atoum J. and Al-Rababaa M., “Multiple Warehouses Scheduling Using Steady State Genetic Algorithms,” The International Arab Journal of Information Technology, vol. 7, no. 3, pp. 310-316, 2010.

[5] Croce F., Salassa F., and T’Kindt V., “A Hybrid Heuristic Approach for Single Machine Scheduling with Release Times,” Computers and Operations Research, vol. 45, pp. 7-11, 2014.

[6] Erel E. and Ghosh J., “Customer Order Scheduling on a Single Machine with Family Setup Times: Complexity and Algorithms,” Applied Mathematics and Computation, vol. 185, (8) 0.2 1.6to 1124z 216145.39 298z 225930.006 12 2212 2.2393zzt nn    176 The International Arab Journal of Information Technology, Vol. 16, No. 2, March 2019 pp. 11-18, 2007.

[7] Hemamalini T., Senthilvel N., and Somasundaram S., “Scheduling Algorithm to Optimize Jobs in Shop Floor,” Journal of Mathematics and Statistics, vol. 6, no. 4, pp. 416- 420, 2010.

[8] Ijaz S., Munir E., Anwar W., and Nasir W., “Efficient Scheduling Strategy for Task Graphs in Heterogeneous Computing Environment,” The International Arab Journal of Information Technology, vol. 10, no. 5, pp. 486-492, 2013.

[9] Munir E., Ijaz S., Anjum S., Khan A., Anwar W., and Nisar W., “Novel Approaches for Scheduling Task Graphs in Heterogeneous Distributed Computing Environment,” The International Arab Journal of Information Technology, vol. 12, no. 3, pp. 270-277, 2015.

[10] Sabouni M. and Logendran R., “A Single Machine Carryover Sequence-Dependent Group Scheduling in PCB Manufacturing,” Computers and Operations Research, vol. 40, no. 1, pp. 236- 247, 2013.

[11] Schaller J., “Scheduling on a Single Machine with Family Setups to Minimize Total Tardiness,” International Journal of Production Economics, vol. 105, no. 2, pp. 329-364, 2007.

[12] Schaller J. and Gupta J., “Single Machine Scheduling with Family Setups to Minimize Total Earliness and Tardiness,” European Journal of Operational Research, vol. 187, no. 3, pp. 1050-1068, 2008.

[13] Sels V. and Vanhoucke M., “A Hybrid Genetic Algorithm for the Single Machine Maximum Lateness Problem with Release Times and Family Setups,” Computers and Operations Research, vol. 39, no. 10, pp. 2346-2358, 2012.

[14] Srikanth U., Maheswari U., Palaniswami S., and Siromoney A., “Task Scheduling Using Probabilistic Ant Colony Heuristics,” The International Arab Journal of Information Technology, vol. 13, no. 4, pp. 375-379, 2016.

[15] Steccoa G., Francois J., and Moretti E., “A Branch-and-Cut Algorithm for a Production Scheduling Problem with Sequence-Dependent and Time-Dependent Setup Times,” Computers and Operations Research, vol. 35, no. 8, pp. 2635-2655, 2008.

[16] Taner M., Hodgson T., King R., and Schultz S., “Satisfying Due-Dates in the Presence of Sequence Dependent Family Setups with a Special Comedown Structure,” Computers and Industrial Engineering, vol. 52, no. 1, pp. 57-70, 2007.

[17] Uzsoy R. and Velásquez J., “Heuristics for Minimizing Maximum Lateness on a Single Machine with Family-Dependent Set-up Times,” Computers and Operations Research, vol. 35, no. 6, pp. 2018-2033, 2008.

[18] Zhou S. and Liu Z., “A Theoretical Development for the Total Tardiness Problem and its Application in Branch and Bound Algorithms,” Computers and Operations Research, vol. 40, no. 1, pp. 248-252, 2013. Scheduling with Setup Time Matrix for Sequence Dependent Family 177 Senthilvel Nataraj received his post graduate degree (M.S By Research) in computer sciences and engineering from Anna University, Chennai, Tamilnadu, India in 2008. He completed his B.E degree in computer science and engineering from Regional Engineering College, Tiruchirappalli, Tamilnadu, India in 1997. Currently, he is an Assistant Professor (Senior Grade) in the department of Computer Science & Engineering at Coimbatore Institute of Technology, Coimbatore, Tamilnadu, India. His research interests include Scheduling Algorithms, Optimization, Remote Sensing & Image Processing. Umamaheshwari Sankareswaran received her doctoral degree in Electrical and Electronics Engineering with specialization in Biometrics, from Bharathiar University, Coimbatore, Tamilnadu, India. She got her Master Degree in Applied Electronics from Coimbatore Institute of Technology in 1991 and Bachelor’s Degree in Electronics and Communication Engineering from Government College of Technology in 1985, Tamilnadu, India. She is presently working as Professor in the Department of Electronics and Communication Engineering, Coimbatore Institute of Technology, Coimbatore, Tamilnadu, India. She holds 29 years of teaching experience. Her research interests are VLSI Design, Optimization, Image and Signal Processing, Embedded Systems and Wireless Communication. Hemamalini Thulasiram received her PhD. degree in Mathematics from Anna University, Chennai, Tamilnadu, India in 2011. She completed her Master of Science degree in Mathematics from Thiyagaraja College of Engineering, Madurai, Tamilnadu, India in 1999. Currently, she is an Assistant Professor in the department of mathematics at Government Arts and Science College, Coimbatore, Tamilnadu, India. Her research interests include Scheduling, Graph Theory, Optimization. Senthiil Varadharajan received his doctoral degree in Mechanical Engineering with specialization in manufacturing simulation from Bharathiar University, Coimbatore, Tamilnadu, India. He got his Master Degree in Production Engineering from PSG College of Technology in 1985 and Bachelor’s Degree in Mechanical Engineering from PSG College of Technology, Coimbatore, Tamilnadu, India in 1983. Presently, he is working as Professor in the department of Production Engineering at St. Peter’s University, Chennai, Tamilnadu, India. His research interests include Optimization, Image Grabbing and Analysis, Virtual Simulation.