Geodesic
Effective algorithms for one scheduling problem on two machines with makespan minimization
Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 4, pp. 63-79.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2015_22_4_a4,
     author = {A. A. Romanova},
     title = {Effective algorithms for one scheduling problem on two machines with makespan minimization},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {63--79},
     publisher = {mathdoc},
     volume = {22},
     number = {4},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2015_22_4_a4/}
}
TY  - JOUR
AU  - A. A. Romanova
TI  - Effective algorithms for one scheduling problem on two machines with makespan minimization
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2015
SP  - 63
EP  - 79
VL  - 22
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2015_22_4_a4/
LA  - ru
ID  - DA_2015_22_4_a4
ER  - 
%0 Journal Article
%A A. A. Romanova
%T Effective algorithms for one scheduling problem on two machines with makespan minimization
%J Diskretnyj analiz i issledovanie operacij
%D 2015
%P 63-79
%V 22
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2015_22_4_a4/
%G ru
%F DA_2015_22_4_a4
A. A. Romanova. Effective algorithms for one scheduling problem on two machines with makespan minimization. Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 4, pp. 63-79. http://geodesic.mathdoc.fr/item/DA_2015_22_4_a4/

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

[2] Apte U. M., Viswanathan S., “Effective cross docking for improving distribution efficiencies”, Int. J. Logist. Res. Appl., 3:3 (2000), 291–302 | DOI

[3] Boysen N., Fliedner M., “Cross dock scheduling: Classification, literature review and research agenda”, Omega, 38:6 (2010), 413–422 | DOI

[4] Chen F., Lee Ch.-Yee, “Minimizing the makespan in a two-machine cross-docking flow-shop problem”, Eur. J. Oper. Res., 193:1 (2009), 59–72 | DOI | MR | Zbl

[5] Chen F., Song K., “Minimizing makespan in two-stage hybrid cross docking scheduling problem”, Comput. Oper. Res., 36:6 (2009), 2066–2073 | DOI | Zbl

[6] Johnson S. M., “Optimal two- and three-stage production schedules with set-up times included”, Naval Res. Logist. Quart., 1:1 (1954), 61–68 | DOI

[7] Prot D., Rapine C., “Approximations for the two-machine cross-docking flow shop problem”, Discrete Appl. Math., 161:13–14 (2013), 2107–2119 | DOI | MR | Zbl

[8] Vahdani B., Zandieh M., “Scheduling trucks in cross-docking systems: Robust meta-heuristics”, Comput. Ind. Eng., 58:1 (2010), 12–24 | DOI