Simultaneous selection and scheduling with sequence-dependent setup times, lateness penalties, and machine availability constraint: Heuristic approaches
, Available Online, June 2015
Mohammad Hossein Zarei, Mehdi Davvari, Farhad Kolahan and Kuan Yew Wong PDF (685K)
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 candidate jobs and schedule them in such a way that the total net profit is maximized. The cost components considered here 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 more reasonable computational time.
Keywords: Job selection, Job scheduling, Earliness, Tardiness, Lateness, Sequence-dependent setup time, Scatter search, Simulated annealing
GRASP to minimize total weighted tardiness in a permutation flow shop environment
, Available Online, June 2015
Lina Paola Molina-Sánchez and Eliana María González-Neira PDF (685K)
Abstract: This paper addresses the scheduling problem in a Permutation Flow Shop (PFS) environment, which is associated with many types of industries such as chemical, petrochemical, automobile manufacturing, metallurgical, textile, etc. Thus, this work intends to solve a PFS scheduling problem in order to minimize the total weighted tardiness, since it is an important sequencing criterion not only for on time delivery jobs but also for customer satisfaction. To solve the problem, GRASP (Greedy Randomized Adaptive Search Procedure) metaheuristic is proposed as a solution, which has shown competitive results compared with other combinatorial problems. In addition, two utility functions called Weighted Modified Due Date (WMDD) and Apparent Tardiness Cost (ATC) are proposed to develop GRASP. These are based on dynamic dispatching rules and also known for solving the problem of total weighted tardiness for single machine scheduling problem. Next, an experimental design was carried out for comparing the GRASP performance with both utility functions and against the WEDD dispatching rule results. The results indicate that GRASP-WMDD could improve the total weighted tardiness in 47.8% compared with WEDD results. Finally, the GRASP-WMDD performance for the PFS total tardiness problem was evaluated, obtaining a relative deviation index of 13.89% and ranking the method over 26 heuristics and metaheuristics.
Keywords: Permutation Flow Shop (PFS), Total Weighted Tardiness (TWT), GRASP, Weighted Modified Due Date (WMDD), Apparent Tardiness Cost (ATC), Weighted Earliest Due Date (WEDD)
® 2010-2015 GrowingScience.Com