有使用限制的二台机器流水作业问题

• Original Articles • Previous Articles Next Articles

Two-Machine Flow Shop Problems with Availability Constraints

YANG Ming, LU Xi-Wen

Received:2011-05-19 Revised:2011-07-12 Online:2011-09-20 Published:2011-09-29
Contact: Xiwen Lu E-mail:xwlu@ecust.edu.cn

Abstract

Abstract: We investigate the problems for two-machine flow shop scheduling with availability constraints. A resumable scenario is assumed, i.e., if a job cannot be finished before the interval it is continued after the machine becomes available again. The objective is to minimize the makespan. We first consider an approximate case of the problem with several availability constraints on both machines, present an algorithm with performance ratio of 3/2. Then we give an algorithm with competitive ratio of 3/2 for the semi-online problem with an availability constraint on the second machine.

Key words: scheduling, flow shop, availability constraint, approximation algorithm, competitive ratio

YANG Ming, LU Xi-Wen. Two-Machine Flow Shop Problems with Availability Constraints[J]. Operations Research Transactions.

[1]	ZHAO Congcong, FANG Dandan, LI Rongheng. Optimal algorithms for hybrid flow shop schedule on two machines with learning effect [J]. Operations Research Transactions, 2020, 24(2): 42-60.
[2]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[3]	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.
[4]	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.
[5]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[6]	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.
[7]	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.
[8]	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.
[9]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[10]	ZHONG Weiya, YANG Ruoyao. Scheduling with sub-jobs' due dates [J]. Operations Research Transactions, 2019, 23(2): 67-74.
[11]	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.
[12]	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.
[13]	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.
[14]	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.
[15]	ZHAO Xiaocheng, LI Dagang. Parallel machine scheduling with machine and human eligibility restrictions [J]. Operations Research Transactions, 2018, 22(3): 99-108.

Two-Machine Flow Shop Problems with Availability Constraints

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments