Abstract
Minimizing total completion time ∑ C j on normal batching machine is solvable in polynomial time for fixed B(B > 1), while Minimizing total completion time ∑ C j for arbitrary B and minimizing total weighted completion time ∑ W j C j are open problems. In this paper, we consider the problem of scheduling jobs on a flexible batching machine in order to minimizing the total completion time. We prove that the problem is strongly NP-hard. Then the problem with agreeable is NP-hard even if there have three fixed capacities all the time.
Supported by the National Natural Science Foundation of China (No. 10371071 and 70618001) and Shanghai Municipal Education Commission Address (No. 07zz178).
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ahmadi, J.H., Almadi, R.H., Dasu, S., Tang, C.S.: Batching and Jobs on Batch and Discrete Processors. Operations Research 40, 750–763 (1992)
Brucker, P., Gladky, S., Hoogeveen, H., Kovalyov, M., Potts, C., Tantenhahn, T., van de Velde, S.: Scheduling a batching machine. Journal of Scheduling 1, 31–54 (1998)
Chandru, V., Lee, C.-Y., Uzsoy, R.: Minimizing total completion time on batch processing machines. International Journal of Production Research 31, 2097–2122 (1993)
Chandru, V., Lee, C.-Y., Uzsoy, R.: Minimizing total completion time on batch processing machines. Operations Research Letter 13, 61–65 (1993)
Coffman Jr., E., Nozari, A., Yannakakis, M.: Optimal Scheduling of Products with Two Subassemblies of a Single Machine. Operations Research 37, 426–436 (1989)
Fan, B., Tang, G.: Scheduling Jobs on a Flexible Batching Machine: Model, Complexity and Algorithms. In: Cai, J.-Y., Cooper, S.B., Li, A. (eds.) TAMC 2006. LNCS, vol. 3959, pp. 118–127. Springer, Heidelberg (2006)
Garey, M.R., Johnson, D.S.: Computers and intactability: A guide to the theory of NP-completeness. Freeman, New York (1979)
Hochbaum, D.S., Landy, D.: Scheduling semiconductor burn-in operations to minimize total flowtime. Operations Research 45, 874–885 (1997)
Ikura, Y., Gimple, M.: Efficient scheduling algorithms for a single batch processing machine. Operations Research Letter 5, 61–65 (1986)
Julien, F., Magazine, M.: Batching and Scheduling Multi-Job Orders. CORS/TIMS/ORSA Vancouver Bulletin (1989)
Lee, C.-Y., Uzsoy, R., Martin-Vega, L.A.: Efficient Algorithms for Scheduling Semiconductor Burn-in Operations. Operations Research 40(4), 764–775 (1992)
Potts, C.N., Kovalyov, M.Y.: Scheduling with batching: a review. European Journal of Operational Research 120, 228–249 (2000)
Poon, C.K., Yu, W.: On minimizing total completion time in batch machine scheduling. International Journal of Foundations of Computer Science 15(4), 593–604 (2004)
Santos, C., Magazine, M.: Batching in Single Operation Manufacturing Syatem. Operations Research Letter 4, 99–103 (1985)
Tang, C.S.: Scheduling Batches on Parallel Machines with Major and Minor Setups. European Journal of Operational Research 46, 28–37 (1990)
Tang, G., Zhang, F., Luo, S., Liu, L.: Theory of Modern Scheduling. Popular Science Press, Shanghai (2003)
Vickson, R.G., Magazine, M.J., Santos, C.A.: Batching and Scheduling of Components at a Single Facility. Working Paper 185-MS-1989, University of Waterloo, Canada (1989)
Webster, S., Baker, K.R.: Scheduling Groups of Jobs on a Single Machine. Operations Research 43, 692–703 (1995)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Fan, B., Gu, J., Tang, G. (2007). Scheduling a Flexible Batching Machine. In: Kao, MY., Li, XY. (eds) Algorithmic Aspects in Information and Management. AAIM 2007. Lecture Notes in Computer Science, vol 4508. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72870-2_9
Download citation
DOI: https://doi.org/10.1007/978-3-540-72870-2_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72868-9
Online ISBN: 978-3-540-72870-2
eBook Packages: Computer ScienceComputer Science (R0)