带批运输的两台同型机排序问题的改进算法

Operations Research Transactions ›› 2013, Vol. 17 ›› Issue (1): 38-43.

• Original Articles • Previous Articles Next Articles

An improved algorithm for scheduling two identical machines with batch delivery consideration

WANG Leiyang¹, LIU Zhaohui¹

1. Department of Mathematics, East China University of Science and Technology

Online:2013-03-15 Published:2013-03-15

Abstract

Abstract: In this paper we consider the scheduling problem on two identical (parallel) machines in which the finished jobs need to be delivered to a customer in batches by single vehicle. The goal is to minimize the makespan, i.e., the time by which the vehicle has delivered the last job and returned to the machines. We assume that the jobs have different sizes, and give an approximation algorithm with the worst-case performance ratio(14/9+ε).

Key words: scheduling, batch delivery, approximation algorithm

WANG Leiyang, LIU Zhaohui. An improved algorithm for scheduling two identical machines with batch delivery consideration[J]. Operations Research Transactions, 2013, 17(1): 38-43.

[1]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[2]	CHEN Rubing, YUAN Jinjiang. Single-machine scheduling to minimize total weighted late work with positional due-indices [J]. Operations Research Transactions, 2020, 24(2): 131-144.
[3]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.
[4]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[5]	GOU Yan, DAI Qin, ZHANG Xingong. Scheduling problem with time-and-position-dependent effect on two parallel machines environments [J]. Operations Research Transactions, 2019, 23(4): 86-94.
[6]	LI Ganggang, LU Xiwen. An improved algorithm for single-machine scheduling problem with a period of maintenance to minimize total delivery time [J]. Operations Research Transactions, 2019, 23(4): 95-104.
[7]	LI Wenhua, ZHAI Weina, CHAI Xing, GAO Chao. On-line bounded-batching scheduling of unit-length jobs with two families [J]. Operations Research Transactions, 2019, 23(4): 105-110.
[8]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[9]	ZHONG Weiya, YANG Ruoyao. Scheduling with sub-jobs' due dates [J]. Operations Research Transactions, 2019, 23(2): 67-74.
[10]	CHEN Qiuhong, ZHANG Xingong. Two-agent preemptive scheduling of jobs with fixed time windows problem about total tardiness on a single machine [J]. Operations Research Transactions, 2019, 23(1): 61-71.
[11]	PENG Nannan, ZHANG Yuzhong, BAI Qingguo, WANG Chengfei. Online batch scheduling problem on uniform machines with agreeable processing times [J]. Operations Research Transactions, 2019, 23(1): 111-118.
[12]	CAI Shuang, YANG Ke, LIU Ke. Model and algorithms of the distributed permutation flow shop scheduling problem with machine eligibility constraints [J]. Operations Research Transactions, 2018, 22(4): 17-30.
[13]	JIANG Yanjun, XU Dachuan, ZHANG Dongmei. An approximation algorithm for the squared metric dynamic facility location problem [J]. Operations Research Transactions, 2018, 22(3): 49-58.
[14]	ZHAO Xiaocheng, LI Dagang. Parallel machine scheduling with machine and human eligibility restrictions [J]. Operations Research Transactions, 2018, 22(3): 99-108.
[15]	LI Ying, QIAO Longliang, ZHENG Feifeng. A study of online berth and quay crane integrated allocation problem with lookahead ability [J]. Operations Research Transactions, 2018, 22(3): 28-36.

An improved algorithm for scheduling two identical machines with batch delivery consideration

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments