ابتکاری برای برنامه ریزی تولید کارگاهی برای به حداقل رساندن تاخیر وزن کل

This paper considers the job shop scheduling problem to minimize the total weighted tardiness with job-specific due dates and delay penalties, and a heuristic algorithm based on the tree search procedure is developed for solving the problem. A certain job shop scheduling to minimize the maximum tardiness subject to fixed sub-schedules is solved at each node of the search tree, and the successor nodes are generated, where the sub-schedules of the operations are fixed. Thus, a schedule is obtained at each node, and the sub-optimum solution is determined among the obtained schedules. Computational results on some 10 jobs and 10 machines problems and 15 jobs and 15 machines problems show that the proposed algorithm can find the sub-optimum solutions with a little computation time.

We consider the minimum total weighted tardiness problem of job shop scheduling with job-specific due dates and delay penalties. A delay penalty is charged if a job is completed after its due date that has been promised to a customer. This penalty is assumed to be constant over time and includes cost of lost future sales or changed orders and rush shipping cost. The minimum total weighted tardiness problem in a job shop is NP hard in a strong sense, and some priority dispatching rules have been suggested. For example, Vepsalainen and Morton (1987) presented the apparent tardiness cost (ATC) rule. Anderson and Nyirenda (1990) showed two kinds of rules that combine two dispatching rules. On the other hand, Singer and Pinedo (1998) have presented a branch and bound algorithm. It is important to explore the ways of obtaining the optimum schedule. However, the enumerative methods are computation time intensive, and typically limited to cases with no more than 10 jobs and 10 machines. Pinedo and Singer (1999) have shown a heuristic, which is based on the shifting bottleneck procedure (SBP) proposed by Adams, Balas, and Zawack (1988). Their heuristic yielded the solutions that are close to optimum on some 10 jobs and 10 machines problems. However, the performance of their heuristic depends on the setting of the two control parameters. A heuristic algorithm based on the tree search procedure for solving the minimum total weighted tardiness problem is developed in this paper to obtain a sub-optimum solution with a little computation time without setting any control parameter. A certain job shop scheduling to minimize the maximum tardiness subject to fixed sub-schedules is solved at each node of the search tree in the proposed algorithm. The longest path for every tardy job at a searching node is found, and the sub-schedule of every operation on the longest path of a tardy job is fixed at each successor node. Some conditions to stop a node are also considered to improve the efficiency of searching. Thus, a schedule is obtained at each node, and the sub-optimum solution is determined among the obtained schedules.

This paper proposed a heuristic algorithm for solving the job shop scheduling to minimize the total weighted tardiness. The proposed algorithm is based on the tree search procedure, and does not require any parameter estimation for its implementation. Some computational results showed that the proposed algorithm can find a sub-optimum solution with a little computation time. Some works remain to be done to improve the method for solving the mini–max tardiness problem subject to fixed sub-schedules, and thus the better solution will be obtained with a less computational time.