To see the other types of publications on this topic, follow the link: Scheduling of Unreliable Jobs.
Dissertations / Theses on the topic 'Scheduling of Unreliable Jobs'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Scheduling of Unreliable Jobs.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Mario, Benini. "Improving Decision Making in Real-world Applications by Solving Combinatorial Optimization Problems." Doctoral thesis, Università di Siena, 2022. https://hdl.handle.net/11365/1221594.
Full textAbstract:
The motivation for this work is to study complex real-world scenarios and provide tools that can actually improve decision-making in those problems. To do so, we mainly adopt techniques from the fields of Operations Research and Combinatorial Optimization.
In this dissertation, we focus on three real-world applications from different industries that can be modeled as combinatorial optimization problems and address them with operations research techniques. The dissertation is divided in chapters, each of which is related to a different topic.
In Chapter 1, a problem concerning the transportation of biological samples from draw centers to a main laboratory for analysis is presented. The problem arises from a healthcare application in Bologna, Italy, where the healthcare authority decided to centralize the analysis of all biological samples of the area to a main laboratory, in order to exploit economies of scales and reduce the costs for samples’ analysis. Of course, such an improvement goal also created a new complex problem: all the samples must be transported from draw centers to the main lab. A fleet of vehicle is available for the transportation and must collect the samples from draw centers during given times of the day and deliver them within a certain time, since samples are perishable. Vehicles can also exploit the existence of dedicated centers that can extend the lifespan of the samples and where samples can be transferred from one vehicle to another. It is clear from this brief description how hard it could be to decide which is the routing of all the vehicles which minimizes the traveling costs while delivering all samples on time. For this problem we developed different mixed integer linear programming models, metaheuristic algorithms, and grouping policies for the samples that are able to tackle the complexity of the problem and improve routing decisions. All methods have been tested through an extensive computational campaign using real-world data, showing the effectiveness of the proposed approaches.
In Chapter 2, a problem related to the agricultural industry is presented. The problem arises from a real-world application in Italy and it is that of planning the use of the available land of a farm for a given number of years, given a set of crops that can be grown. The objective is to maximize the farmer’s profit, but the farmer is subject to several rules both from an agronomic and from a regulation point of view. In fact, many constraints exist regarding agronomic principles, such as maximum replanting, botanical family constraints and crop rotation issues. One of the goals of this work is indeed that of evaluating the risks and benefits of following or not the best practices regarding crop rotation issues in the Mediterranean pedo-climatic context. Furthermore, we want to evaluate the effectiveness of public and private initiatives regarding sustainable agriculture. In fact, it is more and more important nowadays to face these challenges in the food supply chain, which is one of the most discussed industries when it comes to sustainability. In particular, we analyze two different initiatives, namely the Common Agricultural Policy by the European Union and “La Carta del Mulino” by Barilla Group S.p.A.. Both initiatives introduce economic incentives for the farmers following virtuous behaviors from a sustainability point of view. Practically, these behaviors are constraints increasing the complexity of the problem and the difficulty in the decision-making process. For this problem, we will give a formal characterization and study its complexity, also analyzing special cases. We will also present a network-flow based model to solve a special case of the problem and integer linear programming models developed to solve three variants accounting for different sustainability scenarios. Real-world data from 23 Italian farms were used in an extensive computational campaign. The analysis of the results shows that the models can be helpful tools for farmers to plan their production and for authorities to evaluate the effectiveness (and efficiency) of their sustainability initiatives.
In Chapter 3, we discuss a problem concerning the sequencing of unreliable jobs on parallel machines. Even if the problem is not taken from a specific application, it may have several applications in real-world scenarios, such as in manufacturing and planning of complex computations on multi-processors computers. In this problem, we have n unreliable jobs providing a reward when successfully completed, but each job has a probability of not being carried out. We have m parallel identical machines at our disposal, and we want to schedule the jobs on the machines in order to maximize the total expected reward. To increase the probability of completing the jobs, we create m copies of each job and schedule each copy on a different machine. For this problem, we will present a complexity analysis showing that the problem is NP-complete for two machines. For the problem with two machines, we derived some theoretical properties and developed a quadratic integer programming model, a tabu search algorithm, and an upper bound based on the Three-Dimensional Assignment problem. A computational campaign on different sets of instances shows that the tabu search outperforms the model. Then we focused on the general case with m machines. In particular, we developed several heuristics and proved some theoretical results, including the worst case performance guarantee of two heuristics. We also devised a generalized tabu search algorithm and a new, improved, upper bounding scheme based on a relaxation of the problem. Computational experiments are performed for the new methods on the problems with two and three machines. The results show that good optimality gaps are reached on all the instances.
2
Song, Bin 1970. "Scheduling adaptively parallel jobs." Thesis, Massachusetts Institute of Technology, 1998. http://hdl.handle.net/1721.1/50354.
Full text
3
Han, Kai. "Scheduling Distributed Real-Time Tasks in Unreliable and Untrustworthy Systems." Diss., Virginia Tech, 2010. http://hdl.handle.net/10919/26917.
Full textAbstract:
In this dissertation, we consider scheduling distributed soft real-time tasks in unreliable
(e.g., those with arbitrary node and network failures) and untrustworthy systems (e.g., those
with Byzantine node behaviors). We present a distributed real-time scheduling algorithm
called Gamma. Gamma considers a distributed (i.e., multi-node) task model where tasks are
subject to Time/Utility Function (or TUF) end-to-end time constraints, and the scheduling
optimality criterion of maximizing the total accrued utility. The algorithm makes three novel
contributions. First, Gamma uses gossip for reliably propagating task scheduling parameters
and for discovering task execution nodes. Second, Gamma achieves distributed real-time
mutual exclusion in unreliable environments. Third, the algorithm guards against potential
disruption of message propagation due to Byzantine attacks using a mechanism called
Launcher-Attacker-Infective-Susceptible-Immunized-Removed-Consumer (or LAISIRC). By
doing so, the algorithm schedules tasks with probabilistic termination-time satisfactions,
despite system unreliability and untrustworthiness.
We analytically establish several timeliness and non-timeliness properties of the algorithm
including probabilistic end-to-end task termination time satisfactions, optimality
of message overheads, mutual exclusion guarantees, and the mathematical model of the
LAISIRC mechanism. We conducted simulation-based experimental studies and compared
Gamma with its competitors. Our experimental studies reveal that Gammaâ s scheduling algorithm
accrues greater utility and satisfies a greater number of deadlines than do competitor
algorithms (e.g., HVDF) by as much as 47% and 45%, respectively. LAISIRC is more tolerant
to Byzantine attacks than competitor protocols (e.g., Path Verification) by obtaining as much as 28% higher correctness ratio. Gammaâ s mutual exclusion algorithm accrues greater
utility than do competitor algorithms (e.g., EDF-Sigma) by as much as 25%. Further, we
implemented the basic Gamma algorithm in the Emulab/ChronOS 250-node testbed, and
measured the algorithmâ s performance. Our implementation measurements validate our
theoretical analysis and the algorithm's effectiveness and robustness.Ph. D.
4
Ramachandra, Girish. "Scheduling Precedence Related Jobs on Identical Parallel Processors." NCSU, 2002. http://www.lib.ncsu.edu/theses/available/etd-20020121-185145.
Full textAbstract:
The problem of concern to us in this thesis is the scheduling ofprecedence-related jobs non-preemptively on two identical parallelprocessors to minimize the sum of the weighted completion times. The problemis known to be NP-hard.We develop, in chapter 2, a binary integer program which iscapable of solving only small size problems (no larger than 12jobs) to optimality at the present time. We also present a linearprogramming(LP) model adopted from the literature todetermine the lower bound on the optimum. This LP stands us ingood stead when we perform the optimization via the GeneticAlgorithm approach (which is the subject matter of chapter 3). Wealso present a dynamic programming formulation based on theapproach used for solving the "weighted earliness-tardiness"problem. Although DP expands somewhat the size of the problemsthat can be solved to optimality, its computing burden becomesonerous for more than 25 jobs.In an attempt to solve larger, and more realistic problems, a GeneticAlgorithm(GA) is presented in chapter 3. The salient feature of the GAmodel is that the "initial population" of trial solutions are not allrandomly generated but are constituted from a set of priority rules whichare known to be "good" relaxation (in the sense of being "close" to theoptimum) of the original problem. Also, generation of infeasible solutionsis avoided by the use of post-processing procedures after crossover andmutation operations. Computational results show that the GA approach arrivesto within 20% of the lower bound (and hence of the optimum) in very fewiterations.
5
Simonneau, Nicolas. "Hybrid flow shop scheduling with prescription constraints on jobs." Thesis, Virginia Tech, 2003. http://hdl.handle.net/10919/9659.
Full textAbstract:
The sponsor of the thesis is the Composite Unit of AIRBUS Nantes plant, which manufactures aircraft composite. The basic process to manufacture composite parts is to lay-up raw composite material on a tool and involves very costly means and raw material.
This process can be modeled as a two-stage hybrid flow shop problem with specific constraints, particularly prescription constraints on the jobs.
This thesis restates the practical problem as a scheduling problem by doing hypotheses and restrictions. Then, it designs a mathematical model based on time-indexed variables. This model has been implemented in an IP solver to solve real based scenarios. A heuristic algorithm is developed for obtaining good solutions quickly. Finally, the heuristic is used to increase the execution speed of the IP solver. This thesis concludes by a discussion on the advantages and disadvantages of each option (IP solver vs. heuristic software) for the sponsor.Master of Science
6
Yeleswarapu, Radhika M. "Scheduling Of 2-Operation Jobs On A Single Machine To Minimize The Number Of Tardy Jobs." [Tampa, Fla.] : University of South Florida, 2003. http://purl.fcla.edu/fcla/etd/SFE0000216.
Full text
7
Cutler, Mark Christopher. "A study of scheduling operations with preemptive jobs and global system interruptions /." Thesis, Connect to this title online; UW restricted, 1998. http://hdl.handle.net/1773/8729.
Full text
8
Spegal, Christopher S. "Unrelated Machine Scheduling with Deteriorating Jobs and Non-zero Ready Times." Ohio University / OhioLINK, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou154672272196773.
Full text
9
Gangammanavar, Harshavardhana J. "OPTIMAL CODING AND SCHEDULING TECHNIQUES FOR BROADCASTING DEADLINE CONSTRAINT TRAFFIC OVER UNRELIABLE WIRELESS CHANNELS." The Ohio State University, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=osu1262111942.
Full text
10
Korkmaz, Gediz. "Batch Scheduling Of Incompatible Jobs On A Single Reactor With Dynamic Arrivals." Master's thesis, METU, 2004. http://etd.lib.metu.edu.tr/upload/12605096/index.pdf.
Full textAbstract:
In this study, a single machine batch-scheduling problem with incompatible jobs
and dynamic arrivals is examined. The objective function is the minimization of
the total flow time of the jobs. For solving problems a case specific branch and
bound algorithm with a heuristic upper bound scheme and two alternative lower
bound procedures is used. An extensive computational experiment is conducted
to investigate the effects of certain parameters on the computation time. For the
most difficult parameter combination branch and bound algorithm can solve the
problems about 25 jobs with 4 different job types in a 10 minutes time on
average. For the problem types with higher number of jobs and the most difficult
parameter combination proposed upper bound heuristic can be used to obtain
near optimal solutions.
11
Utrera, Iglesias Gladys Miriam. ""Virtual malleability" applied to MPI jobs to improve their execution in a multiprogrammed environment"." Doctoral thesis, Universitat Politècnica de Catalunya, 2007. http://hdl.handle.net/10803/6013.
Full textAbstract:
This work focuses on scheduling of MPI jobs when executing in shared-memory multiprocessors (SMPs). The objective was to obtain the best performance in response time in multiprogrammed multiprocessors systems using batch systems, assuming all the jobs have the same priority.
To achieve that purpose, the benefits of supporting malleability on MPI jobs to reduce fragmentation and consequently improve the performance of the system were studied.
The contributions made in this work can be summarized as follows:
· Virtual malleability: A mechanism where a job is assigned a dynamic processor partition, where the number of processes is greater than the number of processors. The partition size is modified at runtime, according to external requirements such as the load of the system, by varying the multiprogramming level, making the job contend for resources with itself.
In addition to this, a mechanism which decides at runtime if applying local or global process queues to an application depending on the load balancing between processes of it.
· A job scheduling policy, that takes decisions such as how many processes to start with and the maximum multiprogramming degree based on the type and number of applications running and queued. Moreover, as soon as a job finishes execution and where there are queued jobs, this algorithm analyzes whether it is better to start execution of another job immediately or just wait until there are more resources available.
· A new alternative to backfilling strategies for the problema of window execution time expiring. Virtual malleability is applied to the backfilled job, reducing its partition size but without aborting or suspending it as in traditional backfilling.
The evaluation of this thesis has been done using a practical approach. All the proposals were implemented, modifying the three scheduling levels: queuing system, processor scheduler and runtime library.
The impact of the contributions were studied under several types of workloads, varying machine utilization, communication and, balance degree of the applications, multiprogramming level, and job size.
Results showed that it is possible to offer malleability over MPI jobs.
An application obtained better performance when contending for the resources with itself than with other applications, especially in workloads with high machine utilization. Load imbalance was taken into account obtaining better performance if applying the right queue type to each application independently.
The job scheduling policy proposed exploited virtual malleability by choosing at the beginning of execution some parameters like the number of processes and maximum multiprogramming level. It performed well under bursty workloads with low to medium machine utilizations.
However as the load increases, virtual malleability was not enough. That is because, when the machine is heavily loaded, the jobs, once shrunk are not able to expand, so they must be executed all the time with a partition smaller than the job size, thus degrading performance. Thus, at this point the job scheduling policy concentrated just in moldability.
Fragmentation was alleviated also by applying backfilling techniques to the job scheduling algorithm. Virtual malleability showed to be an interesting improvement in the window expiring problem. Backfilled jobs even on a smaller partition, can continue execution reducing memory swapping generated by aborts/suspensions In this way the queueing system is prevented from reinserting the backfilled job in the queue and re-executing it in the future.
12
Ogbu, Francis Akujobi. "The problem of scheduling jobs on machines through the method of simulated annealing." Thesis, University of Exeter, 1990. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.253545.
Full text
13
Speck, Jochen Matthias [Verfasser], and P. [Akademischer Betreuer] Sanders. "Theory and Engineering of Scheduling Parallel Jobs / Jochen Matthias Speck ; Betreuer: P. Sanders." Karlsruhe : KIT-Bibliothek, 2018. http://d-nb.info/1162540745/34.
Full text
14
Possani, Edgar. "Lot streaming and batch scheduling : splitting and grouping jobs to improve production efficiency." Thesis, University of Southampton, 2001. https://eprints.soton.ac.uk/50621/.
Full textAbstract:
This thesis deals with issues arising in manufacturing, in particular related to production efficiency. Lot streaming refers to the process of splitting jobs to move production through several stages as quickly as possible, whereas batch scheduling refers to the process of grouping jobs to improve the use of resources and customer satisfaction. We use a network representation and critical path approach to analyse the lot streaming problem of finding optimal sublot sizes and a job sequence in a two-machine flow shop with transportation and setup times. We introduce a model where the number of sublots for each job is not predetermined, presenting an algorithm to assign a new sublot efficiently, and discuss a heuristic to assign a fixed number of sublots between jobs. A model with several identical jobs in an multiple machine flow shop is analysed through a dominant machine approach to find optimal sublot sizes for jobs. For batch scheduling, we tackle the NP-hard problem of scheduling jobs on a batching machine with restricted batch size to minimise the maximum lateness. We design a branch and bound algorithm, and develop local search heuristics for the problem. Different neighbourhoods are compared, one of which is an exponential sized neighbourhood that can be searched in polynomial time. We develop dynamic programming algorithms to obtain lower bounds and explore neighbourhoods efficiently. The performance of the branch and bound algorithm and the local search heuristics is assessed and supported by extensive computational tests.
15
Wang, Zizhao. "Scheduling Periodic Jobs with Discretely Controllable Processing Time on Edge and Cloud Systems." Thesis, The University of Sydney, 2022. https://hdl.handle.net/2123/29833.
Full textAbstract:
In recent years, the rapid development of the processing capability of smart devices enables us to process a wide variety of intelligent applications in a variety of scenarios. However, due to the limited size and energy, current smart devices are still unable to provide sufficient computational capability when dealing with complex smart applications. Therefore, computation offloading becomes a natural solution. The resource-constrained devices can offload their computational jobs to an edge server or a cloud server to accelerate their computation processes. Other than computation offloading, under many real-world situations, the processing time of computational jobs can be shortened if an acceptable result is expected. This is referred to as discretely controllable processing time, where the original processing time can be shortened to a number of levels with less satisfactory but acceptable processing results.
In this thesis, we are motivated to investigate how to accelerate the computation on the edge/cloud computing systems by combining the advantages of both computation offloading and controllable processing time under different network conditions. We formulate and solve three scheduling problems of periodic jobs with discretely controllable processing time (abbr. PDCPT) with respect to three scenarios: (1) When the edge/cloud system is experiencing the service outage and the computation offloading becomes unavailable, all jobs can only be accelerated by the controllable processing time on the local device. In this case, we propose a dynamic programming based algorithm (i.e., PDCPT-1 solver) to find the best achievable solution with a pseudo-polynomial computational complexity; (2) When the edge/cloud system is under a high-speed network condition with the negligible offloading delay, we can employ both the computation offloading and the controllable processing time to accelerate the computation. In this case, we propose another dynamic programming based algorithm (i.e., PDCPT-2 solver) to generate the optimal schedule within a pseudo-polynomial time; (3) When the edge/cloud system is under a low-speed network condition with the non-negligible offloading delay, we use both the computation offloading and the controllable processing time optimisation techniques. In this case, we design the PDCPT-3 solver to optimally schedule the jobs in a dynamic programming manner with a pseudo-polynomial computational complexity.
For each of the three mentioned cases, we developed novel solutions with analytical analysis. Meanwhile, we also evaluate the performance of the proposed algorithms through conducting a series of trace-driven simulations. For the first case, we design a real world experiment to show the practicability of the PDCPT-1 solver. All results, including both the experiments and simulations, demonstrate the effectiveness of our solutions in accelerating computation on edge/cloud systems.
16
Li, Dong. "An approximate dynamic programming approach to the scheduling of impatient jobs in a clearing system." Thesis, Lancaster University, 2010. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.557156.
Full textAbstract:
A single server is faced with a collection of jobs of varying duration and urgency. Before service starts, all jobs are subject to an initial triage, i.e., an assessment of both their urgency and of their service requirement, and are allocated to distinct classes. Jobs in one class have independent and identically distributed lifetimes, during which they are available for service. Should a job's lifetime expire before its service begins then it is lost from the system unserved. The goal is to schedule the jobs for service to maximise the expected number served to completion. Two heuristic policies have been proposed in the literature. One works well in a lino loss" limit while the other does so when lifetimes are short. Both can exhibit poor performance for problems at some distance from the regimes for which they were designed. We develop a robustly good heuristic by an approximative approach to the application of a single policy improvement step to the first policy above, in which we use a fluid model to obtain an approximation for its value function. The performance of the proposed heuristic is investigated in an extensive numerical study, This problem is substantially complicated if the initial triage is subject to error. We take a Bayesian approach to this additional uncertainty and discuss the design of heuristic policies to maximise the Bayes' return. We identify problem features for which a: high price is paid for poor initial triage and for which improvements in initial job assessment yield significant improvements in service outcomes. An analytical upper bound for the cost of imperfect classification is developed for exponentially distributed lifetime cases. An extensive numerical study is conducted to explore the behaviour of the cost in more general situations.
17
Mese, Emre M. "Cell Loading and Family Scheduling for Jobs with Individual Due Dates in a Shoe Manufacturing Company." Ohio University / OhioLINK, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1248975462.
Full text
18
Sparrman, Victoria. "Tube-tap or Earliest Due Date : What happens when all jobs cannot be completed?" Thesis, Umeå universitet, Institutionen för datavetenskap, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-184627.
Full textAbstract:
In this thesis the scheduling algorithms Earliest Due Date (EDD) and Tube-tap were compared to each other. They were compared to see which algorithm generated more net profit. They were compared to each other in four different scenarios. In each scenario there were two different machines and five different jobs. Each machine had a cost and a processing rate, and each job had a length, a deadline, and a profit. In every scenario all jobs could not be completed before their deadline. The net profit was calculated by subtracting the gross profit by the machine cost. The results for the Tube-tap and EDD algorithms were almost the same for both algorithms in the different scenarios. There was one scenario where Tube-tap gained 0.5 more in profit. This was because Tube-tap had 0.5 in machine cost for one of the scenarios. The conclusions was that there should be more experimentation to see how more profitable Tube-tap can be. Specifically, there should be testing on scenarios where all jobs cannot be completed before their deadlines, but the number of operations does not exceed the available space before the last deadline.
19
Han, Yong-Hee. "Dynamic Sequencing of Jobs on Conveyor Systems for Minimizing Changeovers." Diss., Georgia Institute of Technology, 2004. http://hdl.handle.net/1853/4877.
Full textAbstract:
This research investigates the problem of constrained sequencing of a set of jobs on a conveyor system with the objective of minimizing setup cost. A setup cost is associated with extra material, labor, or energy required due to the change of attributes in consecutive jobs at processing stations. A finite set of attributes is considered in this research. Sequencing is constrained by the availability of two elements ??orage buffers and conveyor junctions. The problem is motivated by the paint purge reduction problem at a major U.S. automotive manufacturer. First, a diverging junction with a sequence-independent setup cost and predefined attributes is modeled as an assignment problem and this model is extended by relaxing the initial assumptions in various ways. We also model the constrained sequencing problem with an off-line buffer and develop heuristics for efficiently getting a good quality solution by exploiting the special problem structure. Finally, we conduct sensitivity analysis using numerical experiments, explain the case study, and discuss the use of the simulation model as a supplementary tool for analyzing the constrained sequencing problem.
20
Hoyningen-Huene, Wiebke von [Verfasser]. "Essays on integrated maintenance and production scheduling with stochastic failures and non-resumable jobs / Wiebke von Hoyningen-Huene." Kiel : Universitätsbibliothek Kiel, 2015. http://d-nb.info/1075190509/34.
Full text
21
Motakpalli, Sankalpanand. "Aperiodic Job Handling in Cache-Based Real-Time Systems." OpenSIUC, 2017. https://opensiuc.lib.siu.edu/dissertations/1474.
Full textAbstract:
Real-time systems require a-priori temporal guarantees. While most of the normal operation in such a system is modeled using time-driven, hard-deadline sporadic tasks, event-driven behavior is modeled using aperiodic jobs with soft or no deadlines. To provide good Quality-of- Service for aperiodic jobs in the presence of sporadic tasks, aperiodic servers were introduced. Aperiodic servers act as a sporadic task and reserve a quota periodically to serve aperiodic jobs. The use of aperiodic servers in systems with caches is unsafe because aperiodic servers do not take into account, the indirect cache-related preemption delays that the execution of aperiodic jobs might impose on the lower-priority sporadic tasks, thus jeopardizing their safety. To solve this problem, we propose an enhancement to the aperiodic server that we call a Cache Delay Server. Here, each lower-priority sporadic task is assigned a delay quota to accommodate the cache-related preemption delay imposed by the execution of aperiodic jobs. Aperiodic jobs are allowed to execute at their assigned server priority only when all the active lower-priority sporadic tasks have a sufficient delay quota to accommodate it. Simulation results demonstrate that a Cache Delay Server ensures the safety of sporadic tasks while providing acceptable Quality-of-Service for aperiodic jobs. We propose a Integer Linear Program based approach to calculate delay quotas for sporadic tasks within a task set where Cache Delay Servers have been pre-assigned. We then propose algorithms to determine Cache Delay Server characteristics for a given sporadic task set. Finally, we extend the Cache Delay Server concept to multi-core architectures and propose approaches to schedule aperiodic jobs on appropriate Cache Delay Servers. Simulation results demonstrate the effectiveness of all our proposed algorithms in improving aperiodic job response times while maintaining the safety of sporadic task execution.
22
Hung, Hui-Chih. "Allocation of jobs and resources to work centers." Columbus, Ohio : Ohio State University, 2006. http://rave.ohiolink.edu/etdc/view?acc%5Fnum=osu1141849609.
Full text
23
Pastorelli, Mario. "Disciplines basées sur la taille pour la planification des jobs dans data-intensif scalable computing systems." Thesis, Paris, ENST, 2014. http://www.theses.fr/2014ENST0048/document.
Full textAbstract:
La dernière décennie a vu l’émergence de systèmes parallèles pour l’analyse de grosse quantités de données (DISC) , tels que Hadoop, et la demande qui en résulte pour les politiques de gestion des ressources, pouvant fournir des temps de réponse rapides ainsi qu’équité. Actuellement, les schedulers pour les systèmes de DISC sont axées sur l’équité, sans optimiser les temps de réponse. Les meilleures pratiques pour surmonter ce problème comprennent une intervention manuelle et une politique de planification ad-hoc , qui est sujette aux erreurs et qui est difficile à adapter aux changements. Dans cette thèse, nous nous concentrons sur la planification basée sur la taille pour les systèmes DISC. La principale contribution de ce travail est le scheduler dit Hadoop Fair Sojourn Protocol (HFSP), un ordonnanceur préemptif basé sur la taille qui tient en considération le vieillissement, ayant comme objectifs de fournir l’équité et des temps de réponse réduits. Hélas, dans les systèmes DISC, les tailles des job d’analyse de données ne sont pas connus a priori, donc, HFSP comprends un module d’estimation de taille, qui calcule une approximation et qui affine cette estimation au fur et a mesure du progrès d’un job. Nous démontrons que l’impact des erreurs d’estimation sur les politiques fondées sur la taille n’est pas significatif. Pour cette raison, et en vertu d’être conçu autour de l’idée de travailler avec des tailles estimées, HFSP est tolérant aux erreurs d’estimation de la taille des jobs. Nos résultats expérimentaux démontrent que, dans un véritable déploiement Hadoop avec des charges de travail réalistes, HFSP est plus performant que les politiques de scheduling existantes, a la fois en terme de temps de réponse et d’équité. En outre, HFSP maintiens ses bonnes performances même lorsque le cluster de calcul est lourdement chargé, car il focalises les ressources sur des jobs ayant priorité. HFSP est une politique préventive: la préemption dans un système DISC peut être mis en œuvre avec des techniques différentes. Les approches actuellement disponibles dans Hadoop ont des lacunes qui ont une incidence sur les performances du système. Par conséquence, nous avons mis en œuvre une nouvelle technique de préemption, appelé suspension, qui exploite le système d’exploitation pour effectuer la préemption d’une manière qui garantie une faible latence sans pénaliser l’avancement des jobs a faible prioritéThe past decade have seen the rise of data-intensive scalable computing (DISC) systems, such as Hadoop, and the consequent demand for scheduling policies to manage their resources, so that they can provide quick response times as well as fairness. Schedulers for DISC systems are usually focused on the fairness, without optimizing the response times. The best practices to overcome this problem include a manual and ad-hoc control of the scheduling policy, which is error-prone and difficult to adapt to changes. In this thesis we focus on size-based scheduling for DISC systems. The main contribution of this work is the Hadoop Fair Sojourn Protocol (HFSP) scheduler, a size-based preemptive scheduler with aging; it provides fairness and achieves reduced response times thanks to its size-based nature. In DISC systems, job sizes are not known a-priori: therefore, HFSP includes a job size estimation module, which computes approximated job sizes and refines these estimations as jobs progress. We show that the impact of estimation errors on the size-based policies is not signifi- cant, under conditions which are verified in a system such as Hadoop. Because of this, and by virtue of being designed around the idea of working with estimated sizes, HFSP is largely tolerant to job size estimation errors. Our experimental results show that, in a real Hadoop deployment and with realistic workloads, HFSP performs better than the built-in scheduling policies, achieving both fairness and small mean response time. Moreover, HFSP maintains its good performance even when the cluster is heavily loaded, by focusing the resources to few selected jobs with the smallest size. HFSP is a preemptive policy: preemption in a DISC system can be implemented with different techniques. Approaches currently available in Hadoop have shortcomings that impact on the system performance. Therefore, we have implemented a new preemption technique, called suspension, that exploits the operating system primitives to implement preemption in a way that guarantees low latency without penalizing low-priority jobs
24
Keller, R., and O. Ilchuk. "The task of schedule optimizing for partially ordered jobs on machines with different productivity in the presence of idle time." Thesis, Sumy State University, 2017. http://essuir.sumdu.edu.ua/handle/123456789/55651.
Full textAbstract:
The subject of this article is the job shop
scheduling problem and methods for solving this
problem. It contains model for the task of schedule
optimizing for partially ordered jobs on machines
with different productivity in the presence of idle time
and algorithm for getting initial permissible solution.
25
Renaud-Goud, Paul. "Energy-aware scheduling : complexity and algorithms." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2012. http://tel.archives-ouvertes.fr/tel-00744247.
Full textAbstract:
In this thesis we have tackled a few scheduling problems under energy constraint, since the energy issue is becoming crucial, for both economical and environmental reasons. In the first chapter, we exhibit tight bounds on the energy metric of a classical algorithm that minimizes the makespan of independent tasks. In the second chapter, we schedule several independent but concurrent pipelined applications and address problems combining multiple criteria, which are period, latency and energy. We perform an exhaustive complexity study and describe the performance of new heuristics. In the third chapter, we study the replica placement problem in a tree network. We try to minimize the energy consumption in a dynamic frame. After a complexity study, we confirm the quality of our heuristics through a complete set of simulations. In the fourth chapter, we come back to streaming applications, but in the form of series-parallel graphs, and try to map them onto a chip multiprocessor. The design of a polynomial algorithm on a simple problem allows us to derive heuristics on the most general problem, whose NP-completeness has been proven. In the fifth chapter, we study energy bounds of different routing policies in chip multiprocessors, compared to the classical XY routing, and develop new routing heuristics. In the last chapter, we compare the performance of different algorithms of the literature that tackle the problem of mapping DAG applications to minimize the energy consumption.
26
Shevade, Shrinidhee. "Minimizing Makespan of a Multi-mode, Multi-item Packaging Machine Subject to Resource and Inventory Constraints." University of Cincinnati / OhioLINK, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1471254235.
Full text
27
ZHANG, RUI-XIONG, and 張瑞雄. "Scheduling jobs to men with different capabilities." Thesis, 1988. http://ndltd.ncl.edu.tw/handle/06023576561304156442.
Full text
28
Yang, Jui-Ling, and 楊瑞玲. "Scheduling Independent Jobs on Unrelated Parallel Machines." Thesis, 1996. http://ndltd.ncl.edu.tw/handle/28689606830728299653.
Full textAbstract:
碩士國立清華大學
工業工程研究所
84
In this paper, we propose several heuristics to schedule independent jobs in unrelated parallel machine systems. We limit our scope to the static and deterministic problem. The system we investigate consists of several different types of machines, and machines of different types are unrelated and machines of the same type are identical. Both the total lateness and total tardiness problem in this thesis are formulated into mathematical programming models. Nevertheless, an optimal solution may not be available; and in practice, all that is required may be just a near-optimal solution. The proposed heuristics contain two phases: The first phase is to allocate jobs onto machines or subsystems. The second phase is to sequence the jobs on each machine or in each subsystem. The first phase consists of two stages: the constructing stage and the allocating stage. The constructing stage is to construct an initial job list which is used as reference to allocate jobs. The allocating stage is to allocate jobs onto machines or subsystems by balancing machine workload or by the criterion taking performacne measure directly into account. The second stage is composed of the sequencing stage which determine the final processing order of jobs on each machine. For the total lateness problem, the SPT rule is adopted to determine the final job sequence; for the total tardiness problem, the TPI rule is adopted in this stage.
29
JHUO, YI-JYUN, and 卓宜君. "Study of Parallel Machine with Malleable Jobs Scheduling." Thesis, 2016. http://ndltd.ncl.edu.tw/handle/49185722253600149909.
Full textAbstract:
碩士國立雲林科技大學
工業工程與管理系
104
In actual production scheduling, in order to make order can be delievered before the due date, many factory usually split the order, and assign order to multi-machine to make these order can be processed simultaneously. But, how to split the order which considers due date and sequence-independent setup time, then scheduling the split order is extremely difficult. Therefore, this study considers job splitting on identical parallel machine scheduling, to make total tardiness is minimize. Then we use mixed integer programming as the basic architecture to construct the model.
30
Lin, Chien-Hao, and 林建豪. "A Study of Parallel Jobs Scheduling with Dependence." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/r6hfbr.
Full textAbstract:
碩士靜宜大學
資訊管理學系研究所
97
With the development of computer technology, clusters have become one of the trends in high performance computing. When large-scale jobs are to be executed, clusters usually have better performance than super computers, various types of scheduling policies have been implemented. In previous studies, simple batch scheduling algorithms like First Come First Serve (FCFS) may waste waiting time when longer jobs run, and system utilization is lower. In order to solve the problems, the space-sharing policy like backfill and the time-sharing policy like Gang scheduling have been provided to improve system utilization , and to overcome the problem of response time. Generally, most of jobs scheduling policies focus on time-sharing and space-sharing. In our study, we discuss the dependent jobs. There may be a relation that some jobs must have to be executed before the other. In order to schedule those jobs in parallel system, we provide a policy with the backfill strategy to schedule dependent jobs to decrease total execution times. We use a directed acyclic graph to express the dependence between jobs. There must be one of topological sequences that can be scheduled with backfill strategy and the makespan is minimum. We call it the smallest topological sequence. When topological sort begins, if the number of vertex’s indegree is 0, the vertex will be outputted. If there are over one vertexes whose indegree is 0, the one which will be outputted dependent on their outdegree numbers. First, we decide the vertex with maximal outdegrees will be outputted first . The result is called maximum outdegree topological sort. Second, we decide the vertex with minimal outdegrees will be outputted first. The result is called minimum outdegree topological sort. Third, we output vertex randomly and the result is named random outdegree topological sort. Then, we schedule the three topological sequences by the backfill strategy. Finally, we find that the makespan of the maximum outdegree topological sequence is very close to the makespan of the smallest topological sequence.
31
Lin, Yu-Pin, and 林鈺濱. "Scheduling Jobs of Differentiated Services in Computational Grids." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/18635913619095111491.
Full text
32
Fang, Huan-yi, and 方歡毅. "A Study on Deteriorating Group Jobs Scheduling Problem." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/08104765528532318350.
Full textAbstract:
碩士國立臺灣科技大學
資訊管理系
101
Deteriorating jobs scheduling has received great attention in the past two decades. In many realistic situations, a job processed later needs more time for processing than the same job when it is processed earlier; this phenomenon is known as deteriorating jobs. We consider the case of deteriorating jobs whose processing times are a simple linear increasing function of their starting time. On the other hand, the production efficiency can be increased by grouping jobs with similar processing requirements. This phenomenon is known as the group technology(GT) in the literature. However, there exist only a few result considering scheduling problems with deteriorating jobs and group technology simultaneously. In this paper, we consider two group scheduling problems of minimizing the makespan with deteriorating jobs. One is a group scheduling problem with deteriorating jobs under GT assumption, and the other is a problem with the same model without GT assumption. We provide a polynomial-time algorithm and a branch-and-bound algorithm to solve the problems respectively.
33
Lin, Guan-jhong, and 林冠仲. "Scheduling equal-length jobs on uniform parallel machines." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/64892507742230945241.
Full textAbstract:
碩士逢甲大學
工業工程與系統管理學研究所
98
Scheduling n identical jobs on m uniform parallel machines to minimize scheduling criteria is very common in practice. The case of identical jobs within a batch is common in manufacturing systems, where the products have identical designs or processing times on the same machine. Also, factories often buy new equipment but retain their slower, older equipment; this results in machines that have different processing speeds. In this research, we proposed several linear programming (LP) models and efficient algorithms to solve the problems of scheduling identical jobs on uniform parallel machines to minimize several regular performance measures individually. Moreover, some extensions of this problem, such as jobs may be required to meet a common due date, or jobs may be restricted by unequal release dates, or when jobs preemptions are allowed are also considered. Performance measures include makespan, total completion time, total weighted completion time, total tardiness, total weighted tardiness, number of tardy jobs, weighted number of tardy jobs, total earliness and tardiness, total weighted earliness and tardiness, and maximum lateness. Computational results showed that proposed LP models can find optimal solutions with equal or less time complexities when compared to other existing LP models. Moreover, proposed algorithms outperform other existing algorithms in terms of solution quality.
34
He, Chia-Chi, and 何嘉綺. "Single-machine scheduling problem with stepwise deteriorating jobs." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/70055140730758225200.
Full textAbstract:
碩士逢甲大學
統計與精算所
95
In many real situations, it is found that if certain maintenance procedures fail to be completed prior to a pre-specified deteriorating date, then the jobs will require extra time for successful completion. In this thesis, a single-machine total completion time problem with stepwise deteriorating jobs is considered. A branch-and-bound method incorporated with several dominance properties and a lower bound was developed to derive the optimal solution for this problem. In addition, a weight-combination search algorithm is proposed to search for the near-optimal solution. Computational results indicate that the branch-and-bound algorithm can solve most of the problems for up to 24 jobs in a reasonable amount of time. Moreover, the proposed heuristic algorithm is accurate with mean error percentages of less than 0.3%.
35
LAN, WU SHANG, and 吳尚倫. "Scheduling of jobs in Taiwan chemical material industry." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/76970559302936491169.
Full textAbstract:
碩士中國科技大學
運籌管理研究所
96
The problem we consider here is one faced by a chemical material company, which is famous in north Taiwan. In the studied company, we collect a set of real data during May 2007. To solve the problems of total flow time and tardiness and number of tardy jobs, we use the SPT (shortest processing time), EDD (earliest due date) and Moore algorithms as the solution methods. To improve the performance of the company, effective scheduling procedures are introduced in our research. Form the practical viewpoint, there are two reasons that three algorithms can be adopted in the company. First, reducing the production cost can be achieved by using the algorithms. Second, the manager can easily derive a feasible schedule in a short time by running a computer program. Currently, we are trying to implement three algorithms in the studied company.
36
Chang, Chia-Wen, and 張家雯. "Unrelated parallel-machine scheduling with deteriorating jobs and rejection." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/92804513623199071204.
Full textAbstract:
碩士南開科技大學
車輛與機電產業研究所
102
This paper aimed to investigate the unrelated parallel-machine scheduling with deteriorating jobs and rejection. The objective is to find the rejected jobs, the non-rejected jobs, and the optimal non-rejected job sequence so that the cost function that includes the weighted of total load, total completion time, and total absolute deviation of completion time plus the total penalty of the rejected jobs would be minimized. Results showed that the problem is polynomial time solvable when the number of machine is fixed.
37
Lee, Chi-Hsuan, and 李圻軒. "Scheduling of Deteriorating Jobs with Time Dependent Selling Prices." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/10068707902409886265.
Full textAbstract:
碩士國立交通大學
工業工程與管理學系
100
We consider a scheduling problem of deteriorating jobs with time dependent selling prices on a single machine. Our goal is to maximize revenues of jobs. We first formulate the problem as a non-linear programming problem (NLP). Then, we explore several important properties and theorems of the optimal schedule. Under some specific conditions, our problem is equivalent to the problem proposed by Mosheiov (1991). Finally, we propose a heuristic to find a near optimal solution based on these properties. Numerical studies are implemented to verify the efficiency of our heuristic.
38
Chou, Yang-Ru, and 周揚儒. "Scheduling Techniques for Periodic Jobs in a Heterogeneous Environment." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/70727414870921736702.
Full textAbstract:
碩士國立臺灣大學
資訊工程學研究所
97
This paper considers a scheduling problem for periodic jobs in a heterogeneous environment. There are m heterogeneous processors and n identical jobs. Jobs are released one at a time periodically. Each job is assigned to a processor for execution. Preemption is not allowed. The goal is to minimize the summation of completion time of all the jobs. We borrow the idea from Dessouky et al. to propose an approximation algorithm for scheduling identical and periodic jobs to heterogeneous processors. We show that there is a competetive ratio related to the processing time of the fastest processor in this problem.
39
Liu, Chia-Cheng, and 劉家成. "Randomized Local Policies for Scheduling Games with Multi-jobs Players." Thesis, 2016. http://ndltd.ncl.edu.tw/handle/82478591453504218586.
Full textAbstract:
碩士國立交通大學
資訊管理研究所
104
Most research on scheduling games assumes a single-job model, where each job can be seen as a distinct player. Each player decides to assign her job to a machine to minimize her own completion time according to a local policy for ordering jobs on a machine. The price of anarchy as a measure of the overall performance is defined as the ratio between the social cost of the worst equilibrium and the optimal social cost. A common social cost is the sum of all weighted completion times. In this thesis, we study multi-job scheduling games, where each player owns several jobs and can move any subset of her jobs arbitrarily to minimize the sum of weighted completion times of her jobs. We analyze weak equilibria for multi-job scheduling games with a randomized local policy and give a price-of-anarchy upper bound less than 4.
40
Liao, Yu-Sheng, and 廖祐紳. "Robust Single Machine Scheduling to Minimize Number of Tardy Jobs." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/u2ax3z.
Full textAbstract:
碩士國立臺北科技大學
工業工程與管理研究所
98
The general scheduling problem that assume that all task parameters can be specified precisely in advance of scheduling, allowing the outcome of any scheduling decision to be determined exactly, but many parameters cannot be executed exactly. Therefore, the object value in the uncertainties of its parameters are likely to result in small changes in the efficiency of this solution may deteriorate or become infeasible. This paper we considering the single machine、the job of processing time uncertainty in order to minimize the objective function of the number of tardy jobs, Bertsimas and Sim [13] of the model used to establish the robust of consideration of mixed integer programming model, Then use this concept to fully list method , Backward-Forward Heuristic and Genetic Algorithm to obtain a robust solution with robust , To provide a more reliable scheduling decision-making model .
41
Huang, Wei-ting, and 黃偉婷. "Job Shop Scheduling with Machine Availability Constraint and Recirculation Jobs." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/63202050759960491438.
Full textAbstract:
碩士國立中央大學
工業管理研究所
99
In the thesis we consider the job shop scheduling with machine availability restrictions and recirculation jobs while minimizing the makespan. Each machine is not continuously available at all time. On the other hand, each machine is not always available for processing. Besides, each job may visit a machine more than once and has to be processed at an available interval. We propose the branch and bound algorithms to solve the scheduling problem optimally. First, we decide that the minimum number of each machine unavailable interval. Then, we modify disjunctive graph technique to model the scheduling problem with the dummy jobs that is denoted by each machine unavailable interval. Also, each dummy job is no-wait attribute. Second, we develop the branching scheme to generate the entire tree and use propositions to transfer infeasible solutions to feasible. Then, determine the lower bound of the makespan as the length of the longest path. Finally, we use algorithm to recalculate the scheduling problem until find an optimal solution. Experimental designs are used to evaluate and analyze the performance of the algorithm. Computational analysis shows that the lower bound proposed is effective and can eliminate more than 60% node when the total operation numbers. The results show that the lower bound affect the solution time used by branch and bound algorithm.
42
Chen, Chien-Wei. "Energy Efficient Real-Time Co-Scheduling of Multimedia DSP Jobs." 2007. http://www.cetd.com.tw/ec/thesisdetail.aspx?etdun=U0001-2507200715242900.
Full text
43
Ming-Tai, Kuo, and 郭明泰. "Scheduling of jobs in a flowshop---the development and evaluation of multi criterias scheduling heuristic algoruthm." Thesis, 1999. http://ndltd.ncl.edu.tw/handle/77544488175903104968.
Full text
44
Yerra, Singu Babu. "Scheduling of jobs on a single machine to minimize total cost." Thesis, 1996. http://spectrum.library.concordia.ca/4159/1/MM10911.pdf.
Full text
45
Chen, Yu-Hsi, and 陳育習. "Scheduling multi-operation jobs with job families on a single machine." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/nnwjbp.
Full textAbstract:
碩士中原大學
工業工程研究所
93
We consider the single machine multi-operation jobs scheduling problem. Each job consists of several operations that belong to different families. In a schedule, each family of job operations may be processed in batches with each batch incurring a set-up time. A job completes when all of its operations have been processed. Our analysis covers two classic optimality criteria: minimize the maximum lateness and minimize the sum of the job completion times. In the literature, we develop a optimal sequence about minimize the maximum lateness problem and consider both exact and heuristic to minimize the sum of the job completion times. The exact approach are tested and detailed computational results are given and we also propose a heuristic algorithms and their results are reported.
46
Liang, Hua-Chan, and 梁華展. "Scheduling preemptive jobs to specific time intervals of uniform parallel machines." Thesis, 2015. http://ndltd.ncl.edu.tw/handle/5h4na3.
Full textAbstract:
碩士國立交通大學
工業工程與管理系所
103
We consider the scheduling problem of uniform parallel machines with preemptive jobs, where machines have specific available time intervals. Our study considers arbitrary time intervals, Integer and Rational job processing time, and then formulates the Mixed Integer Programming models. For our problem, we consider three different objectives─(1) to maximize the basic processing time assigned to machines with specific available time intervals, (2) to minimize the completion time of the last job, and (3) to minimize the completion time of the last job on some specific machines. Finally, we develop three algorithms based on Optimum Finishing Time (OFT) concept which solve the three objectives in polynomial time.
47
Chi-Fan, Wang, and 王啟帆. "Scheduling of Jobs in Taiwan Textile Industries — For a Dyeing case." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/54988491001461038113.
Full textAbstract:
碩士中國科技大學
運籌管理研究所
96
The purpose of this study is to discuss a problem of textile company in Taiwan. We collect a set of real data from May 2007 to June 2007. To solve the problem of the studied company, we apply the early-lately due date algorithm in this study. The company provides the information of several jobs, which includes processing times and due dates. Using the information, we can solve the problem of inventory level and tardiness. For simplicity, we present the forward and backward algorithm to eliminate any unnecessary calculation in our study. After using the two methods, we compare the optimal scheduling cost with the highest scheduling cost. It is found that the difference of two costs is large. In such a situation, we have known that production scheduling plays a key role in our research. Two efficient and effective algorithms are proposed as the solution method. We can conclude that the proposed algorithms can reduce the production cost and increase the company output.
48
Shie, Wan-Ling, and 謝婉玲. "Two-machine flowshop scheduling to minimize the number of tardy jobs." Thesis, 2004. http://ndltd.ncl.edu.tw/handle/95667435044788596189.
Full textAbstract:
碩士中原大學
工業工程研究所
92
This paper considers a hybrid two-stage flowshop problem with a batch processor in stage 1 and a discrete processor in stage 2. Each batch processor can process Z jobs simultaneously and has the fixed processing time. The objective is to minimize the total number of tardy jobs. This problem is shown to be NP-hard. Several properties and lower bound are developed. A heuristic algorithm and a branch and bound algorithm are proposed. The performance ratios of the heuristic algorithm and computational results are presented.
49
Ben, Wang，Chau, and 王昭斌. "Scheduling to maximize the number of jobs finished within delivery range." Thesis, 1994. http://ndltd.ncl.edu.tw/handle/96411519229354283158.
Full textAbstract:
碩士輔仁大學
管理科學研究所
82
Delivery range represents that time of delivery permitted is confined in an interval. The earliest delivery time per- mitted is called the earliest due date and the latest de- livery time permitted is called the latest due date. De- livery range is between the two time points, the earliest and the latest due date. In the field of production scheduling research, we consider the delivery range to instead of a fixed due date. That is completely different from the others who traditionally regards a single time point as due date. Factly, the decisions of delivery date should be a complex relation between productivity of supp- lier and the urgent condition of the customer. So a single due date can't cover the situation which we actually face to. For the reason, this paper offers the delivery range concept and then the supplier and the customer can decide their earliest and latest permitted delivery time which are accepted by each other. This is useful to make maximal pro- fit. For the above explanation, we know this hypothesis for delivery range is a very special theme. This can create a new direction for the scheduling theory. The paper focuses on Production Scheduling in delivery range and proceeds to study. The main contribution is as below : 1. We use the maximum number of non-early jobs finished whi- ch can match the earliest due date as measure criterion in a single machine scheduling problem and develop an efficient algorithm. 2. We use the maximum number of non-tardy jobs finished whi- ch can match the latest due date as measure criterion in a single machine scheduling problem and develop an efficient algorithm. 3. We use B&B method to solve the maximum number of jobs fi- nished within delivery range as measure criterion. Furth- ermore, a heuristic algorithm is also completed.
50
Lin, Wen-Yi, and 林文儀. "Some scheduling problems with time-dependent learning effect and deteriorating jobs." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/76946570346267098343.
Full textAbstract:
博士國立雲林科技大學
工業工程與管理研究所博士班
102
Scheduling problem plays an important role in a manufacturing system, and numerous scheduling problems have been studied for many years. In classical scheduling problems, the processing times of jobs are assumed to be fixed values. However, in many realistic situations, the actual processing time of a job can be more or less than its normal processing time if it is scheduled later. Hence, this research aims at the time-dependent learning effects scheduling problems and takes various situations into account to construct an effective mathematical model to meet some objectives for a specified scheduling problem. Under the proposed model, we shows that the polynomially solvable for some single-machine and flowshop scheduling problems with the certain performance measures such as makespan, total completion time, and total weighted completion time.