Operations Research Transactions ›› 2010, Vol. 14 ›› Issue (2): 1-10.

• Original Articles •     Next Articles

Dense Schedule for Open Shop Problems with at Most   Two Idle Intervals on the Last Complete Machine

CHEN Rong-Jun, HUANG Wan-Zhen, TANG Guo-Chun   

  • Online:2010-06-15 Published:2010-06-15

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.