Volume 22, No 4, 2015, P. 63-79

UDC 519.2+621.391
Romanova A. A.
Effective algorithms for one scheduling problem on two machines with makespan minimization

Abstract:
We consider an NP-hard problem of scheduling a set of jobs of equal processing time on two machines, given a partial precedence order between the jobs, with an objective to minimize the makespan. An approximation algorithm with performance guarantee is proposed for this problem. Polynomial solvability of the problem is proved in the case when each job on the first machine is in precedence relation with two jobs on the second machine.
Ill. 9, bibliogr. 8. 

Keywords: cross-docking problem, schedule, partial order, approximation algorithm.

DOI: 10.17377/daio.2015.22.483

Anna A. Romanova ^1,2
1. Omsk Law Academy,
12 Korolenko St., 644010 Omsk, Russia
2. Omsk State University,
55-a Mir Ave., 644077 Omsk, Russia
e-mail: anna.a.r@bk.ru

Received 17 March 2015
Revised 6 May 2015

References

[1] A. A. Romanova and I. B. Cheredova, The scheduling problem for two machines with partial precedence order, in Tr. V Mezhdunarodnoi aziatskoi shkoly-seminara “Problemy optimizatsii slozhnykh sistem” (Proc. V Int. Asian School-Seminar “Optimization Problems of Complex Systems”), Bishkek, Kyrgyzstan, Aug. 12–22, 2009, pp. 119–124, Inst. Vychisl. Mat. Mat. Geofiz., Novosibirsk, 2009.

[2] U. M. Apte and S. Viswanathan, Effective cross docking for improving distribution efficiencies, Int. J. Logist., Res. Appl., 3, No. 3, 291–302, 2000.

[3] N. Boysen and M. Fliedner, Cross dock scheduling: Classification, literature review and research agenda, Omega, 38, No. 6, 413–422, 2010.

[4] F. Chen and Ch.-Yee Lee, Minimizing the makespan in a two-machine cross-docking flow shop problem, Eur. J. Oper. Res., 193, No. 1, 59–72, 2009.

[5] F. Chen and K. Song, Minimizing makespan in two-stage hybrid cross docking scheduling problem, Comput. Oper. Res., 36, No. 6, 2066–2073, 2009.

[6] S. M. Johnson, Optimal two- and three-stage production schedules with setup times included, Nav. Res. Logist. Q., 1, No. 1, 61–68, 1954.

[7] D. Prot and C. Rapine, Approximations for the two-machine cross-docking flow shop problem, Discrete Appl. Math., 161, No. 13–14, 2107–2119, 2013.

[8] B. Vahdani and M. Zandieh, Scheduling trucks in cross-docking systems: Robust meta-heuristics, Comput. Ind. Eng., 58, No. 1, 12–24, 2010.