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

Meeting due dates is the most important goal of scheduling if the due date of each job has been promised to its customer. This paper considers the job-shop scheduling problem of minimizing the total holding cost of completed and in-process products subject to no tardy jobs. A heuristic algorithm based on the shifting bottleneck procedure is proposed for solving the minimum total holding cost problem subject to no tardy jobs. Several benchmark problems which are commonly used for job-shop scheduling problems of minimizing the makespan are solved by the proposed method and the results are reported.

The job-shop scheduling problem has been extensively studied with the objective of minimizing some functions of the completion times of jobs. Enumerative methods have been proposed and heuristics have been designed for solving the minimum makespan problem, the minimum total tardiness problem and so on (e.g. Adams et al., 1988; Anderson and Nyirenda, 1990; Applegate and Cook, 1991; Carlier and Pinson, 1994 and Carlier and Pinson, 1989; Liao and You, 1992; Raman and Talbot, 1993; Van Laarhoven et al., 1992; Vepsalainen and Morton, 1987). Meeting due dates is often the most important goal of scheduling, but the due-date constraints are rarely ever considered in job-shop scheduling problems. We treat due dates as deadlines and require the job-shop scheduling to meet job-specific due dates in order to avoid delay penalties including customer's bad impression, cost of lost future sales and rush shipping cost. A heuristic algorithm for solving the scheduling problem to meet due dates in a simple job-shop is developed to approximately minimize the total holding cost corresponding to the sum of product inventory cost and in-process inventory cost. The proposed method decomposes the job-shop problem into a number of single-machine problems with ready-time and due-date constraints. Each decomposed problem is strictly solved by a branch and bound (B&B) method using new due dates for each operation decided by considering to meet pre-specified due dates and minimizing objective functions, simultaneously. We used an elimination method adapted for a single-machine problem at each node to directly select some disjunctions or at least to determine whether or not a potentially global solution can be obtained. In this way, the B&B tree is trimmed efficiently. Several benchmark problems are solved by the proposed method and the results are reported.

This paper proposed a heuristic algorithm for the job-shop scheduling to minimize total holding cost of completed and in-process products subject to no tardy jobs. The proposed algorithm is based on the Shifting Bottleneck Procedure, and has the characteristics limiting the number of the generating successor nodes and solving the sub-problem as the single-machine problem with the ready-time and due-date constraints. Computation results indicate that the proposed algorithm performs well especially on the problem with tight due dates. However, the computation results are not enough to guarantee the above conclusions. The holding costs were fixed to one set of values for all the experiments. Some runs with the parameter t set to a low enough value to make it impossible to satisfy all due-date constraints were omitted. Therefore, these computational experiences should be taken under considering an algorithm which can effectively check the infeasible problems. Furthermore, some works also remain to be done to improve the selection method of successor nodes and/or generating nodes in order to reduce the computation times further.