| 带有机器维修和两车辆派送的单机排序问题 |
| |
| 引用本文： | 蔡伟,杨梅. 带有机器维修和两车辆派送的单机排序问题[J]. 运筹与管理, 2022, 31(11): 72-76. DOI: 10.12005/orms.2022.0355 |
| |
| 作者姓名： | 蔡伟 杨梅 |
| |
| 作者单位： | 1.南京审计大学金审学院 基础教学部,江苏 南京 210046; 2.中国石油大学(北京)克拉玛依校区文理学院,新疆克拉玛依 834000 |
| |
| 基金项目： | 江苏高校哲学社会科学研究一般项目(2021SJA2279);南京审计大学金审学院校级课题(JSXJKT2012) |
| |
| 摘 要： | 研究了带有机器维修和工件派送的单机排序问题，该问题可以被视为一个集成生产和出站配送的排序模型。不同体积的工件需要在带有一个维修区间的机器上加工，且加工不可中断，然后由固定容量的两辆同类车批次交付给单客户，目标函数是极小化最大完工时间，本文提出了2-近似算法，并证明了2是紧界。
|
| 关 键 词： | 单机排序 机器维修 工件派送 近似算法 最坏情况分析 |
| 收稿时间： | 2020-11-10 |
Single Machine Scheduling with a Maintenance Interval and Two Vehicles DeliveryCoordination |
| |
| CAI Wei,YANG Mei. Single Machine Scheduling with a Maintenance Interval and Two Vehicles DeliveryCoordination[J]. Operations Research and Management Science, 2022, 31(11): 72-76. DOI: 10.12005/orms.2022.0355 |
| |
| Authors: | CAI Wei YANG Mei |
| |
| Affiliation: | 1. Basic Teaching Department, Nanjing Audit University Jinshen College, Nanjing 210046, China; 2. College of Arts and Sciences, China University of Petroleum——Beijing at Karamay, Karamay 834000, China |
| |
| Abstract: | This paper investigates a single machine scheduling problem with a maintenance interval and job delivery coordination. The problem can also be viewed as an integrated production and outbound distribution scheduling model. Each job needs to be processed without preemption on the single machine with a maintenance, which demands different amount of storage space during transportation. After processing in the manufacturing center, they need to be delivered to a customer by two homogeneous vehicles with a limited load capacity in batches in the distribution center. The goal is minimize the makespan. We present a 2-approximation algorithm for the case, and also, we show that the performance ratio is tight. |
| |
| Keywords: | single machine scheduling machine maintenance job delivery approximation algorithm worst-case performance analysis |
|
| 点击此处可从《运筹与管理》浏览原始摘要信息 |
|
点击此处可从《运筹与管理》下载免费的PDF全文 |
