单机分批加工最大迟后问题的一个多项式时间算法

Journal of Applied Sciences ›› 1998, Vol. 16 ›› Issue (1): 18-23.

• Articles • Previous Articles Next Articles

A Polynomial Time Algorithm for Maximum Lateness in Single Machine Scheduling with Batching

SUN SHIJIE¹, ANDREWS BOADI¹, LIU ZHAOHUI²

1. Shanghai Institute on Applied Mathematics and Computation, Shanghai 201800;
2. East China University of Science and Technology, Shanghai 200237

Received:1996-03-01 Revised:1996-12-19 Online:1998-03-31 Published:1998-03-31

Abstract

Abstract: N jobs arrive at same time and need to be processed in batches by the same machine. The jobs in the same batch are processed successively and the completion time of all the jobs in the same batch is defined as the completion time of the batch they belong to. There exists a set up time whenever the machine begins to process a new batch. Taking the maximum lateness as objective function, this paper develops a polynomial time algorithms for the processing sequence of the n jobs given or not given.

Key words: batch, polynomial time algorithm, scheduling, maximum lateness

SUN SHIJIE, ANDREWS BOADI, LIU ZHAOHUI. A Polynomial Time Algorithm for Maximum Lateness in Single Machine Scheduling with Batching[J]. Journal of Applied Sciences, 1998, 16(1): 18-23.

[1]	YANG Yanan, LI Yiming, NIE Lihai, ZHANG Ning, ZHAO Laiping. Cost-Efficient Task Scheduling in Geo-distributed Datacenters [J]. Journal of Applied Sciences, 2019, 37(6): 859-874.
[2]	ZHANG Meng-kang, ZHAO Hai-tao, YU Hong-su, MAO Tian-qi, ZHU Hong-bo. Multipath TCP Scheduling Optimization Based on PSRBP in Vehicular Heterogeneous Network [J]. Journal of Applied Sciences, 2019, 37(2): 261-270.
[3]	PENG Ya-li, ZENG Xin-yi, LÜ Ling, YANG Yu-xin, YIN Hong. Prediction of Public Cycling Complex Network Scheduling Based on Wave Motion Modes [J]. Journal of Applied Sciences, 2018, 36(4): 711-722.
[4]	CAO Tian-wei, XIE Wei, XU You-yun, XIANG Wei. Energy-Balanced Joint Clustering-Sleep Management Strategy for Machine-to-Machine Communications [J]. Journal of Applied Sciences, 2015, 33(4): 341-350.
[5]	DAI Cui-qin, WANG Liang, WANG Hai-bao. QoS Guarantee for Mixed-Service in OFDM Relay System [J]. Journal of Applied Sciences, 2014, 32(1): 13-18.
[6]	ZHANG Zhi-qiang, ZHANG Jing, ZHANG Xiang, LI Shu-juan. Improved Ant Colony Optimization Algorithm for Job Shop Scheduling Problem [J]. Journal of Applied Sciences, 2010, 28(2): 182-188.
[7]	SUN Huan;WANG Xin-yu;WANG Yan;YOU Xiao-hu. Multi-user Scheduling in MIMO System with Block Diagonalization [J]. Journal of Applied Sciences, 2008, 26(6): 551-555 .
[8]	ZHONG Chong-xian;YANG Lu-xi. User Scheduling and Power Allocation for Downlink of MIMO Systems with Limited Feedback [J]. Journal of Applied Sciences, 2007, 25(6): 551-551 .
[9]	SUN Huan;WANG Xin-yu;WANG Yan;YOU Xiao-hu. Influence of Feedback Delay on The Performance of Multi-user System [J]. Journal of Applied Sciences, 2007, 25(6): 564-564 .
[10]	WANG Li;SUN Shi-jie. A Scheduling Problem with Rejection of Goods Loading and Unloading [J]. Journal of Applied Sciences, 2007, 25(3): 283-283 .
[11]	CHEN Yue, SUN Shi-jie, SONG Zheng-fang, HE Long-min. Minimizing the Maximum Lateness on a Two Machine Flowshop with Batch Processors [J]. Journal of Applied Sciences, 2004, 22(2): 247-251.
[12]	CHENG Ming-bao, SUN Shi-jie, HE Long-min. Minimizing the Range of Lateness on a Single Machine with the Workpieces Processed in Batches [J]. Journal of Applied Sciences, 2003, 21(2): 141-145.
[13]	XU Zhi, XI Yu-geng, HAN Bing. An Algorithm of Make span Scheduling for Hybrid Production in Dynamic Environment [J]. Journal of Applied Sciences, 2002, 20(1): 70-76.
[14]	YAN Ji-hong, WU Cheng. A Neural Network Based Approach for Concurrent Activities Scheduling [J]. Journal of Applied Sciences, 2001, 19(3): 241-244.
[15]	LEI HANG, XIONG GUANGZE. Real Time Performance Evaluation for Dynamic Scheduling Algorithm [J]. Journal of Applied Sciences, 1998, 16(4): 457-462.

A Polynomial Time Algorithm for Maximum Lateness in Single Machine Scheduling with Batching

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments