Group scheduling with controllable setup and processing times: minimizing total weighted completion time. (English) Zbl 1119.90020
Summary: The following single machine scheduling problem is studied. A partition of a set of \(n\) jobs into \(g\) groups on the basis of group technology is given. The machine processes jobs of the same group contiguously, with a sequence independent setup time preceding the processing of each group. The setup times and the job processing times are controllable through the allocation of a continuously divisible or discrete resource to them. Each job uses the same amount of the resource. Each setup also uses the same amount of resource, which may be different from that for the jobs. Polynomial-time algorithms are constructed for variants of the problem of finding an optimal job sequence and resource values so as to minimize the total weighted job completion time, subject to given restrictions on resource consumption. The algorithms are based on a polynomial enumeration of the candidates for an optimal job sequence and solving the problem with a fixed job sequence by linear programming.
Keywords:
single machine scheduling; group technology; total weighted completion time; controllable setup and processing timesReferences:
| [1] | Aho, A.V., J.E. Hopcroft, and J.D. Ullman. (1974). The Design and Analysis of Computer Algorithms. Reading, MA: Addison-Wesley. · Zbl 0326.68005 |
| [2] | Biskup, D. and H. Jahnke. (2001). ”Common Due Date Assignment for Scheduling on a Single Machine with Jointly Reducible Processing Times.” International Journal of Production Economics 69, 317–322. · doi:10.1016/S0925-5273(00)00040-2 |
| [3] | Błazewicz, J. (1996). Scheduling Computer and Manufacturing Processes. Berlin: Springer. · Zbl 0911.90201 |
| [4] | Chen, Z.L., Q. Lu, and G. Tang. (1997). ”Single Machine Scheduling with Discretely Controllable Processing Times.” Operations Research Letters 21, 69–76. · Zbl 0888.90088 · doi:10.1016/S0167-6377(97)00010-2 |
| [5] | Cheng, T.C.E. (1998). ”Single Machine Scheduling to Minimize the Sum of Compression and Late Costs.” Naval Research Logistics 45, 67–82. · Zbl 0897.90125 · doi:10.1002/(SICI)1520-6750(199802)45:1<67::AID-NAV4>3.0.CO;2-J |
| [6] | Cheng, T.C.E. and A. Janiak. (1994). ”Resource Optimal Control in Single-Machine Scheduling with Completion Time Constraints.” IEEE Transactions on Automatic Control 39, 1243–1246. · Zbl 0816.90080 · doi:10.1109/9.293187 |
| [7] | Cheng, T.C.E. and M.Y. Kovalyov. (1995). ”Single Machine Batch Scheduling with Deadlines and Resource Dependent Processing Times.” Operations Research Letters 17, 243–249. · Zbl 0858.90073 · doi:10.1016/0167-6377(95)00011-8 |
| [8] | Cheng, T.C.E., A. Janiak, and M.Y. Kovalyov. (2001). ”Single Machine Batch Scheduling with Resource Dependent Setup and Processing Times.” European Journal of Operational Research 135, 177–183. · Zbl 1077.90525 · doi:10.1016/S0377-2217(00)00312-X |
| [9] | Conway, R.W., W.L. Maxwell, and L.W. Miller. (1967). Theory of Scheduling. Reading: Addison-Wesley. · Zbl 1058.90500 |
| [10] | Dantzig, G.B. (1963). Linear Programming and Extensions. Princeton: Princeton Univ. Press. · Zbl 0108.33103 |
| [11] | Graham, R.L. (1979). ”Optimization and Approximation in Deterministic Machine Scheduling: A Survey.” Annals of Discrete Mathematics 5, 287–326. · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X |
| [12] | Ham, I., K. Hitomy, and T. Yoshida. (1985). Group Technology: Applications to Production Management. Boston: Kluwer/Nijhoff. |
| [13] | Janiak, A. (1986). ”Time-Optimal Control in a Single Machine Problem with Resource Constraints.” Automatica 22, 745–747. · Zbl 0608.90044 · doi:10.1016/0005-1098(86)90014-2 |
| [14] | Janiak, A. (1991). ”Single Machine Scheduling Problem with a Common Deadline and Resource Dependent Release Dates.” European Journal of Operational Research 53, 317–325. · Zbl 0743.90066 · doi:10.1016/0377-2217(91)90065-4 |
| [15] | Janiak, A. and M.Y. Kovalyov. (1995). ”Single Machine Group Scheduling with Ordered Criteria.” Annals of Operations Research 57, 191–201. · Zbl 0838.90062 · doi:10.1007/BF02099697 |
| [16] | Janiak, A. and M.Y. Kovalyov. (1996). ”Single Machine Scheduling with Deadlines and Resource Dependent Processing Times.” European Journal of Operational Research 94, 284–291. · Zbl 0947.90584 · doi:10.1016/0377-2217(96)00129-4 |
| [17] | Janiak, A., M.Y. Kovalyov, and M.-C. Portmann. (2005). ”Single Machine Group Scheduling with Resource Dependent Setup and Processing Times.” European Journal of Operational Research 162, 112–121. · Zbl 1132.90325 · doi:10.1016/j.ejor.2002.11.004 |
| [18] | Janiak, A. and M.-C. Portmann. (1997). ”Minimization of the Maximum Lateness in Single Machine Scheduling with Release Dates and Additional Resources.” In Proceedings of the International Conference on Industrial Engineering and Production Management. Lyon: Book I, pp. 283–292. |
| [19] | Janiak, A., Y.M. Shafransky, and A.V. Tuzikov. (2001). ”Sequencing with Ordered Criteria, Precedence and Group Technology Constraints.” Informatica 12, 61–88. · Zbl 0994.90071 |
| [20] | Kovalyov, M.Y. and A.V. Tuzikov. (1994). ”Group Sequencing Subject to Precedence Constraints.” Applied Mathematics and Computer Science 4, 635–641. · Zbl 0837.68016 |
| [21] | Li, C.L., E.C. Sewell, and T.C.E. Cheng. (1994). ”Scheduling to Minimize Release-Time Resource Consumption and Tardiness Penalties.” Naval Research Logistics 42, 946–966. · Zbl 0845.90074 |
| [22] | Liaee, M.M. and H. Emmons. (1997). ”Scheduling Families of Jobs with Setup Times.” International Journal of Production Economics 51, 165–176. · doi:10.1016/S0925-5273(96)00105-3 |
| [23] | Liu, Z. and W. Yu. (1999). ”Minimizing the Number of Late Jobs under the Group Technology Assumption.” Journal of Combinatorial Optimization 3, 5–15. · Zbl 0967.90048 · doi:10.1023/A:1009841719644 |
| [24] | Mitrofanovo, S.P. (1966). Scientific Principles of Group Technology. Translated by E. Harris. Yorkshire: National Lending Library. |
| [25] | Opitz, H. (1970). A Classification System to Describe Workpieces: Parts I and II. Oxford: Pergamon. |
| [26] | Potts, C.N. and M.Y. Kovalyov. (2000). ”Scheduling with Batching: A Review.” European Journal of Operational Research 120, 228–249. · Zbl 0953.90028 · doi:10.1016/S0377-2217(99)00153-8 |
| [27] | Potts, C.N. and L.N. Van Wassenhove. (1991). ”Integrating Scheduling with Batching and Lot-Sizing: A Review of Algorithms and Complexity.” Journal of the Operational Research Society 43, 395–406. · Zbl 0756.90050 |
| [28] | Shallcross, D.F. (1992). ”A Polynomial Algorithm for a One Machine Batching Problem.” Operations Research Letters 11, 213–218. · Zbl 0760.90059 · doi:10.1016/0167-6377(92)90027-Z |
| [29] | Smith, W.E. (1956). ”Various Optimizers for Single-Stage Production.” Naval Research Logistics Quarterly 1, 59–66. · doi:10.1002/nav.3800030106 |
| [30] | Tuzikov, A.V. (1984). ”A Two-Criterion Scheduling Problem Allowing Variation in Job Execution.” USSR Computing Mathematics and Mathematical Physics 24, 1585–1590. · Zbl 0572.90054 |
| [31] | Van Wassenhove, L.N. and K.R. Baker. (1982). ”A Bicriterion Approach to Time/Cost Tradeoffs in Sequencing.” European Journal of Operational Research 11, 48–54. · Zbl 0482.90043 · doi:10.1016/S0377-2217(82)80008-8 |
| [32] | Vickson, R.G. (1980). ”Two Single Machine Sequencing Problems Involving Controllable Job Processing Times.” AIIE Transactions 12, 258–262. |
| [33] | Zamanskii, L.Y. and V.L. Cherkasskii. (1984). ”A Formula for Finding the Number of Integer Points under a Straight Line and Its Applications.” Economika i Matematicheskie Metodi 20, 1132–1138 (in Russian). |
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.
