Scheduling with batching: Minimizing the weighted number of tardy jobs. (English) Zbl 0820.90052
Summary: The weighted tardiness with batching (WTB) problem can be briefly described as follows: given \(n\) jobs, each with a processing time, a weight, and a due date, and given a batch setup time, find a sequence of batches that minimizes the weighted number of tardy jobs. We show that the decision version of WTB is NP-complete, but that it can be solved in pseudo-polynomial time by a dynamic programming algorithm. We also analyze various restricted versions of the problem generated by requiring that one or more of the job parameters (weight, processing time, or due date) is the same for all jobs. For each such version of the problem, we prove NP-completeness or provide a polynomial algorithm.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
Keywords:
semiconductor manufacturing; weighted tardiness with batching; processing time; due date; pseudo-polynomial time; NP-completenessReferences:
| [1] | Albers, S.; Brucker, P., The complexity of one-machine batching problems, Discrete Appl. Math., 47, 87-107 (1993) · Zbl 0792.90035 |
| [2] | Brucker, P., Scheduling problems in connection with flexible production systems, (Proc. 1991 IEEE Int. Conf. on Robotics and Automation (1991)), 1778-1783 |
| [3] | Bruno, J.; Downey, P., Complexity of task sequencing with deadlines, set-up times and changeover costs, SIAM J. Comput., 7, 393-404 (1978) · Zbl 0386.68050 |
| [4] | Coffman, E.; Nozari, A.; Yannakakis, M., Optimal scheduling of products with two subassemblies on a single machine, Oper. Res., 37, 426-436 (1989) · Zbl 0672.90075 |
| [5] | Coffman, E.; Yannakakis, M.; Magazine, M.; Santos, C., Batch sizing and sequencing on a single machine, Ann. Oper. Res., 26, 135-147 (1990) · Zbl 0712.90035 |
| [6] | Dobson, G.; Karmarkar, U. S.; Rummel, J. L., Batching to minimize flow times on one machine, Management Sci., 33, 784-799 (1987) · Zbl 0624.90047 |
| [7] | Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York), 85-103 · Zbl 0366.68041 |
| [8] | Lawler, E.; Moore, J., A functional equation and its application to resource allocation and sequencing problems, Management Sci., 16, 77-84 (1969) · Zbl 0184.23303 |
| [9] | Naddef, D.; Santos, C., One-pass batching algorithms for the one machine problem, Discrete Appl. Math., 21, 133-145 (1988) · Zbl 0661.90044 |
| [10] | Shallcross, D., A polynomial algorithm for a one machine batching problem, Oper. Res. Lett., 11, 213-218 (1992) · Zbl 0760.90059 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
