Title of article :
Simultaneous selection and scheduling with sequence-dependent setup times, lateness penalties, and machine availability constraint: Heuristic approaches
Author/Authors :
Zarei، Mohammad Hossein نويسنده Escuela Técnica Superior de Ingenieros Industriales, Universidad Politécnica de Madrid, C/Jose´ Gutie´rrez Abascal, 2, 28006 Madrid, Spain , , Davvari، Mehdi نويسنده Department of Automotive Engineering, Islamic Azad University, Khomeini Shahr Branch, Isfahan, Iran , , Kolahan، Farhad نويسنده Ferdowsi University of Mashhad , , Wong، Kuan Yew نويسنده Department of Manufacturing and Industrial Engineering, Faculty of Mechanical Engineering, Universiti Teknologi Malaysia, Johor Bahru, Malaysia ,
Abstract :
Job selection and scheduling are among the most important decisions for production planning in today’s manufacturing systems. However, the studies that take into account both problems together are scarce. Given that such problems are strongly NP-hard, this paper presents an approach based on two heuristic algorithms for simultaneous job selection and scheduling. The objective is to select a subset of jobs and schedule them in such a way that the total net profit is maximized. The cost components considered include jobsʹ processing costs and weighted earliness/tardiness penalties. Two heuristic algorithms; namely scatter search (SS) and simulated annealing (SA), were employed to solve the problem for single machine environments. The algorithms were applied to several examples of different sizes with sequence-dependent setup times. Computational results were compared in terms of quality of solutions and convergence speed. Both algorithms were found to be efficient in solving the problem. While SS could provide solutions with slightly higher quality for large size problems, SA could achieve solutions in a more reasonable computational time.
