Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aho, A.V., J.E. Hopcroft, and J.D. Ullman. (1974). The Design and Analysis of Computer Algorithms. Reading, MA: Addison-Wesley.
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.
Błazewicz, J. (1996). Scheduling Computer and Manufacturing Processes. Berlin: Springer.
Chen, Z.L., Q. Lu, and G. Tang. (1997). “Single Machine Scheduling with Discretely Controllable Processing Times.” Operations Research Letters 21, 69–76.
Cheng, T.C.E. (1998). “Single Machine Scheduling to Minimize the Sum of Compression and Late Costs.” Naval Research Logistics 45, 67–82.
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.
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.
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.
Conway, R.W., W.L. Maxwell, and L.W. Miller. (1967). Theory of Scheduling. Reading: Addison-Wesley.
Dantzig, G.B. (1963). Linear Programming and Extensions. Princeton: Princeton Univ. Press.
Graham, R.L. (1979). “Optimization and Approximation in Deterministic Machine Scheduling: A Survey.” Annals of Discrete Mathematics 5, 287–326.
Ham, I., K. Hitomy, and T. Yoshida. (1985). Group Technology: Applications to Production Management. Boston: Kluwer/Nijhoff.
Janiak, A. (1986). “Time-Optimal Control in a Single Machine Problem with Resource Constraints.” Automatica 22, 745–747.
Janiak, A. (1991). “Single Machine Scheduling Problem with a Common Deadline and Resource Dependent Release Dates.” European Journal of Operational Research 53, 317–325.
Janiak, A. and M.Y. Kovalyov. (1995). “Single Machine Group Scheduling with Ordered Criteria.” Annals of Operations Research 57, 191–201.
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.
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.
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.
Janiak, A., Y.M. Shafransky, and A.V. Tuzikov. (2001). “Sequencing with Ordered Criteria, Precedence and Group Technology Constraints.” Informatica 12, 61–88.
Kovalyov, M.Y. and A.V. Tuzikov. (1994). “Group Sequencing Subject to Precedence Constraints.” Applied Mathematics and Computer Science 4, 635–641.
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.
Liaee, M.M. and H. Emmons. (1997). “Scheduling Families of Jobs with Setup Times.” International Journal of Production Economics 51, 165–176.
Liu, Z. and W. Yu. (1999). “Minimizing the Number of Late Jobs under the Group Technology Assumption.” Journal of Combinatorial Optimization 3, 5–15.
Mitrofanovo, S.P. (1966). Scientific Principles of Group Technology. Translated by E. Harris. Yorkshire: National Lending Library.
Opitz, H. (1970). A Classification System to Describe Workpieces: Parts I and II. Oxford: Pergamon.
Potts, C.N. and M.Y. Kovalyov. (2000). “Scheduling with Batching: A Review.” European Journal of Operational Research 120, 228–249.
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.
Shallcross, D.F. (1992). “A Polynomial Algorithm for a One Machine Batching Problem.” Operations Research Letters 11, 213–218.
Smith, W.E. (1956). “Various Optimizers for Single-Stage Production.” Naval Research Logistics Quarterly 1, 59–66.
Tuzikov, A.V. (1984). “A Two-Criterion Scheduling Problem Allowing Variation in Job Execution.” USSR Computing Mathematics and Mathematical Physics 24, 1585–1590.
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.
Vickson, R.G. (1980). “Two Single Machine Sequencing Problems Involving Controllable Job Processing Times.” AIIE Transactions 12, 258–262.
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).
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was supported in part by The Hong Kong Polytechnic University under grant number G-T246 and the Research Grants Council of Hong Kong under grant number PolyU 5191/01E. In addition, the research of M.Y. Kovalyov was supported by INTAS under grant number 00-217.
Rights and permissions
About this article
Cite this article
Ng, C.T., Cheng, T.C.E., Janiak, A. et al. Group Scheduling with Controllable Setup and Processing Times: Minimizing Total Weighted Completion Time. Ann Oper Res 133, 163–174 (2005). https://doi.org/10.1007/s10479-004-5030-1
Issue Date:
DOI: https://doi.org/10.1007/s10479-004-5030-1