×

Total completion time minimization in two-machine flow shop scheduling problems with a fixed job sequence. (English) Zbl 1242.90077

Summary: This paper addresses scheduling n jobs in a two-machine flow shop to minimize the total completion time, subject to the condition that the jobs are processed in the same given sequence on both machines. A new concept of optimal schedule block is introduced, and polynomial time dynamic programming algorithms employing this concept are derived for two specific problems. In the first problem, the machine-2 processing time of a job is a step increasing function of its waiting time between the machines, and a decision about machine-1 idle time insertion has to be made. This problem is solved in \(O(n^{2})\) time. In the second problem, the jobs are processed in batches and each batch is preceded by a machine-dependent setup time. An \(O(n^{5})\) algorithm is developed to find an optimal batching decision.

MSC:

90B35 Deterministic scheduling theory in operations research
90C39 Dynamic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Kanet, J. J.; Sridharan, V., Scheduling with inserted idle time: problem taxonomy and literature review, Operations Research, 48, 1, 99-110 (2000)
[2] Potts, C. N.; Kovalyov, M. Y., Scheduling with batching: a review, European Journal of Operational Research, 120, 2, 228-249 (2000) · Zbl 0953.90028
[3] Shafransky, Y. M.; Strusevich, V. A., The open shop scheduling problem with a given sequence of jobs on one machine, Naval Research Logistics, 45, 7, 705-731 (1998) · Zbl 0936.90029
[4] Hendel, Y.; Sourd, F., An improved earliness-tardiness timing algorithm, Computers & Operations Research, 34, 10, 2931-2938 (2007) · Zbl 1185.90077
[5] Garey, M. R.; Tarjan, R. E.; Wilfong, G. T., One processor scheduling with symmetrical earliness and tardiness penalties, Mathematics of Operations Research, 13, 2, 330-348 (1988) · Zbl 0671.90033
[6] Davis, J. S.; Kanet, J. J., Single-machine scheduling with early and tardy completion costs, Naval Research Logistics, 40, 1, 85-101 (1993) · Zbl 0769.90048
[7] Szwarc, W.; Mukhopadhyay, S. K., Optimal timing schedules in earliness-tardiness single machine sequencing, Naval Research Logistics, 42, 7, 1109-1114 (1995) · Zbl 0841.90078
[8] Sourd, F., Optimal timing of a sequence of tasks with general completion costs, European Journal of Operational Research, 165, 1, 82-96 (2005) · Zbl 1112.90340
[9] Pan, Y.; Shi, L., Dual constrained single machine sequencing to minimize total weighted completion time, IEEE Transactions on Automation Science and Engineering, 2, 4, 344-357 (2005)
[10] Colina, E. C.; Quinino, R. C., An algorithm for insertion of idle time in the single-machine scheduling problem with convex cost functions, Computers & Operations Research, 32, 9, 2285-2296 (2005) · Zbl 1116.90347
[11] Bauman, J.; Józefowska, J., Minimizing the earliness-tardiness costs on a single machine, Computers & Operations Research, 33, 11, 3219-3230 (2006) · Zbl 1113.90057
[12] Della Croce, F.; Trubian, M., Optimal idle time insertion in early-tardy parallel machines scheduling with precedence constraints, Production Planning & Control, 13, 2, 133-142 (2002)
[13] Lin, B. M.T.; Cheng, T. C.E., Two-machine flowshop scheduling with conditional deteriorating second operations, International Transactions in Operational Research, 13, 2, 91-98 (2006) · Zbl 1127.90031
[14] Cheng, T. C.E.; Ding, Q.; Lin, B. M.T., A concise survey of scheduling with time-dependent processing times, European Journal of Operational Research, 152, 1, 1-13 (2004) · Zbl 1030.90023
[15] Cheng, T. C.E.; Lin, B. M.T.; Toker, A., Makespan minimization in the two-machine flowshop batch scheduling problem, Naval Research Logistics, 47, 2, 128-144 (2000) · Zbl 0973.90031
[16] Ng, C. T.; Kovalyov, M. Y., Batching and scheduling in a multi-machine flow shop, Journal of Scheduling, 10, 6, 353-364 (2007) · Zbl 1153.90431
[17] Cheng, T. C.E.; Wang, G., Scheduling the fabrication and assembly of components in a two-machine flowshop, IIE Transactions, 31, 2, 135-143 (1999)
[18] Lin, B. M.T.; Cheng, T. C.E.; Chou, A. S.C, Scheduling in an assembly-type production chain with batch transfer, Omega, 35, 2, 143-151 (2007)
[19] F.J. Hwang, B.M.T. Lin, Two-stage assembly-type flowshop batching problem subject to a fixed job sequence, Journal of the Operational Research Society (2011), in press (doi:10.1057/jors.2011.90; F.J. Hwang, B.M.T. Lin, Two-stage assembly-type flowshop batching problem subject to a fixed job sequence, Journal of the Operational Research Society (2011), in press (doi:10.1057/jors.2011.90
[20] Lin, B. M.T.; Cheng, T. C.E., Scheduling with centralized and decentralized batching policies in concurrent open shops, Naval Research Logistics, 58, 1, 17-27 (2011) · Zbl 1210.90091
[21] Glass, C. A.; Potts, C. N.; Strusevich, A. V., Scheduling batches with sequential job processing for two-machine flow and open shops, INFORMS Journal on Computing, 13, 2, 120-137 (2001) · Zbl 1238.90064
[22] Kovalyov, M. Y.; Potts, C. N.; Strusevich, V. A., Batching decisions for assembly production systems, European Journal of Operational Research, 157, 3, 620-642 (2004) · Zbl 1067.90044
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.