Some Results On The Model Of Two Modern Sort

Scheduling is to assign jobs processed on machines under some constraints, such that one- or multi-criteria attain to the optimum. It can be divided into classical scheduling and modern scheduling. Compared with the classical scheduling, the modern scheduling is non-classical and new-type. There have been more than ten modern scheduling models which are widely discussed over the last twenty years, such as the scheduling with controllable processing time, the batching scheduling, multi-criteria scheduling, the scheduling with transportation constraints and so on. In this paper, we consider two modern scheduling models: (1) the single machine batching problem with identical family setup times to minimize maximum lateness (l|sf = s|Lmax). (2) the single machine scheduling and job delivery to minimize makespan with the processing time of jobs being proportional to their sizes (1 â†' D, k = 1|v = 1, c = z,Pj = uSj|Cmax).(1) the single machine batching problem with identical family setup times to minimize maximum lateness (l|sf = s|Lmax)In the single machine, family jobs, batch scheduling problem (see [2, 11]), we have n jobs J1,J2,...,Jn and F families of jobs F1,F2...FF, which partition the job set {J1,J2 ...Jn} Each job Jj has a processing time pj and a due date dj, and each family Ff has an associated setup time sf. The jobs in a family are processed in batches and each batch of family Ff will incur a setup time Sf. The objective is to minimize the maximum lateness. In the literature,this problem is denoted by 1|s/|Lmax.The scheduling problem 1|sf|Lmax was first researched by Bruno and Downey [2] in 1978. The binary NP-hardness proof for the problem l|sf|Lmax was given by Bruno and Downey [2]. The best algorithm for the problem l|sy|Lmax is a dynamic programming algorithm given by Ghosh and Gupta [6] with a time bound O(F2NF), where N = 1/F∑1≤f≤F|Ff|+ 1- The strongly NP-hardness of the problem l|sf|Lmax was proved by Cheng, Ng and Yuan [9] in 2003. This answers a long-standing open problem posed by Bruno and Downey [2] in 1978. When the setup times of all families are identical, whetherthe problem l|s/ = s\Lmax is strongly NP-hard is still an open problem. By a development of the proof in [9], we show in this paper that the scheduling problem l\sf = s|Lmax is still strongly NP-hard.(2) the single machine scheduling and job delivery to minimize makespan with the processing time of jobs being proportional to their sizes (1 —? D, k — \\v = l,c = z,pj = MSj|CmaxjThe single machine scheduling and job delivery problem to minimize makespan can be described as follows. There are n jobs Ji,..., Jn to first be processed in a manufacturing system by a single machine and then to be delivered to a single customer. Each job Jj has a processing time pj and a size Sj, where Sj represents the physical space Jj occupies when it is loaded in the vehicle. Only one vehicle is employed to deliver all the jobs, which has a capacity z. That is, the total physical space of jobs loaded into the vehicle does not exceed z. The problem is to find a schedule for processing jobs in the manufacturing system and for delivering finished jobs to a single customer such that the time required for all jobs to be processed and delivered to the costumer is minimized. By using the notion of Lee and Chen [20], the single machine scheduling problem with job delivery to minimize makespan is denoted by 1 —> D, k = l|i> = 1, c = z\Cmax, where "1 —> D,k = 1" is used to represent problems in which jobs are first processed on a single machine, and then delivered to a single customer; and "v = l,c = z" means that only a vehicle is employed to deliver all jobs, which has a capacity z.The machine scheduling problem with delivery coordination has been one of the most important and widely discussed topics in manufacturing research over the last ten years. Ahmadi et al. [13] have considered a two-machine flowshop (a single machine and a subsequent batch processor) scheduling problem with two performance measures including makespan and sum of completion times. Herrmann and Lee [19], Yuan [24], Chen [15], Yang [23] and Cheng et al. [17] have considered several batch scheduling problem with due dates related measures. Lee and Chen [20] have considered another coordination of production scheduling and transportation (subject to delivery time and vehicle capacity)to minimize makespan without considering delivery cost. This problem has been extended by Chang and Lee [16] by considering the situation where each job might occupy a different amount of physical space in a vehicle. They assumed that the processing time of a job is independent on its size, and proved that this problem is strongly NP-hard and then provided a heuristic of worst-case performance ratio of |, and this bound is tight.But in the manufacturing system, the job with bigger size might need more processing time than another job with smaller size when they are processed on a single machine. In this paper, we assume that the processing times of jobs are proportional to their sizes, i.e., Pj = uSj, Vj, where u denotes the processing time needed for a unit size. Under this restriction,the problem is denoted by 1 —? D,k — \\v = l,c = z,pj — uSj\Cmax. By setting u — 0, we can observe that the strongly NP-hard bin-packing problem (Garey and Johnson, [3]) is a subproblem of the problem under consideration. Hence, the problem 1 —> D,k = l|i? = l,c = z,pj = usj\Cmax is still strongly NP-hard. For this problem, we first show that Chang-Lee's heuristic has a better performance ratio of ||, and then we also provide a new heuristic which has the worst-case performance ratio of |, and this bound is best.