中文

Operations Research Transactions ›› 2011, Vol. 15 ›› Issue (2): 59-67.

• Original Articles • Previous Articles     Next Articles

Two Models of Single Machine Scheduling with General Processing Time Functions

WANG  Cheng-Fei, ZHANG  Yu-Zhong, MIAO  Cui-Xia   

  • Online:2011-06-15 Published:2011-06-15
  • Supported by:

    Supported by the National Natural Science Foundation of China (No. 11071142, 70971076), ``Taishan Scholar" Project in Applied Mathematics of Shandong Province, Shandong Provincial Natural Science Foundation(No. ZR2010AM034), Specialized Research Fund for the Doctoral Program of Higher Education (No. 20070446001) and Social Science Planning Project of Shandong (No. 10DJGJ12)

PDF

1290

Abstract: Two models of single machine scheduling  with general processing time functions are considered.  Job's processing time is assumed to be the sum of  basic processing time and a function of starting time or  a function of position.  For processing over starting time model, the makespan minimization problem and total completion time minimization problem are polynomially solvable under certain conditions, which have more generality compared with previous articles. For processing  over position  model, there are optimal schedules for makespan minimization problem and total completion time minimization problem.   A property of optimal schedule and a greedy algorithm for total weighted completion time minimization problem are presented.

Key words:  scheduling, single machine, processing time function, time dependent

CLC Number: