| In this paper, we consider two modern scheduling models: (1) scheduling with job position restriction (l\PR\f). (2) the single machine scheduling with job delivery to minimize makespan (1â†'D,k = 2|v = 1,c = z,2T1≥ T3 |Cmax).(1) Scheduling with job position restriction (1|PR|f).In the machine position restriction problem, we have n jobs J1, J2,..., Jn and m families of jobs F1,F2,....Fm, which partition the job set {J1, J2,..., Jn} with Fi∩Fj= θ (i≠j). Each job Jj has a processing time pj, a weight Wj, a release date rj and a due date dj. Each Fk has a position admissible set Sk {1,2,..., n}, k = 1,2,..., m. Si, and Sj may intersect from each other (i ≠j). Then φ = {S1,S2, ..., Sm} is a subset family of positions. In the literature, this problem is denoted by l|PR|f.The scheduling problem l|PR|f was first proposed by Lin Yixun and Yuan Jinjiang. We know that 1|| ∑wjCj can be solved in polynomial time by Smith's rule: Process the jobs in order of nonincreasing ratios wj/pj. 1||Lmax can be solved in polynomial time in EDD rule. 1|| ∑wjpj and 1|| ∑wjTj are both NP-hard. But the complexity of the problem 1|PR|∑wjcj is still open. In this article, we consider some polynomially solvable cases obtained by restricting pj = 1. Then we further consider a problem on unrelated parallel processors.(2) The single machine scheduling with job delivery to minimize makespan (1 â†' D, k = 2|v = 1,c = z,2T1≥T3|Cmax).The single machine scheduling problem with job delivery to minimize makespan can be described as follows. There are n jobs J1,..., Jn to be first batched and then processed by a single machine and then to be delivered to two customers. 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 two customers such that the time required for all jobs to be processed and delivered to the costumers is minimized. By using the notation of Lee and Chen [15], the single machine scheduling problem with job delivery to minimize makespan is denoted by1 â†'D,k = 2|v = 1,c = z, 2T1 ≥ T3|Cmax, where "1 â†' D,k = 2" is used to represent problems in which jobs are first processed on a single machine, and then delivered to two customers; 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 decade. Ahmadi et al. [7] have considered a two-machine flowshop (a single machine and a subsequent batch processor) scheduling problem with two performance measures including the makespan and the total completion time. Herrmann and Lee [14], Yuan [19], Chen [9], Yang [18] and Cheng et al. [11] have considered several batch scheduling problem with due dates related measures. Lee and Chen [15] 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 [10] 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 2.In this paper, we assume that 2Ti > T3, where Tiffi) is the transportation time for a batch that contains only jobs that require delivery to area l(area 2), T3 is the transportation time for a batch that contains jobs that require delivery to area 1 and area 2. Under this restriction, the problem is denoted by 1 —> D,k = 2\v = l,c = z, 2T\ > T3|Cmax- We give an algorithm with worst-case performance ratio ||. |
PDF Full Text Request