带有学习效应和机器可用性限制的排序问题

针对单机和两台机器的平行机排序问题,建立了机器具有学习效应和可用性限制的排序模型。在这个模型中,机器具有学习效应。在学习效应下,工件的加工时间与所排位置有关,对于需要在同台机器上加工的工件,工件随位置的靠后其实际的加工时间减少。同时由于定期维修等原因而导致机器在某段时间内不能加工工件。考虑了目标函数为极小化总完工时间的单机和两台机器的平行机问题。对于机器在任意时间进行维修的一般情况给出了动态规划算法,通过数值例子说明了算法的有效性,对机器在使用前进行维修的特殊情况给出了多项式算法。

Scheduling problems with learning effect and availability constraint

Aiming at the scheduling problems of the single machine and two parallel machines,a model of scheduling problems with learning effect and an availability constraint is established.In the model,the machines have learning effect.By the learning effect,the processing time of jobs is defined as the function of their positions in a sequence,and the jobs to be processed on the same machine,Their actual processing time is gradually reduced along with the order of their positions.Moreover,the machine could be unavailable for a specified period of time by periodic machine maintenance activity.That the objective function is to minimize the total completion time of single machine problems and two parallel machines problems is considered.A dynamic programming algorithm is provided for the machine maintenance in the common case at any time,and the validity of the algorithm is also illustrated by an example.A polynomial algorithm is given for the maintenance before the use of the machine in the special case.