Single Machine Scheduling With Fixed Jobs And Job Delivery Times

Scheduling problem is attracting a lot of attention because its deeply background in the real world and bright future in various application environments. In this paper we consider single machine scheduling with fixed jobs. The fixed jobs are special and their starting times and completion times are previously given. They occupy some disjoint intervals in the horizon. During processing, preemption is not allowed. Whence the processing of a job is finished, it is delivered to its customer immediately which takes a delivery time. We assume that there are sufficiently many vehicles to deliver the jobs.Two chapters are included in this thesis.In the first chapter, some notation, definitions and basic background information about the subject are introduced.In the second chapter, we discuss four scheduling models mainly. They are representedasThe complexity, pseudo-polynomial time algorithms and polynomial-time approximation algorithms are included. Main results of this paper are as follows.(1) 1|FB(F),q_j|L_max, 1|FB(F)|maxω_jC_j and 1|FB(F)|∑ω_jC_j are NP-hard, 1|FB, q_j|L_max is strongly NP-hard.(2) 1|FB(F), q_j|L_max, 1|FB(F)|maxω_jC_j and 1|FB(F)|∑ω_jC_j can be solved in pseudo-polynomial time.(3) For 1|FB,q_j|L_max , we give a 2-approximation algorithm and show that this is best possible polynomial-time approximation algorithm;For 1|FB(1),q_j|L_max , a 3/2-approximation algorithm is provided;For 1|FB(1)|maxω_jC_j, we provide a ploynomial-time approximation algorithm withworst case ratio 2. When is a constant, we get a PTAS. We also prove that for anygiven constant M, the problem 1|FB(2)|maxω_jC_j has no polynomial-time approximation algorithm with worst case ratio achieving M unless P = NP.