パス構造グラフにおける納期違反コスト最小化選択的配達スケジューリング(機械要素,潤滑,工作,生産管理など)

概要

論文の詳細を見る
In this paper, we consider a selective scheduling problem of minimizing a due date involving criterion for a single uncapacitated vehicle. Let G= (V, E) be a path with a set V={v_i|i=1, 2, ・・・, n} of vertices and a set E={{v_i, v_<i+l>}|i=1,2,・・・,n-1} of edges. The vehicle is initially situated at v_1. There is a job i at each vertex v_i&isinsvt; V, which has its own handling time h_i and due date d_i. Travel times W_<i,i+1> of the vehicle are associated with edges {v_i, v<i+1>}i&isinsvt;E. A schedule of the vehicle is called 1-way if it visits every edge {v_i-, v<i+1>} exactly once, that is, it simply moves from v_i to v_n on G. In this paper, the vehicle is assumed to move according to a 1-way schedule. But a choice still remains for each job whether it is processed at the time of the visit, since a certain penalty a (≥1) is required if some job is not processed by the vehicle. If a processed job i is completed by its due date d_i, no penalty is required. Otherwise, the unit penalty is paid. The objective is to minimize the total penalty over all n jobs. We show that, if α is given as a positive integer, the selective vehicle scheduling problem can be solved in polynomial time by a dynamic programming approach.
一般社団法人日本機械学会の論文
2007-03-25