Operations Research Transactions ›› 2010, Vol. 14 ›› Issue (2): 1-10.
• Original Articles • Next Articles
CHEN Rong-Jun, HUANG Wan-Zhen, TANG Guo-Chun
Online:
Published:
Abstract: For open shop problem, if the principle of avoiding unnecessary machine idleness is applied when arranging jobs, a dense schedule is obtained. It is conjectured that the makespan of any dense schedule is at most $2-1/m$ times the optimal makespan of the problem, where m is the number of machines. The conjecture remains unproved when the number of machine is greater than six. In this paper, by introducing characteristic functions of jobs and machines and non-interruption of machines about jobs, we propose sufficient conditions under which the conjecture is true for general number of machines, provided that the last complete machine in the dense schedule has no more than two idle intervals.
CHEN Rong-Jun, HUANG Wan-Zhen, TANG Guo-Chun. Dense Schedule for Open Shop Problems with at Most Two Idle Intervals on the Last Complete Machine[J]. Operations Research Transactions, 2010, 14(2): 1-10.
0 / / Recommend
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/Y2010/V14/I2/1