Some Results About Two Scheduling Models

Scheduling is to assign jobs processed on machines under some constraints, such thatone-or mufti-criteria are attained to the optimum. In this paper, we consider two scheduling models: (1) The single machine parallel batching problem with batching costs. (2)The single machine scheduling problem with common due date to minimize total weightedtardiness.(1) The single machine parallel batching problem with batching costs.The problem we consider is adding batching costs to the general regular objectivefunction of the single machine parallel batching problem. It can be described as follows:there are n jobsJ₁,J₂,…,J_n and a single batching machine which can process up to bjobs simultaneously. Each job J_j has a processing time p_j. We assume that the jobs andthe machine are available from time zero onwards. The jobs that are processed togetherform a batch and once processed they can not be interrupted. The processing time of abatch is equal to the maximum processing time of the jobs assigned to it. The objectivefunction is the sum of the general regular cost function and the batching costs. Let fdenote the arbitrary regular function and V denote the total batching costs. Moreover, weassume that there is a same batching cost v for each batch. This means that if there arem batches, the total batching costs V are equal to mv. Our problem can be denoted by1|p-batch,b=∞(b＜n)|f+V. We give some dynamic programming algorithms to thedifferent models with batching costs to obtain the optimal solution.(2) The single machine scheduling problem with common due date to minimize totalweighted tardiness.The problem of minimizing the total weighted tardiness on a single machine occursfrequently in practice. But only a few results involving arbitrary due dates have beenreported in the literature since the problems are quite hard to handle analytically. Theinterest in special due date models has been increasing lately, such as the common/constant(CON) due date model, i.e., d_j = d; the equal-slack (SLK) due date model, i.e., d_j = P_j +q,where q is a given constant; and the more general model called the processing-plus-wait (PPW) due date model,i.e., d_j =αp_j+q,whereαand q are given constants. Someresearchers are also interested in models where special restrictions are imposed on otherproblem parameters. For example, the problems 1|w_j=1|∑w_jT_j,1|w_j=kp_j|∑w_jT_j,1|p_j=p|∑w_jT_j, were considered in the literature [11][5][8][10]. Our problem is 1|d_j=d|∑w_jT_j. We know that it is NP-hard in the ordinary sense [9]. Lawler and Moore [7]provided a pseudo-polynomial algorithm for it. We also know the problem 1||∑w_jT_j isstrongly NP-hard [5][10]. Cheng et al. [17] gave a O(n2) time approximation algorithmfor this problem. We take the objective value of this algorithm as the upper bound of ourproblem 1|d_j=d|∑w_jT_j. Similar to the algorithm which Cheng et al.[17] gave to theproblem 1|d_j=p_j+q|∑w_jT_j, we give for the problem 1|d_j=d|∑w_jT_j a full polynomialtime approximation scheme (FPTAS).