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

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.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/

https://www.ort.shu.edu.cn/EN/Y2013/V17/I1/38

[1]	XU Ke, JI Lanping, GONG Hua, LIU Peng, SUN Wenjuan. A coordinated multi-agent production and transportation scheduling on parallel machines based on auction algorithm [J]. Operations Research Transactions, 2026, 30(1): 121-136.
[2]	CHEN Rongjun, LIU Yongcai, HUANG He, TANG Guochun. Dynamic programming algorithms for single machine supply chain scheduling [J]. Operations Research Transactions, 2026, 30(1): 171-178.
[3]	MENG Lanmeng, MA Ran, ZHANG Yuzhong. Single-machine online scheduling with NDP constraint and deterioration [J]. Operations Research Transactions, 2026, 30(1): 179-187.
[4]	WU Hongyi, WANG Dong, WAN Long, LUO Wenchang. Approximation algorithm for mixed batch parallel machine scheduling with nested processing set restrictions [J]. Operations Research Transactions, 2026, 30(1): 188-196.
[5]	Dawei LI, Ganggang LI. Single-machine scheduling with operator non-availability periods and deteriorating jobs [J]. Operations Research Transactions, 2025, 29(4): 14-26.
[6]	Kaiyuan JIN, Feifeng ZHENG, Ming LIU. Online scheduling model of batch processing machine considering order types and setup time [J]. Operations Research Transactions, 2025, 29(4): 231-240.
[7]	Ruiqing SUN, Rui ZHANG, Yan LAN, Weidong LI. LPT algorithm for early work maximization problem [J]. Operations Research Transactions, 2025, 29(4): 249-254.
[8]	Guohua WAN, Shan WANG, Tengfang HUANG. Appointment scheduling in service systems: A survey and extension [J]. Operations Research Transactions, 2025, 29(3): 61-76.
[9]	Wei LU, Xingyu LU, Ding ZOU, Boxiao CHEN, Yihan ZHOU, Guochuan ZHANG. Research on computing power scheduling problem and technology in green computing [J]. Operations Research Transactions, 2025, 29(3): 179-201.
[10]	Siqi GUO, Ping ZHOU, Yiwei JIANG, Min JI. Single-machine scheduling with carbon emission cost and piece-rate maintenance [J]. Operations Research Transactions, 2025, 29(2): 68-79.
[11]	Di ZHAO, Jin YU, Xiwen LU. Approximation algorithms for two-agent serial batching scheduling problems [J]. Operations Research Transactions, 2025, 29(2): 184-193.
[12]	Yuan YUAN, Yan LAN, Xin HAN. A survey of scheduling with maintenance periods [J]. Operations Research Transactions, 2025, 29(1): 1-18.
[13]	Na LI, Ran MA, Long LI, Yuzhong ZHANG. Study on the production scheduling of prefabricated components with learning effect [J]. Operations Research Transactions, 2025, 29(1): 19-30.
[14]	Tongxin CUI, Qian XIA, Xingong ZHANG. Single two-agent scheduling problems with slack due date to minimize the total weighted tardiness [J]. Operations Research Transactions, 2025, 29(1): 31-40.
[15]	Shipian DU, Manzhan GU. Stochastic scheduling to minimize the expected total number of tardy jobs with machine maintenance activities [J]. Operations Research Transactions, 2025, 29(1): 142-158.

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

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Related Articles 15

Recommended Articles

Metrics

Comments