In this paper we develop a mathematical model and propose six heuristic algorithms for scheduling jobs with incompatible job families, on a singe batch processor (BP). The motivation for this paper comes from the heat treatment operation in gear manufacturing process used to manufacture automobile gears. The different types of gears used in automobiles form incompatible families for the heat treatment operation. The objective here is to schedule jobs with dynamic job arrivals and different due dates in order to minimize total weighted tardiness. An integer linear programming (ILP) model is developed for the problem. The problem is NP-hard and hence we propose heuristics algorithms to address it. We demonstrate the workability of the algorithms with a numerical example.
Keywords: Scheduling, Batch processor, Incompatible job families, Heuristic Algorithms.
[...] Weighted Job Score Heuristic algorithm 3 (WJSH3): The heuristic algorithm WJSH3 is similar to the heuristic algorithms WJSH2 except that in Step of this heuristic algorithm the jobs considered for accommodating in the temporary batch need not be consecutive. That is, the ordered job-list is accessed till the end Development of Weighted Family score and Job Score based Heuristic algorithms (WFJSH): The heuristic algorithms in this group are based on the computation of weighted score of the families followed by the weighted score of jobs in the selected family. [...]
[...] The working mechanism of the proposed heuristic algorithms of this group is as follows: The jobs available in front of the batch processor at the actual available time t are considered. The weighted score of each job is computed based on: job weight, job processing time, and amount of slack available for the job at the actual time t. For computing the weighted score the normalized values of job weight, job processing time and amount of slack available are used. [...]
[...] The weights: 40% for family tardiness factor and 60% for family slackness factor are fixed from a series of pilot experiments conducted. Also, for family slackness factor, a negative weight is used, so that lower values of these will get higher scores. The family having the minimum score is selected. The logic here is that by selecting this family, the losses for jobs not belonging to the selected family are minimized. After selection of family the next decision is construction of a batch from the jobs of the selected family. [...]
[...] Consider one more constraint in addition to the default capacity constraint of the BP Single BPM; different job sizes; equal ready times Single BPM; different job sizes; equal ready times Algorithm Proposed exact and approximate solution procedures Developed DP algorithms and provided heuristics Branch and bound procedure for BPM model proposed in Dobson and Nambimadom (2001) Integer programming model developed; it was proven that the problem is NP-hard and a number of heuristic algorithms were proposed Proposed two versions of genetic algorithms Proposed a number of heuristics and designed genetic algorithms Heuristic algorithms proposed Decomposed problem into subproblems & proposed heuristic NP-hard proof was shown and a DP algorithm with polynomial time complexity proposed Proposed a number of heuristics and design a hybrid genetic algorithm Decompose the problem into two subproblems and use GA Proposed several heuristics algorithms Heuristic algorithms proposed Used inductive decision trees and neural networks from machine learning Propose genetic algorithm Objective & 5 Mehta and Uzsoy (1998) Azizoglu and Webster (2001) Dobson and Nambimadom (2001) Balasubramanian et al. [...]
[...] Conclusion: We have developed a mathematical model and proposed six heuristic algorithms for solving the single batch processor scheduling problem that considers many real life situations simultaneously. The heuristic algorithms are based on the computation of weighted score of the families and/or the weighted score of jobs. We developed a numerical example and demonstrated the working of two of the heuristic algorithms. References: Azizoglu, M., and Webster, S. (2001) Scheduling a batch processing machine with incompatible job families. Computers & Industrial Engineering -335. [...]
APA Style reference
For your bibliographyOnline reading
with our online readerContent validated
by our reading committee
