Dissertation > Excellent graduate degree dissertation topics show

Some Results about Two Scheduling Models

Author: Zhang
Tutor: LiWenHua
School: Zhengzhou University
Course: Operational Research and Cybernetics
Keywords: single machine parallel batching batching cost dynamic programming common due date total weighted tardiness FPTAS
CLC: O226
Type: Master's thesis
Year: 2008
Downloads: 5
Quote: 0
Read: Download Dissertation

Abstract


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 jobsJ1,J2,…,Jn and a single batching machine which can process up to bjobs simultaneously. Each job Jj has a processing time pj. 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., dj = d; the equal-slack （SLK） due date model, i.e., dj = Pj +q,where q is a given constant; and the more general model called the processing-plus-wait （PPW） due date model,i.e., dj =αpj+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|wj=1|∑wjTj,1|wj=kpj|∑wjTj,1|pj=p|∑wjTj, were considered in the literature [11][5][8][10]. Our problem is 1|dj=d|∑wjTj. 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||∑wjTj 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|dj=d|∑wjTj. Similar to the algorithm which Cheng et al.[17] gave to theproblem 1|dj=pj+q|∑wjTj, we give for the problem 1|dj=d|∑wjTj a full polynomialtime approximation scheme （FPTAS）.

Related Dissertations

  1. Waveform Selection Method Based on Adaptive Dynamic Programming,TN951
  2. Coordination Scheduling Problem of Single Machine Manufacturing with Delivery in Supply Chain Environment,TH186
  3. Integration Supply Chain Scheduling with Single Machine,F274
  4. Three Gorges Cascade Reservoir Scheduling with Fuzzy Optimization Method,TV697.1
  5. The Reaserch and Realization of Large-scale Hydropower Station Economic Operation Decision Support System,TV737
  6. Research on Diagnosis Methods of Breast Masses Based on Reference Images,TP391.41
  7. Study on Power System Voltage and Reactive Power Control Method,TM761.1
  8. Research on Approaches of the Subjective Automated Assessment,TP391.1
  9. Study on Fleet Building Decision for Iron and Steel Enterprises,F552
  10. Research on the Optimal Strategies for the Multistage Multiple Purchasing When Purchase Price Is Uncertain,F224
  11. Multi-objective Optimal Operation for Reservoirs,TV697.1
  12. Real estate based on dynamic programming optimization decision multi-project development,F293.3
  13. Logistic Network Node Dynamic Location Analysis Based on Urban Development,F224
  14. Study on Real-time Rhythmic Information Retrieval of Musical Audio Signal and the System Implementation,TN912.3
  15. Research on Dim Target Detection Algorithm with Monopulse Doppler Radar,TN957.52
  16. Research of Problem of Supply Economic Lot-sizing of Enterprise Supply Chain Based on the Games Theory,F224
  17. Utility Optimization Problem and Generalization of p-Optimal Martingale Measure with Jumps,O224
  18. Bacteria in the food supply chain control model,TS201.6
  19. Model Predictive Control for a Plug-in Hybrid Electric Vehicle,U469.7
  20. Research and Implementation of Human Resources Dispatch in Software Enterprises,TP311.52
  21. Research and Implementation of Applications Oriented System with DAG Data Dependence,TP311.1

CLC: > Mathematical sciences and chemical > Mathematics > Operations Research > Queuing theory (random system)
© 2012 www.DissertationTopic.Net  Mobile