×

A polynomial algorithm for lot-size scheduling of two type tasks. (English) Zbl 1051.68142

Summary: We study the problem of scheduling unit time tasks of two types on \(m\) parallel identical machines. For each type, given numbers of tasks are required to be completed by the specified deadlines. These tasks leave the system at the deadlines. The in-process inventory capacities are given. The objective is to construct a schedule that minimizes the number of changeovers occurring between the tasks of different types. This problem arises, for instance, in the production of gear-boxes on transfer lines and in the tobacco industry. M. Pattloch and G. Schmidt [Discrete Appl. Math. 65, 409–419 (1996; Zbl 0846.90052)] give an \(O(mH)\) algorithm to solve this problem where \(H\) is the latest deadline. We present here a modification of that algorithm with \(O(K\min\{K,m\})\) time complexity where \(K\) is the number of deadlines.

MSC:

68W05 Nonnumerical algorithms
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B35 Deterministic scheduling theory in operations research

Citations:

Zbl 0846.90052
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allahverdi, A.; Gupta, J. N.D.; Aldowaisan, T., A review of scheduling research involving setup considerations, Omega, 27, 219-239 (1999)
[2] Blocher, J. D.; Chand, S., A forward branch-and-search algorithm and forecast horizon results for the changeover scheduling problem, European J. Oper. Res., 91, 456-470 (1996) · Zbl 0918.90081
[3] Brucker, P.; Kovalyov, M. Y.; Shafransky, Y. M.; Werner, F., Batch scheduling with deadlines on parallel machines, Ann. Oper. Res., 83, 23-40 (1998) · Zbl 0913.90160
[4] 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
[5] Clifford, J. J.; Posner, M. E., High multiplicity in earliness-tardiness scheduling, Oper. Res., 48, 788-800 (2000) · Zbl 1106.90330
[6] Clifford, J. J.; Posner, M. E., Parallel machine scheduling with high multiplicity, Math. Programming, Ser. A, 89, 359-383 (2001) · Zbl 0978.90044
[7] Driscoll, W.; Emmons, H., Scheduling production on one machine with change-over costs, AIIE Trans., 9, 388-395 (1977)
[8] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Co.: W.H. Freeman and Co. San Francisco, CA · Zbl 0411.68039
[9] Glassey, C. R., Minimum change-over scheduling of several products on one machine, Oper. Res., 16, 342-352 (1968) · Zbl 0186.24902
[10] Hochbaum, D. S.; Shamir, R., Minimizing the number of tardy job units under release time constraints, Discrete Appl. Math., 28, 45-57 (1990) · Zbl 0707.90049
[11] Hochbaum, D. S.; Shamir, R., Strongly polynomial algorithms for the high multiplicity scheduling problem, Oper. Res., 39, 648-653 (1991) · Zbl 0736.90043
[12] Hu, T. C.; Kuo, Y. S.; Ruskey, F., Some optimum algorithms for scheduling problems with changeover costs, Oper. Res., 35, 94-99 (1987) · Zbl 0621.90038
[13] Kovalyov, M. Y.; Shafransky, Y. M., Uniform machine scheduling of unit-time jobs subject to resource constraints, Discrete Appl. Math., 84, 253-257 (1998) · Zbl 0908.90167
[14] Magnanti, T. L.; Vachani, R., A strong cutting plane algorithm for production scheduling with changeover costs, Oper. Res., 38, 456-473 (1990) · Zbl 0707.90047
[15] Mitsumori, S., Optimal production scheduling of multicommodity in flow line, IEEE Trans. Syst. Man Cybernet., 2, 486-493 (1972) · Zbl 0241.90028
[16] Pattloch, M.; Schmidt, G., Lot-size scheduling of two types of jobs on identical machines, Discrete Appl. Math., 65, 409-419 (1996) · Zbl 0846.90052
[17] Pattloch, M.; Schmidt, G.; Kovalyov, M. Y., Heuristic algorithms for lotsize scheduling with application in the tobacco industry, Comput. Industrial Engrg., 39, 235-253 (2001)
[18] Potts, C. N.; Kovalyov, M. Y., Scheduling with batching: A review, European J. Oper. Res., 120, 228-249 (2000) · Zbl 0953.90028
[19] Potts, C. N.; Van Wassenhove, L. N., Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity, J. Oper. Res. Soc., 43, 395-406 (1992) · Zbl 0756.90050
[20] Timkovsky, V. G., A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem, Discrete Appl. Math., 77, 185-200 (1997) · Zbl 0879.68011
[21] Rinnooy Kan, A. H.G., Machine Scheduling Problems (1976), Martinus Nijhoff: Martinus Nijhoff The Hague · Zbl 0309.90026
[22] Salomon, M., Deterministic Lotsizing Models for Production Planning. Deterministic Lotsizing Models for Production Planning, Lecture Notes in Economics and Mathematical Systems, 355 (1991), Springer: Springer Berlin · Zbl 0761.90054
[23] Shallcross, D. F., A polynomial algorithm for a one machine batching problem, Oper. Res. Lett., 11, 213-218 (1992) · Zbl 0760.90059
[24] Webster, S. T., A note on “Parallel machine scheduling with batch setup times”, Oper. Res., 46, 423 (1998) · Zbl 0996.90046
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.