作者：欧锦文
出版社：暨南大学出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
生产与运输协同调度：模型与算法(英文版)试读：
Preface
The coordination of logistics activities in a supply chain has received a lot of attention in operations management research. In a typical supply chain, raw materials are transported to factories where items are produced, and finished products are either shipped to warehouses for temporary storage or delivered directly to the retailers or the customers. To achieve better operational performance, the coordination and integration of production and distribution is an important consideration.
In this book, we study five models of coordinated scheduling of production and distribution operations. The motivations of five models are different.
In Chapter 1, we consider an order acceptance and scheduling model with job delivery times and machine availability constraints. Order acceptance and scheduling (OAS) is to balance order acceptance (to increase revenue and guarantee satisfaction of customers) and order rejection (to reduce production or delivery load so as to meet limited production capacity restrictions and tight delivery requirements). In our model, due to specific production constraints of machine availability and the delivery times of finished orders, some orders (jobs) have to be rejected or outsourced.
In Chapter 2, we study an inbound logistics scheduling model with limited unloading capacity, which is motivated by the inbound logistics system for a major automobile manufacturing company in China. The research problem can be reduced to a parallel machine scheduling problem with multiple common unloading servers. In the proposed scheduling model, after processing a job, an unloading server will be needed to remove the job from the machine. Only after its current job is unloaded, a machine can start processing the next job.
In Chapter 3, we study machine scheduling with raw material pickup and finished job delivery. Traditional machine scheduling models focus on the optimization of schedules under various machine environments, processing characteristics and constraints, and performance measures. However, these models normally ignore the transportation arrangements of the incoming materials and the delivery arrangements of the finished products. In this chapter, we develop and analyze a scheduling model that takes into account the machine schedule and the pickup and delivery plan of the supply of the raw materials and the shipment of finished jobs.
In Chapter 4, we turn to the study of coordinated scheduling of customer orders with decentralized machine locations. In many production and transportation planning environments, the delivery of finished goods is constrained by the processing of different component parts of the product. It is also quite common that different components of a product have to be processed by their own dedicated machines or work centers. For example, in the production of personal computer systems, the computers and monitors are usually produced by different facilities at different locations. However, both the computers and monitors of the finished products must be bundled together before they can be delivered to customers. In order to obtain a system-wide optimal production and delivery plan, it is essential to consider the sequencing and scheduling of the tasks at each machine and the delivery arrangements of the finished tasks to their final destinations at the same time. When such an integrated plan is developed, the scheduler faces a tradeoff between providing quick deliveries and minimizing shipping costs. Quick deliveries minimize customers' waiting time while low shipping costs directly benefit the company's bottom line. Thus, we consider a scheduling which reflects such production and delivery arrangements.
In Chapter 5, we study the coordination of cargo unloading and storage arrangements at cargo terminals. We specifically consider a problem which is motivated by the operations of air cargo terminal operators at the Hong Kong International Airport (HKIA). In this problem, there are a number of outbound flights with confirmed air waybills. The terminal operator would like to schedule the arrival of the delivery trucks so that some of the shipments can be transferred directly to the departing flights, while other shipments will be transferred to the storage area of the terminal and will incur extra handling and storage costs. The objective is to obtain a feasible schedule so as to minimize the total cost of operations.Chapter 1 Order Acceptance and Scheduling with Job Delivery Times and Machine Availability Constraints1.1 Introduction
Order acceptance and scheduling (OAS) has attracted considerable attention from scheduling researchers as well as production managers who practice it in the past decades. The key issue in OAS is to balance order acceptance (to increase revenue and guarantee satisfaction of customers) and order rejection (to reduce production or delivery load so as to meet production capacity or delivery requirements). One important application of OAS arises in make-to-order production systems with limited production capacity or tight delivery requirements, where order rejection and scheduling decisions have to be made simultaneously. In practice, due to production capacity constraints and short delivery due dates, a typical manufacturer may have to reject some orders which require long processing or delivery times but make relatively small profits. Another important application of OAS occurs in scheduling when outsourcing is an alternative option. OAS combines outsourcing and production scheduling decisions together.
In traditional OAS models the manufacturer (machine) is usually assumed to have the capacity of processing orders continuously. But in reality, production could be interrupted due to some unpredictable reasons such as machine breakdown or maintenance, production setup, worker vacation and so on, which leads to the scenario that there are only a number of discontinuous time intervals available to process the orders in question. When production capacity and machine available time have restrictions, to reduce production load, the manufacturer may have to reject some orders which require long processing times but make relatively small profits, or outsource the production of some orders, in this case the profit of those outsourced orders is reduced. In this chapter,we study a single-machine OAS model with machine availability constraints and order delivery times. In the proposed model, the machine is available to process orders only within a number of given discontinuous time intervals, and the manufacturer is allowed to reject some orders. When an order is rejected, an order-dependent penalty will occur. Each order has a specific delivery times after its processing. The manufacturer needs to balance the production capacity and the delivery requirement (the time span of delivering all accepted orders to their customers) and the total penalty of all rejected jobs.
OAS has been studied extensively in the production scheduling literature. Guerrero and Kern(1988) provided the rational to accept and reject orders effectively. Slotnick and Morton (1996) and Ghosh (1997) studied single-machine OAS with the objective of maximizing revenue and minimizing lateness penalties. Slotnick and Morton (2007) extended their previous work (Slotnick and Morton, 1996) by replacing lateness with tardiness in the objective function. Rom and Slotnick (2009) developed a genetic algorithm for the same problem and compared it with the myopic heuristic given in Slotnick and Morton (2007). Nobibon and Leus (2011) studied an OAS model with “firm planned orders as well as potential orders”. Oguz et al. (2010) included sequence-dependent setup times and two-level due-dates in an OAS model with weighted tardiness. Cesaret et al. (2012) developed a tabu algorithm for the same problem and compared it with the two heuristics proposed in Oguz et al. (2010). Yang and Geunes (2007) considered an OAS model with controllable processing times. Chen and Li (2008), Lee and Sung (2008a, 2008b) and Qi (2008, 2009, 2011) considered OAS models with outsourcing options. An excellent literature survey on the topic of OAS is provided by Slotnick (2011) recently.
OAS is equivalent to machine scheduling with rejection (MSR) in mathematics. Bartal et al. (2000) first introduced a multi-processor MSR model to minimize the makespan of all accepted jobs plus the total rejection penalty of all rejected jobs. Seiden (2001) and Hoogeveen et al. (2003) studied the on-line version and the off-line version in Bartal et al. (2000) when job preemption is allowed, respectively. Epstein et al. (2002) considered on-line MSR with unit-processing-time jobs and the total completion time of all accepted jobs. Engels et al. (2003) studied single-processor MSR with total weighted completion times of all accepted jobs, and recently, Kellerer and Strusevich (2013) improved the related results. MSR models with industrial applications are studied by Cheng and Sun (2009), Zhang et al. (2009,2010), Lu et al. (2008) and Lu et al. (2009), among others. A very recent survey on MSR is provided by Shabtay et al. (2013). All of the OAS and MSR models mentioned above have the potential assumption that machines can process jobs continuously, which differ from our model.
Our model is an extension of machine scheduling with availability constraints (MSAC). MSAC also has been studied extensively. The surveys of MSAC are provided by Schmidt (2000) and Ma et al. (2010). In this paper we consider a single-machine model with machine availability constraints. In the following we only review the previous work of MSAC with a single machine, and whose objective is limited to minimization of makespan. For convenience, we define MSAC-k to be the MSAC problem to minimize makespan with a single machine and k time intervals during which the machine is not allowed to process jobs. Lee (1996) showed that MSAC-1 has been NP-hard, and that MSAC-k is NP-hard in the strong sense if k is arbitrary. He et al. (2005) proposed a fully polynomial time approximation scheme (FPTAS) for MSAC-1. Breit et al. (2003) showed that no polynomial time approximation algorithm with a fixed performance ratio exists for MSAC-2. When every job also has a delivery time, Yuan et al. (2008) showed that MSAC-k can be solved by a pseudo-polynomial time algorithm if k is fixed. They also developed a polynomial time approximation scheme (PTAS) for MSAC-1. Kacem (2009) studied a similar problem to Yuan et al. (2008), and proposed an FPTAS by exploiting the well-known approach of Ibarra and Kim (1975). Wu and Lee (2003), Gawiejnowicz (2007), and Ji et al. (2006) studied MSAC with deterioration, where the processing time of a job is a linear function of its starting time. To the best of our knowledge, our model is the first to examine OAS with machine availability constraints.
Our model is also an extension of machine scheduling with job delivery times. Machine scheduling with job delivery times is also a classical scheduling model (see, for example, Hall and Shmoys, 1989, Jackson, 1955, Kise et al., 1979, Lawler et al., 1993, and among others), in which each job is delivered to its customer at its processing completed time by a specific vehicle with a given delivery time. For machine scheduling with delivery times, a classical result is that, the problem 1|qj|Dmax can be solved in O(nlogn) time by using the “largest delivery time first” (LDT) rule (see Jackson, 1955). Lawler et al. (1993) prove that problem 1|rj,qj|Dmax is strongly NP-hard. For the same problem, Kise et al. (1979) show that LDT rule is 2-competitive, and Hall and Shmoys (1989, 1992) develop two polynomial time approximation schemes. Mastrolilli (2003) develops an improved approximation scheme for the same problem. When preemption is allowed, it is shown in Baker et al. (1983) that problem 1|prec, pmtn, rj, qj|Dmax can be solved in O(n2) time.
We now describe our problem formally as follows. Given a set of n jobs J={J1,J2,…,Jn} and a single machine, each job Jj∈J is associated with a processing time pj, a job delivery time qj and a rejection penalty wj. Job Jj is either accepted and then processed on the machine, or it is rejected by the machine and then a rejection penalty wj is paid. Penalty wj is regarded as the cost of losing or outsourcing job Jj. Also given 2m+1 non-negative integers a0,a1,…,a2m such that 0=a0 In our model, we assume that the machine can process at most one job at a time, that job preemption is not allowed, and that pj and wj are non-negative integers for j=1,2,…,n. Following the standard classification scheme for scheduling problems［7,18］, the proposed scheduling problem is denoted as where “FB” means that accepted jobs must be processed in free time slots to avoid forbidden intervals, while “rej” means that job rejection is allowed. When m (i. e., the number of UIs) is a fixed number, we denote the problem as When qj=0 for each job, i. e., the job delivery time of each job is zero, we denote the problem as Machine scheduling with forbidden intervals (machine maintenances) has been widely studied in the past two decades. NP-hardness results of problem 1｜FB｜Cmax are provided by Lee (1996) and Scharbrodt et al. (1999). For problem 1｜FB(1)｜Cmax, the performance ratio of the LPT heuristic is shown to be, and the bound is tight (Lee, 1996). A fully polynomial time approximation scheme is given by He et al. (2005). Some related work on scheduling with forbidden intervals can also be found in the study of Cassady and Kutanoglu (2003), Chen(2006), Graves and Lee(1999). A survey on machine scheduling with forbidden intervals is provided by Schmidt (2000). Study of a relaxed version in which machine maintenances are not fixed previously can be found in Akturk et al. (2003, 2004), Qi (2007), Qi et al. (1999). Note that when job preemption is allowed, problem 1｜FB(m),pmtn,qj｜Dmax is solved in O(nlogn+mlogm) time by Yuan and Lin (2005). For convenience, we introduce the following notations, which will be used throughout the paper:=the total processing time of all the jobs;=the total rejection penalty of all the jobs;=the set of jobs with processing times less than their rejection penalty;=the set of jobs with processing times no less than their rejection penalty;=the total processing time of all the jobs in U; σ* = the optimal solution; A* = the set of all accepted jobs in σ*; R*=J＼A*=the set of all rejected jobs in σ*;= the makespan of A*, i. e., the completion time of the last accepted job in A*; Dmax= the completion time of delivery for all the jobs in A*;the objective function value of σ*; a2m+1=a2m+P = the largest possible makespan of all accepted jobs in σ*; Li=a2i-a2i-1 = the length of the i-th UI (i=1,2,…,m); L′i=a2i-1-a2i-2 = the length of the i-th AI (i=1,2,…,m+1); ε: any given small constant such thatis a positive integer. The rest of the chapter is organized as follows. In Section 1.2 we develop a pseudo-polynomial algorithm to solve problem 1｜FB(m),rej,qj｜Dmax+∑wj. In Section 1.3 we provide non-approximability results to problem 1｜FB(2),rej,qj｜Dmax+∑wj. In Section 1.4 we present an FPTAS for the special case 1｜FB(1),rej,｜Cmax+∑wj. In Section 1.5 we present a polynomial time approximation scheme (PTAS) for the special case 1｜FB(1),qj｜Dmax. In Section 1.6 we develop a(2+ε)-approximation for the special case with Li′=L′, Li=L for i=1,2,…,m and qj=0 for j=1,2,…,n. Some concluding remarks are provided in Section 1.7.1.2 An Optimal Pseudo-polynomial Algorithm When m Is Fixed Note that if m is arbitrary, then problem 1｜FB,rej,qj｜Dmax+∑wj is shown to be NP-hard in the strong sense by reducing from 3-PARTITION (even when eachqj=0), and thus an optimal pseudo-polynomial algorithm for 1｜FB,rej,qj｜Dmax+∑wj does not exist (see Garey and Johnson, 1979). Therefore, in the remainder of this section, we study the special case when the value of m is fixed. We present a pseudo-polynomial algorithm to solve. It is clear that the accepted jobs that are scheduled within the same AI follow the “largest delivery time first”rule. A schedule is called an LDT schedule if the accepted jobs that are scheduled within each AI follow the LDT rule. In the development of our algorithm, we only need to determine an optimal LDT schedule. Reindex the n jobs in an LDT order, i. e., q1≥q2≥…≥qn. We now develop our pseudo-polynomial time algorithm for problem 1｜FB(m),rej,qj｜Dmax+∑wj. In the following of this section, when we mention a solution or schedule, we always mean an LDT solution or schedule. Without loss of generality, we can assume thatL′i Our DP will keep tracking the total processing time of the jobs scheduled within each of the m+1 AIs when considering the n jobs one by one. Let qmax={qj｜Jj∈J}. To simplify our DP, we add a dummy job J0 with zero processing time and zero job delivery time. The dummy job J0 is fixed to be scheduled within the last AI ［a2m,a2m+1］so that it is the first job to be scheduled in the AI (i. e., the completion time of the delivery of J0 is equal to a2m). We now present our DP. Denote the problem instance containing only the first j jobs J1,J2,…,Jj by Ij. For any j=1,2,…,n,D=a2m,a2m+1,…,a2m+1+qmax, i=1,2,…,m+1 and gi=0,1,…,L′i, define Gj(g1,g2,…,gm+1,D) as the minimum total cost to Ij such that the total processing time of all accepted jobs assigned to AI［a2i-2,a2i-1］is equal to gi for i=1,2,…,m+1, and the completion time of the delivery of all accepted jobs among the first j jobs is equal to D. To develop recursive relations, consider the following two cases: Case A: Job Jj is rejected. In this case, we have Gj(g1,g2,…,gm+1,D)=Gj-1(g1,g2,…,gm+1,D)+wj. Case B: Job Jj is accepted and scheduled to the i-th AI for some i=1,2,…,m+1. In this case, Jj is the last accepted job to be processed within the i-th AI currently, and we should have gi≥pj and a2i-2+gi+qj≤D. Thus, we have Gj(g1,…,gi,…,gm+1,D)=Gj- 1(g1,…,gi-pj,…,gm+1,D). Combining the two cases above, we have the following dynamic program DP1: (1) Recurrence relation: For j=1,2,…,n, i=1,2,…,m+1 and gi=0,1,…,L′i, Gj(g1,g2,…,gm+1,D)= (2) Boundary condition: (3) Objective: min{Gn(g1,g2,…,gm+1,D)|1≤i≤m+1,0≤gi≤Li',a2m≤D≤a2m+1+qmax∑(i=1,2,…,m+1)gi≤P}. Consider the complexity of DP1. Note that we assume L′i Theorem 1.1 Problem 1|FB(m),rej,qj|Dmax+∑wj can be solved in a pseudo-polynomial time.
试读结束[说明：试读内容隐藏了图片]