Abstract
We consider in this paper a two-machine flowshop scheduling problem in which the first machine processes jobs individually while the second machine processes jobs in batches. The forming of each batch on the second machine incurs a constant setup time. The objective is to minimize the makespan. This problem was previously shown to be NP-hard in the ordinary sense. In this paper, we first present a strong NP-hardness result of the problem. We also identify a polynomially solvable case with either anticipatory or non-anticipatory setups. We then establish a property that an optimal solution for the special case is a lower bound for the general problem. To obtain near-optimal solutions for the general problem, we devise some heuristics. The lower bound is used to evaluate the quality of the heuristic solutions. Results of computational experiments reveal that the heuristics produce solutions with small error ratios. They also suggest that the lower bound is close to the optimal solution.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahmadi, J.H., R.H. Ahmadi, S. Dasu, and C.S. Tang. (1992). “Batching and Scheduling on Batch and Discrete Processors.” Operations Research 40, 750–763.
Albers, A. and P. Brucker. (1993). “The Complexity of One-Machine Batching Problem.” Discrete Applied Mathatmematics 47, 87–107.
Allahverdi, A., J.N.D. Gupta, and T. Aldowaisan. (1999). “A Review of Scheduling Research Involving Setup Considerations.” Omega 27, 219–239.
Cheng, T.C.E., Z.-L. Chen, M.Y. Kovalyov, and B.M.T. Lin. (1996). “Parallel-Machine Batching and Scheduling to Minimize Total Completion Time.” IIE Transactions 28, 953–956.
Cheng, T.C.E., J.N.D. Gupta, and G. Wang. (2000). “A Review of Flowshop Scheduling Research with Setup Times.” Production and Operations Management 9, 262–282.
Cheng, T.C.E., M.Y. Kovalyov, and B.M.T. Lin. (1997). “Single Machine Scheduling to Minimize Batch Delivery and Job Earliness Penalties.” SIAM Journal on Optimization 7, 547–559.
Cheng, T.C.E., B.M.T. Lin, and A. Toker. (2000). “Makespan Minimization in the Two-Machine Flowshop Batch Scheduling Problem.” Naval Research Logistics 47, 128–144.
Cheng, T.C.E. and G. Wang. (1998). “Batching and Scheduling to Minimize the Makespan in the Two-Machine Flowshop.” IIE Transactions 30, 447–453.
Coffmann, E.G., A. Nozari, and M. Yannakakis. (1989). “Optimal Scheduling of Products with Two Subassemblies on a Single Machine.” Operations Research 37, 426–436.
Garey, M.R. and D.S. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: Freeman.
Glass, C.A., C.N. Potts, and A.V. Strusevich. (2001). “Scheduling Batches with Sequential Job Processing for Two-Machine Flow and Open Shops.” INFORMS Journal on Computing 13, 120–137.
Johnson, S.M. (1954). “Optimal Two- and Three-Stage Production Schedules with Setup Times Included.” Naval Research Logistics Quarterly 1, 61–67.
Lin, B.M.T. and J.M. Wu. (2002). “A New Lower Bound Scheme for the Two-Machine Flowshop Scheduling to Minimize the Total Completion Time.” In Electronic Proceedings of the Fourth Asia-Pacific Conference on Industrial Engineering and Management Systems, Taipei, Taiwan, December 2002.
Naddef, D. and C. Santos. (1988). “One-Pass Batching Algorithms for the One-Machine Problem.” Discrete Applied Matthematics 21, 133–146.
Potts, C.N. and M.K. Kovalyov. (2000). “Scheduling with Batching: A Review.” European Journal of Operational Research 102, 228–249.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lin, B.M.T., Cheng, T.C.E. Two-Machine Flowshop Batching and Scheduling. Ann Oper Res 133, 149–161 (2005). https://doi.org/10.1007/s10479-004-5029-7
Issue Date:
DOI: https://doi.org/10.1007/s10479-004-5029-7