NASA Technical Reports Server (NTRS)
Moore, J. E.
1975-01-01
An enumeration algorithm is presented for solving a scheduling problem similar to the single machine job shop problem with sequence dependent setup times. The scheduling problem differs from the job shop problem in two ways. First, its objective is to select an optimum subset of the available tasks to be performed during a fixed period of time. Secondly, each task scheduled is constrained to occur within its particular scheduling window. The algorithm is currently being used to develop typical observational timelines for a telescope that will be operated in earth orbit. Computational times associated with timeline development are presented.
JIT single machine scheduling problem with periodic preventive maintenance
NASA Astrophysics Data System (ADS)
Shahriari, Mohammadreza; Shoja, Naghi; Zade, Amir Ebrahimi; Barak, Sasan; Sharifi, Mani
2016-03-01
This article investigates a JIT single machine scheduling problem with a periodic preventive maintenance. Also to maintain the quality of the products, there is a limitation on the maximum number of allowable jobs in each period. The proposed bi-objective mixed integer model minimizes total earliness-tardiness and makespan simultaneously. Due to the computational complexity of the problem, multi-objective particle swarm optimization (MOPSO) algorithm is implemented. Also, as well as MOPSO, two other optimization algorithms are used for comparing the results. Eventually, Taguchi method with metrics analysis is presented to tune the algorithms' parameters and a multiple criterion decision making technique based on the technique for order of preference by similarity to ideal solution is applied to choose the best algorithm. Comparison results confirmed the supremacy of MOPSO to the other algorithms.
Manipulating Tabu List to Handle Machine Breakdowns in Job Shop Scheduling Problems
NASA Astrophysics Data System (ADS)
Nababan, Erna Budhiarti; SalimSitompul, Opim
2011-06-01
Machine breakdowns in a production schedule may occur on a random basis that make the well-known hard combinatorial problem of Job Shop Scheduling Problems (JSSP) becomes more complex. One of popular techniques used to solve the combinatorial problems is Tabu Search. In this technique, moves that will be not allowed to be revisited are retained in a tabu list in order to avoid in gaining solutions that have been obtained previously. In this paper, we propose an algorithm to employ a second tabu list to keep broken machines, in addition to the tabu list that keeps the moves. The period of how long the broken machines will be kept on the list is categorized using fuzzy membership function. Our technique are tested to the benchmark data of JSSP available on the OR library. From the experiment, we found that our algorithm is promising to help a decision maker to face the event of machine breakdowns.
Scheduling of flow shop problems on 3 machines in fuzzy environment with double transport facility
NASA Astrophysics Data System (ADS)
Sathish, Shakeela; Ganesan, K.
2016-06-01
Flow shop scheduling is a decision making problem in production and manufacturing field which has a significant impact on the performance of an organization. When the machines on which jobs are to be processed are placed at different places, the transportation time plays a significant role in production. Further two different transport agents where 1st takes the job from 1st machine to 2nd machine and then returns back to the first machine and the 2nd takes the job from 2nd machine to 3rd machine and then returns back to the 2nd machine are also considered. We propose a method to minimize the total make span; without converting the fuzzy processing time to classical numbers by using a new type of fuzzy arithmetic and a fuzzy ranking method. A numerical example is provided to explain the proposed method.
Some single-machine scheduling problems with learning effects and two competing agents.
Li, Hongjie; Li, Zeyuan; Yin, Yunqiang
2014-01-01
This study considers a scheduling environment in which there are two agents and a set of jobs, each of which belongs to one of the two agents and its actual processing time is defined as a decreasing linear function of its starting time. Each of the two agents competes to process its respective jobs on a single machine and has its own scheduling objective to optimize. The objective is to assign the jobs so that the resulting schedule performs well with respect to the objectives of both agents. The objective functions addressed in this study include the maximum cost, the total weighted completion time, and the discounted total weighted completion time. We investigate three problems arising from different combinations of the objectives of the two agents. The computational complexity of the problems is discussed and solution algorithms where possible are presented. PMID:25009829
Some Single-Machine Scheduling Problems with Learning Effects and Two Competing Agents
Li, Hongjie; Li, Zeyuan; Yin, Yunqiang
2014-01-01
This study considers a scheduling environment in which there are two agents and a set of jobs, each of which belongs to one of the two agents and its actual processing time is defined as a decreasing linear function of its starting time. Each of the two agents competes to process its respective jobs on a single machine and has its own scheduling objective to optimize. The objective is to assign the jobs so that the resulting schedule performs well with respect to the objectives of both agents. The objective functions addressed in this study include the maximum cost, the total weighted completion time, and the discounted total weighted completion time. We investigate three problems arising from different combinations of the objectives of the two agents. The computational complexity of the problems is discussed and solution algorithms where possible are presented. PMID:25009829
Hybrid Metaheuristics for Solving a Fuzzy Single Batch-Processing Machine Scheduling Problem
Molla-Alizadeh-Zavardehi, S.; Tavakkoli-Moghaddam, R.; Lotfi, F. Hosseinzadeh
2014-01-01
This paper deals with a problem of minimizing total weighted tardiness of jobs in a real-world single batch-processing machine (SBPM) scheduling in the presence of fuzzy due date. In this paper, first a fuzzy mixed integer linear programming model is developed. Then, due to the complexity of the problem, which is NP-hard, we design two hybrid metaheuristics called GA-VNS and VNS-SA applying the advantages of genetic algorithm (GA), variable neighborhood search (VNS), and simulated annealing (SA) frameworks. Besides, we propose three fuzzy earliest due date heuristics to solve the given problem. Through computational experiments with several random test problems, a robust calibration is applied on the parameters. Finally, computational results on different-scale test problems are presented to compare the proposed algorithms. PMID:24883359
Hybrid metaheuristics for solving a fuzzy single batch-processing machine scheduling problem.
Molla-Alizadeh-Zavardehi, S; Tavakkoli-Moghaddam, R; Lotfi, F Hosseinzadeh
2014-01-01
This paper deals with a problem of minimizing total weighted tardiness of jobs in a real-world single batch-processing machine (SBPM) scheduling in the presence of fuzzy due date. In this paper, first a fuzzy mixed integer linear programming model is developed. Then, due to the complexity of the problem, which is NP-hard, we design two hybrid metaheuristics called GA-VNS and VNS-SA applying the advantages of genetic algorithm (GA), variable neighborhood search (VNS), and simulated annealing (SA) frameworks. Besides, we propose three fuzzy earliest due date heuristics to solve the given problem. Through computational experiments with several random test problems, a robust calibration is applied on the parameters. Finally, computational results on different-scale test problems are presented to compare the proposed algorithms. PMID:24883359
NASA Astrophysics Data System (ADS)
Li, Kai; Yang, Shan-Lin; Ren, Ming-Lun
2011-10-01
This article considers the single-machine scheduling problem to minimise the total resource consumption under the constraint that the makespan does not exceed a given limit, in which the release date of a job is a linear decreasing continuous function of the resource consumption. This problem is NP-hard in the strong sense. We design a simulated annealing (SA) algorithm to obtain the near-optimal solution with high quality. Two operators, right-move and left-move, are defined and their influences on the resource consumption are analysed. We use two operations, insert and swap, to generate the neighbourhood, and discuss how to calculate the change of total resource consumption. To evaluate the performance of the proposed algorithm, we relax the problem to an assignment problem, and obtain a lower bound by the Hungary method. And then, we improve its quality by Chu's method. Based on the settings that Janiak provided, we generate the random test data in our experiments to simulate the ingot preheating and hot-rolling process in steel mills. The accuracy and efficiency of the proposed SA algorithm are tested based on those data with problem sizes varying from 50 to 200 jobs. The computational results indicate that the SA approach is promising and capable of solving large-scale problems in a reasonable time.
Xu, Zhenzhen; Zou, Yongxing; Kong, Xiangjie
2015-01-01
To our knowledge, this paper investigates the first application of meta-heuristic algorithms to tackle the parallel machines scheduling problem with weighted late work criterion and common due date ([Formula: see text]). Late work criterion is one of the performance measures of scheduling problems which considers the length of late parts of particular jobs when evaluating the quality of scheduling. Since this problem is known to be NP-hard, three meta-heuristic algorithms, namely ant colony system, genetic algorithm, and simulated annealing are designed and implemented, respectively. We also propose a novel algorithm named LDF (largest density first) which is improved from LPT (longest processing time first). The computational experiments compared these meta-heuristic algorithms with LDF, LPT and LS (list scheduling), and the experimental results show that SA performs the best in most cases. However, LDF is better than SA in some conditions, moreover, the running time of LDF is much shorter than SA. PMID:26702371
Gang scheduling a parallel machine
Gorda, B.C.; Brooks, E.D. III.
1991-03-01
Program development on parallel machines can be a nightmare of scheduling headaches. We have developed a portable time sharing mechanism to handle the problem of scheduling gangs of processors. User program and their gangs of processors are put to sleep and awakened by the gang scheduler to provide a time sharing environment. Time quantums are adjusted according to priority queues and a system of fair share accounting. The initial platform for this software is the 128 processor BBN TC2000 in use in the Massively Parallel Computing Initiative at the Lawrence Livermore National Laboratory. 2 refs., 1 fig.
Gang scheduling a parallel machine
Gorda, B.C.; Brooks, E.D. III.
1991-12-01
Program development on parallel machines can be a nightmare of scheduling headaches. We have developed a portable time sharing mechanism to handle the problem of scheduling gangs of processes. User programs and their gangs of processes are put to sleep and awakened by the gang scheduler to provide a time sharing environment. Time quantum are adjusted according to priority queues and a system of fair share accounting. The initial platform for this software is the 128 processor BBN TC2000 in use in the Massively Parallel Computing Initiative at the Lawrence Livermore National Laboratory.
NASA Astrophysics Data System (ADS)
Joo, Cheol Min; Kim, Byung Soo
2012-09-01
This article considers a parallel machine scheduling problem with ready times, due times and sequence-dependent setup times. The objective of this problem is to determine the allocation policy of jobs and the scheduling policy of machines to minimize the weighted sum of setup times, delay times and tardy times. A mathematical model for optimal solution is derived. An in-depth analysis of the model shows that it is very complicated and difficult to obtain optimal solutions as the problem size becomes large. Therefore, two meta-heuristics, genetic algorithm (GA) and a new population-based evolutionary meta-heuristic called self-evolution algorithm (SEA), are proposed. The performances of the meta-heuristic algorithms are evaluated through comparison with optimal solutions using several randomly generated examples.
NASA Astrophysics Data System (ADS)
Liou, Cheng-Dar; Hsieh, Yi-Chih; Chen, Yin-Yann
2013-01-01
This article investigates the two-machine flow-shop group scheduling problem (GSP) with sequence-dependent setup and removal times, and job transportation times between machines. The objective is to minimise the total completion time. As known, this problem is an NP-hard problem and generalises the typical two-machine GSPs. In this article, a new encoding scheme based on permutation representation is proposed to transform a random job permutation to a feasible permutation for GSPs. The proposed encoding scheme simultaneously determines both the sequence of jobs in each group and the sequence of groups. By reasonably combining particle swarm optimisation (PSO) and genetic algorithm (GA), we develop a fast and easily implemented hybrid algorithm (HA) for solving the considered problems. The effectiveness and efficiency of the proposed HA are demonstrated and compared with those of standard PSO and GA by numerical results of various tested instances with group numbers up to 20. In addition, three different lower bounds are developed to evaluate the solution quality of the HA. Limited numerical results indicate that the proposed HA is a viable and effective approach for the studied two-machine flow-shop group scheduling problem.
Single-machine group scheduling problems with deteriorating and learning effect
NASA Astrophysics Data System (ADS)
Xingong, Zhang; Yong, Wang; Shikun, Bai
2016-07-01
The concepts of deteriorating jobs and learning effects have been individually studied in many scheduling problems. However, most studies considering the deteriorating and learning effects ignore the fact that production efficiency can be increased by grouping various parts and products with similar designs and/or production processes. This phenomenon is known as 'group technology' in the literature. In this paper, a new group scheduling model with deteriorating and learning effects is proposed, where learning effect depends not only on job position, but also on the position of the corresponding job group; deteriorating effect depends on its starting time of the job. This paper shows that the makespan and the total completion time problems remain polynomial optimal solvable under the proposed model. In addition, a polynomial optimal solution is also presented to minimise the maximum lateness problem under certain agreeable restriction.
NASA Astrophysics Data System (ADS)
Xu, Ye; Wang, Ling; Wang, Shengyao; Liu, Min
2013-12-01
In this article, an effective shuffled frog-leaping algorithm (SFLA) is proposed to solve the hybrid flow-shop scheduling problem with identical parallel machines (HFSP-IPM). First, some novel heuristic decoding rules for both job order decision and machine assignment are proposed. Then, three hybrid decoding schemes are designed to decode job order sequences to schedules. A special bi-level crossover and multiple local search operators are incorporated in the searching framework of the SFLA to enrich the memetic searching behaviour and to balance the exploration and exploitation capabilities. Meanwhile, some theoretical analysis for the local search operators is provided for guiding the local search. The parameter setting of the algorithm is also investigated based on the Taguchi method of design of experiments. Finally, numerical testing based on well-known benchmarks and comparisons with some existing algorithms are carried out to demonstrate the effectiveness of the proposed algorithm.
NASA Astrophysics Data System (ADS)
Hasani, Keramat; Kravchenko, Svetlana A.; Werner, Frank
2016-01-01
This article considers the problem of scheduling a given set of n jobs on two identical parallel machines with a single server. Each job must be processed on one of the machines. Before processing, the server has to set up the relevant machine. The objective is to minimize the makespan. For this unary NP-hard problem, two fast constructive algorithms with a complexity of O(n2) are presented. The performance of these algorithms is evaluated for instances with up to 10,000 jobs. Computational results indicate that the algorithms have an excellent performance for very large instances so that the obtained objective function values are very close to a lower bound, and in many cases even an optimal solution is achieved. Superiority over all existing algorithms is obtained by sequencing the jobs on the two machines so that the machine idle time and the server waiting time are minimized. In doing so, the characteristics of an optimal solution resulting from its relevant lower bound are taken into account.
NASA Astrophysics Data System (ADS)
Kaplan, Sezgin; Rabadi, Ghaith
2013-01-01
This article addresses the aerial refuelling scheduling problem (ARSP), where a set of fighter jets (jobs) with certain ready times must be refuelled from tankers (machines) by their due dates; otherwise, they reach a low fuel level (deadline) incurring a high cost. ARSP is an identical parallel machine scheduling problem with release times and due date-to-deadline windows to minimize the total weighted tardiness. A simulated annealing (SA) and metaheuristic for randomized priority search (Meta-RaPS) with the newly introduced composite dispatching rule, apparent piecewise tardiness cost with ready times (APTCR), are applied to the problem. Computational experiments compared the algorithms' solutions to optimal solutions for small problems and to each other for larger problems. To obtain optimal solutions, a mixed integer program with a piecewise weighted tardiness objective function was solved for up to 12 jobs. The results show that Meta-RaPS performs better in terms of average relative error but SA is more efficient.
Gang scheduling a parallel machine. Revision 1
Gorda, B.C.; Brooks, E.D. III
1991-12-01
Program development on parallel machines can be a nightmare of scheduling headaches. We have developed a portable time sharing mechanism to handle the problem of scheduling gangs of processes. User programs and their gangs of processes are put to sleep and awakened by the gang scheduler to provide a time sharing environment. Time quantum are adjusted according to priority queues and a system of fair share accounting. The initial platform for this software is the 128 processor BBN TC2000 in use in the Massively Parallel Computing Initiative at the Lawrence Livermore National Laboratory.
Parallel machine scheduling with a common server
Hall, N.; Sriskandarajah, C.; Potts, C.
1994-12-31
This paper considers the nonpreemptive scheduling of a given set of jobs on several identical, parallel machines. Each job must be processed on one of the machines. Prior to processing, a job must be loaded (setup) by a single server onto the relevant machine. The server may be a human operator, a robot, or a piece of specialized equipment. We study a number of classical scheduling objectives in this environment, including makespan, maximum lateness, the sum of completion times, the number of late jobs, and total tardiness, as well as weighted versions of some of these. The number of machines may be constant or arbitrary. Setup times may be unit, equal, or arbitrary. Processing times may be unit or arbitrary. For each problem considered, we attempt to provide either an efficient algorithm, or a proof that such an algorithm is unlikely to exist. Our results provide a mapping of the computational complexity of these problems. Included in these results are generalizations of the classical algorithms of Moore, Lawler and Moore and Lawler. In addition, we describe two heuristics for makespan scheduling in this environment, and provide an exact analysis of their worst-case performance.
NASA Astrophysics Data System (ADS)
He, Yong; Sun, Li
2015-05-01
In this paper, we introduce a group scheduling model with general deteriorating jobs and learning effects in which deteriorating jobs and learning effects are both considered simultaneously. This means that the actual processing time of a job depends not only on the processing time of the jobs already processed, but also on its scheduled position. In our model, the group setup times are general linear functions of their starting times and the jobs in the same group have general position-dependent learning effects and time-dependent deterioration. The objective of scheduling problems is to minimise the makespan and the sum of completion times, respectively. We show that the problems remain solvable in polynomial time under the proposed model.
A Study on Machine Maintenance Scheduling Using Distributed Cooperative Approach
NASA Astrophysics Data System (ADS)
Tsujibe, Akihisa; Kaihara, Toshiya; Fujii, Nobutada; Nonaka, Youichi
In this study, we propose a distributed cooperative scheduling method, and apply the method into a machine maintenance scheduling problem in re-entrant production systems. As one of the distributed cooperative scheduling methods, we focus on Lagrangian decomposition and coordination (LDC) method, and formulate the machine maintenance scheduling problem with LDC so as to improve computational efficiency by decomposing an original scheduling problem into several sub-problems. The derived solutions by solving the decomposed dual problem are converted into feasible solutions with a heuristic procedure applied in this study. The proposed approach regards maintenance as job with starting and finishing time constraints, so that product and maintenance schedule can realize proper maintenance operations without losing productivity. We show the effectiveness of the proposed method in several simulation experiments.
Static scheduling for dynamic dataflow machines
Beck, M.; Pingali, K.K. ); Nicolau, A. )
1990-12-01
Dynamic dataflow machines exploit parallelism among loop iterations by loop unraveling: all iterations of the loop are started together and operations in various iterations execute when their input data are present. Unbounded loop unraveling can strain the resources available on the machine and, in extreme cases, deadlock can occur due to overcommitment of resources. Previous efforts to address this problem have focused mainly on run-time mechanisms of debatable utility. Loop bounding, a compile-time technique, controls parallelism by permitting a fixed number of iterations to execute at one time. In this paper, the authors argue that loop bounding can lead to inefficient use of resources, and we propose an alternative way of compiling loops of overlapped execution of loop iterations. The authors introduce the notion of a stage decomposition of a loop, which defines a partition of the operations in a loop iteration into stages, and they show that the problem of choosing a stage decomposition for a particular loop can be tackled by applying static scheduling techniques like the ones used in generating code for VLIW machines. These techniques permit the compiler to allocate resources more skillfully than with loop bounding. The practical utility of stage decomposition remains to be tested on a real dataflow machine. In the absence of one, the authors describe how the schema could be implemented on the Monsoon dataflow machine being built at MIT.
Integrated network design and scheduling problems :
Nurre, Sarah G.; Carlson, Jeffrey J.
2014-01-01
We consider the class of integrated network design and scheduling problems. These problems focus on selecting and scheduling operations that will change the characteristics of a network, while being speci cally concerned with the performance of the network over time. Motivating applications of INDS problems include infrastructure restoration after extreme events and building humanitarian distribution supply chains. While similar models have been proposed, no one has performed an extensive review of INDS problems from their complexity, network and scheduling characteristics, information, and solution methods. We examine INDS problems under a parallel identical machine scheduling environment where the performance of the network is evaluated by solving classic network optimization problems. We classify that all considered INDS problems as NP-Hard and propose a novel heuristic dispatching rule algorithm that selects and schedules sets of arcs based on their interactions in the network. We present computational analysis based on realistic data sets representing the infrastructures of coastal New Hanover County, North Carolina, lower Manhattan, New York, and a realistic arti cial community CLARC County. These tests demonstrate the importance of a dispatching rule to arrive at near-optimal solutions during real-time decision making activities. We extend INDS problems to incorporate release dates which represent the earliest an operation can be performed and exible release dates through the introduction of specialized machine(s) that can perform work to move the release date earlier in time. An online optimization setting is explored where the release date of a component is not known.
A simple neural network scheduler for real-time machine task scheduling
Gritzo, R.E.
1991-01-01
The recent development of a new generation of automated radionuclide assay equipment in our facility requires embedded software at each machine for the scheduling of tasks. The execution time requirements of real-time embedded software limit the complexity of the scheduler design. By representing the scheduling problem properly, a simple backpropagation neural network performs the scheduling function within the imposed requirements. Operational tests have demonstrated that the neural network scheduler has met all development goals and is superior to the previous approaches. 3 refs., 1 tab.
A threshold scheduling strategy for Sisal on distributed memory machines
Pande, S.S.; Agrawal, D.P.; Mauney, J. )
1994-05-01
The problem of scheduling tasks on distributed memory machines is known to be NP-complete in the strong sense, ruling out the possibility of a pseudo-polynomial algorithm. This paper introduces a new heuristic algorithm for scheduling Sisal (Streams and Iterations In a Single Assignment Language) programs on a distributed memory machine, Intel Touchstone i860. The compile time scheduling method works on IF-2, an intermediate form based on the dataflow parallelism in the program. The authors initially carry out a dependence analysis, to bind the implicit dependencies across IF-2 graph boundaries, followed by a cost assignment based on Intel Touchstone i860 timings. The scheduler works in two phases. The first phase of the scheduler finds the earliest and latest completion times of each task given by the shortest and longest paths from root task to the given task respectively. A threshold defined as the difference between the latest and the earliest start times of the task, is found. The scheduler varies the value of the allowable threshold, and determines the best value for minimal schedule length. In the second phase of the scheduler, the authors merge the processors to generate schedule to match the available number of processors. Schedule results for several benchmark programs have been included to demonstrate the effectiveness of their approach.
The Microchp Scheduling Problem
NASA Astrophysics Data System (ADS)
Bosman, M. G. C.; Bakker, V.; Molderink, A.; Hurink, J. L.; Smit, G. J. M.
2009-08-01
The increasing penetration of renewable energy sources, the demand for more energy efficient electricity production and the increase in distributed electricity generation causes a shift in the way electricity is produced and consumed. The downside of these changes in the electricity grid is that network stability and controllability becomes more difficult compared to the old situation. The new network has to accommodate various means of production, consumption and buffering and needs to offer control over the energy flows between these three elements. In order to offer such a control mechanism we need to know more about the individual aspects. In this paper we focus on the modelling of distributed production. Especially we look at the use of microCHP (Combined Heat and Power) appliances in a group of houses. The problem of planning the production runs of the microCHP is modelled via an ILP formulation both for a single house and for a group of houses.
Bounded Parallel-Batch Scheduling on Unrelated Parallel Machines
NASA Astrophysics Data System (ADS)
Miao, Cuixia; Zhang, Yuzhong; Wang, Chengfei
In this paper, we consider the bounded parallel-batch scheduling problem on unrelated parallel machines. Problems R m |B|F are NP-hard for any objective function F. For this reason, we discuss the special case with p ij = p i for i = 1, 2, ⋯ , m , j = 1, 2, ⋯ , n. We give optimal algorithms for the general scheduling to minimize total weighted completion time, makespan and the number of tardy jobs. And we design pseudo-polynomial time algorithms for the case with rejection penalty to minimize the makespan and the total weighted completion time plus the total penalty of the rejected jobs, respectively.
A simple neural network scheduler for real-time machine task scheduling
Gritzo, R.E.
1992-06-01
The recent development of a new generation of automated radionuclide assay equipment in our facility requires embedded software at each machine for the scheduling of sample assay tasks. The execution time requirements of real-time embedded software limit the complexity of the schedular software. By representing the scheduling problem properly, a simple backpropagation neural network performs the scheduling function within the imposed requirements. Operational tests have demonstrated that the neural network schedular has met all development goals and is superior to the previous approaches. This paper describes the design and development of the neural network task scheduler. In addition, several aspects of the practical application of neural networks to real-world problems are discussed.
A simple neural network scheduler for real-time machine task scheduling
Gritzo, R.E.
1992-01-01
The recent development of a new generation of automated radionuclide assay equipment in our facility requires embedded software at each machine for the scheduling of sample assay tasks. The execution time requirements of real-time embedded software limit the complexity of the schedular software. By representing the scheduling problem properly, a simple backpropagation neural network performs the scheduling function within the imposed requirements. Operational tests have demonstrated that the neural network schedular has met all development goals and is superior to the previous approaches. This paper describes the design and development of the neural network task scheduler. In addition, several aspects of the practical application of neural networks to real-world problems are discussed.
Two-machine flow shop scheduling integrated with preventive maintenance planning
NASA Astrophysics Data System (ADS)
Wang, Shijin; Liu, Ming
2016-02-01
This paper investigates an integrated optimisation problem of production scheduling and preventive maintenance (PM) in a two-machine flow shop with time to failure of each machine subject to a Weibull probability distribution. The objective is to find the optimal job sequence and the optimal PM decisions before each job such that the expected makespan is minimised. To investigate the value of integrated scheduling solution, computational experiments on small-scale problems with different configurations are conducted with total enumeration method, and the results are compared with those of scheduling without maintenance but with machine degradation, and individual job scheduling combined with independent PM planning. Then, for large-scale problems, four genetic algorithm (GA) based heuristics are proposed. The numerical results with several large problem sizes and different configurations indicate the potential benefits of integrated scheduling solution and the results also show that proposed GA-based heuristics are efficient for the integrated problem.
Job shop scheduling problem with late work criterion
NASA Astrophysics Data System (ADS)
Piroozfard, Hamed; Wong, Kuan Yew
2015-05-01
Scheduling is considered as a key task in many industries, such as project based scheduling, crew scheduling, flight scheduling, machine scheduling, etc. In the machine scheduling area, the job shop scheduling problems are considered to be important and highly complex, in which they are characterized as NP-hard. The job shop scheduling problems with late work criterion and non-preemptive jobs are addressed in this paper. Late work criterion is a fairly new objective function. It is a qualitative measure and concerns with late parts of the jobs, unlike classical objective functions that are quantitative measures. In this work, simulated annealing was presented to solve the scheduling problem. In addition, operation based representation was used to encode the solution, and a neighbourhood search structure was employed to search for the new solutions. The case studies are Lawrence instances that were taken from the Operations Research Library. Computational results of this probabilistic meta-heuristic algorithm were compared with a conventional genetic algorithm, and a conclusion was made based on the algorithm and problem.
Bicriteria single machine scheduling with setup times and learning effects
NASA Astrophysics Data System (ADS)
Soroush, H. M.
2012-11-01
We study a bicriteria single machine scheduling problem with job-dependent and past-sequence-dependent (psd) setup time and job-dependent learning effects. The goal is to find the optimal sequence that minimizes a linear combination of a pair of performance criteria consisting of the makespan, the total completion time, and the total absolute differences in completion times. We show that special cases of the resulting three problems are solvable polynomially. However, the general cases cannot be solved in polynomial time; thus, branch-and-bound (B&B) methods are proposed to derive optimal sequences. Computational results demonstrate that the B&B methods solve relatively large problem instances in reasonable amounts of time.
NASA Astrophysics Data System (ADS)
Afzalirad, Mojtaba; Rezaeian, Javad
2016-04-01
This study involves an unrelated parallel machine scheduling problem in which sequence-dependent set-up times, different release dates, machine eligibility and precedence constraints are considered to minimize total late works. A new mixed-integer programming model is presented and two efficient hybrid meta-heuristics, genetic algorithm and ant colony optimization, combined with the acceptance strategy of the simulated annealing algorithm (Metropolis acceptance rule), are proposed to solve this problem. Manifestly, the precedence constraints greatly increase the complexity of the scheduling problem to generate feasible solutions, especially in a parallel machine environment. In this research, a new corrective algorithm is proposed to obtain the feasibility in all stages of the algorithms. The performance of the proposed algorithms is evaluated in numerical examples. The results indicate that the suggested hybrid ant colony optimization statistically outperformed the proposed hybrid genetic algorithm in solving large-size test problems.
Group scheduling problems in directional sensor networks
NASA Astrophysics Data System (ADS)
Singh, Alok; Rossi, André
2015-12-01
This article addresses the problem of scheduling a set of groups of directional sensors arising as a result of applying an exact or a heuristic approach for solving a problem involving directional sensors. The problem seeks a schedule for these groups that minimizes the total energy consumed in switching from one group to the next group in the schedule. In practice, when switching from a group to the next one, active sensors in the new group have to rotate in order to face their working direction. These rotations consume energy, and the problem is to schedule the groups so as to minimize the total amount of energy consumed by all the sensor rotations, knowing the initial angular positions of all the sensors. In this article, it is assumed that energy consumption is proportional to the angular movement for all the sensors. Another problem version is also investigated that seeks to minimize the total time during which the sensor network cannot cover all the targets because active sensors are rotating. Both problems are proved to be ?-hard, and a lower bound for the first problem is presented. A greedy heuristic and a genetic algorithm are also proposed for addressing the problem of minimizing total rotation in the general case. Finally, a local search is also proposed to improve the solutions obtained through a genetic algorithm.
Prediction Based Proactive Thermal Virtual Machine Scheduling in Green Clouds
Kinger, Supriya; Kumar, Rajesh; Sharma, Anju
2014-01-01
Cloud computing has rapidly emerged as a widely accepted computing paradigm, but the research on Cloud computing is still at an early stage. Cloud computing provides many advanced features but it still has some shortcomings such as relatively high operating cost and environmental hazards like increasing carbon footprints. These hazards can be reduced up to some extent by efficient scheduling of Cloud resources. Working temperature on which a machine is currently running can be taken as a criterion for Virtual Machine (VM) scheduling. This paper proposes a new proactive technique that considers current and maximum threshold temperature of Server Machines (SMs) before making scheduling decisions with the help of a temperature predictor, so that maximum temperature is never reached. Different workload scenarios have been taken into consideration. The results obtained show that the proposed system is better than existing systems of VM scheduling, which does not consider current temperature of nodes before making scheduling decisions. Thus, a reduction in need of cooling systems for a Cloud environment has been obtained and validated. PMID:24737962
Prediction based proactive thermal virtual machine scheduling in green clouds.
Kinger, Supriya; Kumar, Rajesh; Sharma, Anju
2014-01-01
Cloud computing has rapidly emerged as a widely accepted computing paradigm, but the research on Cloud computing is still at an early stage. Cloud computing provides many advanced features but it still has some shortcomings such as relatively high operating cost and environmental hazards like increasing carbon footprints. These hazards can be reduced up to some extent by efficient scheduling of Cloud resources. Working temperature on which a machine is currently running can be taken as a criterion for Virtual Machine (VM) scheduling. This paper proposes a new proactive technique that considers current and maximum threshold temperature of Server Machines (SMs) before making scheduling decisions with the help of a temperature predictor, so that maximum temperature is never reached. Different workload scenarios have been taken into consideration. The results obtained show that the proposed system is better than existing systems of VM scheduling, which does not consider current temperature of nodes before making scheduling decisions. Thus, a reduction in need of cooling systems for a Cloud environment has been obtained and validated. PMID:24737962
Solving Stochastic Flexible Flow Shop Scheduling Problems with a Decomposition-Based Approach
NASA Astrophysics Data System (ADS)
Wang, K.; Choi, S. H.
2010-06-01
Real manufacturing is dynamic and tends to suffer a lot of uncertainties. Research on production scheduling under uncertainty has recently received much attention. Although various approaches have been developed for scheduling under uncertainty, this problem is still difficult to tackle by any single approach, because of its inherent difficulties. This chapter describes a decomposition-based approach (DBA) for makespan minimisation of a flexible flow shop (FFS) scheduling problem with stochastic processing times. The DBA decomposes an FFS into several machine clusters which can be solved more easily by different approaches. A neighbouring K-means clustering algorithm is developed to firstly group the machines of an FFS into an appropriate number of machine clusters, based on a weighted cluster validity index. A back propagation network (BPN) is then adopted to assign either the Shortest Processing Time (SPT) Algorithm or the Genetic Algorithm (GA) to generate a sub-schedule for each machine cluster. After machine grouping and approach assignment, an overall schedule is generated by integrating the sub-schedules of the machine clusters. Computation results reveal that the DBA is superior to SPT and GA alone for FFS scheduling under stochastic processing times, and that it can be easily adapted to schedule FFS under other uncertainties.
Job shop scheduling model for non-identic machine with fixed delivery time to minimize tardiness
NASA Astrophysics Data System (ADS)
Kusuma, K. K.; Maruf, A.
2016-02-01
Scheduling non-identic machines problem with low utilization characteristic and fixed delivery time are frequent in manufacture industry. This paper propose a mathematical model to minimize total tardiness for non-identic machines in job shop environment. This model will be categorized as an integer linier programming model and using branch and bound algorithm as the solver method. We will use fixed delivery time as main constraint and different processing time to process a job. The result of this proposed model shows that the utilization of production machines can be increase with minimal tardiness using fixed delivery time as constraint.
Optimum Production Control and Workforce Scheduling of Machining Project
NASA Astrophysics Data System (ADS)
Lan, Tian-Syung; Lo, Chih-Yao; Hou, Cheng-I.
Through the proposed model in this study, the production control with the consideration of workforce scheduling for advanced manufacturing systems becomes realistically and concretely solvable. This study not only meditates the concept of balancing machine productivity and human ability into the objective, but also implements Calculus of Variations to optimize the profit for a deterministic production quantity. In addition, the optimum solutions of dynamic productivity control and workforce scheduling are comprehensively provided. Moreover, the decision criteria for selecting the optimum solution and the sensitivity analysis of the critical variables are fully discussed. This study definitely contributes the applicable strategy to control the productivity and workforce in manufacturing and provides the valuable tool to conclusively optimize the profit of a machining project for operations research in today`s manufacturing industry with profound insight.
Optimal pre-scheduling of problem remappings
NASA Technical Reports Server (NTRS)
Nicol, David M.; Saltz, Joel H.
1987-01-01
A large class of scientific computational problems can be characterized as a sequence of steps where a significant amount of computation occurs each step, but the work performed at each step is not necessarily identical. Two good examples of this type of computation are: (1) regridding methods which change the problem discretization during the course of the computation, and (2) methods for solving sparse triangular systems of linear equations. Recent work has investigated a means of mapping such computations onto parallel processors; the method defines a family of static mappings with differing degrees of importance placed on the conflicting goals of good load balance and low communication/synchronization overhead. The performance tradeoffs are controllable by adjusting the parameters of the mapping method. To achieve good performance it may be necessary to dynamically change these parameters at run-time, but such changes can impose additional costs. If the computation's behavior can be determined prior to its execution, it can be possible to construct an optimal parameter schedule using a low-order-polynomial-time dynamic programming algorithm. Since the latter can be expensive, the performance is studied of the effect of a linear-time scheduling heuristic on one of the model problems, and it is shown to be effective and nearly optimal.
NASA Astrophysics Data System (ADS)
Wang, Li-Chih; Chen, Yin-Yann; Chen, Tzu-Li; Cheng, Chen-Yang; Chang, Chin-Wei
2014-10-01
This paper studies a solar cell industry scheduling problem, which is similar to traditional hybrid flowshop scheduling (HFS). In a typical HFS problem, the allocation of machine resources for each order should be scheduled in advance. However, the challenge in solar cell manufacturing is the number of machines that can be adjusted dynamically to complete the job. An optimal production scheduling model is developed to explore these issues, considering the practical characteristics, such as hybrid flowshop, parallel machine system, dedicated machines, sequence independent job setup times and sequence dependent job setup times. The objective of this model is to minimise the makespan and to decide the processing sequence of the orders/lots in each stage, lot-splitting decisions for the orders and the number of machines used to satisfy the demands in each stage. From the experimental results, lot-splitting has significant effect on shortening the makespan, and the improvement effect is influenced by the processing time and the setup time of orders. Therefore, the threshold point to improve the makespan can be identified. In addition, the model also indicates that more lot-splitting approaches, that is, the flexibility of allocating orders/lots to machines is larger, will result in a better scheduling performance.
A hybrid dynamic harmony search algorithm for identical parallel machines scheduling
NASA Astrophysics Data System (ADS)
Chen, Jing; Pan, Quan-Ke; Wang, Ling; Li, Jun-Qing
2012-02-01
In this article, a dynamic harmony search (DHS) algorithm is proposed for the identical parallel machines scheduling problem with the objective to minimize makespan. First, an encoding scheme based on a list scheduling rule is developed to convert the continuous harmony vectors to discrete job assignments. Second, the whole harmony memory (HM) is divided into multiple small-sized sub-HMs, and each sub-HM performs evolution independently and exchanges information with others periodically by using a regrouping schedule. Third, a novel improvisation process is applied to generate a new harmony by making use of the information of harmony vectors in each sub-HM. Moreover, a local search strategy is presented and incorporated into the DHS algorithm to find promising solutions. Simulation results show that the hybrid DHS (DHS_LS) is very competitive in comparison to its competitors in terms of mean performance and average computational time.
Frutos, M; Méndez, M; Tohmé, F; Broz, D
2013-01-01
Many of the problems that arise in production systems can be handled with multiobjective techniques. One of those problems is that of scheduling operations subject to constraints on the availability of machines and buffer capacity. In this paper we analyze different Evolutionary multiobjective Algorithms (MOEAs) for this kind of problems. We consider an experimental framework in which we schedule production operations for four real world Job-Shop contexts using three algorithms, NSGAII, SPEA2, and IBEA. Using two performance indexes, Hypervolume and R2, we found that SPEA2 and IBEA are the most efficient for the tasks at hand. On the other hand IBEA seems to be a better choice of tool since it yields more solutions in the approximate Pareto frontier. PMID:24489502
Frutos, M.; Méndez, M.; Tohmé, F.; Broz, D.
2013-01-01
Many of the problems that arise in production systems can be handled with multiobjective techniques. One of those problems is that of scheduling operations subject to constraints on the availability of machines and buffer capacity. In this paper we analyze different Evolutionary multiobjective Algorithms (MOEAs) for this kind of problems. We consider an experimental framework in which we schedule production operations for four real world Job-Shop contexts using three algorithms, NSGAII, SPEA2, and IBEA. Using two performance indexes, Hypervolume and R2, we found that SPEA2 and IBEA are the most efficient for the tasks at hand. On the other hand IBEA seems to be a better choice of tool since it yields more solutions in the approximate Pareto frontier. PMID:24489502
Run-time scheduling and execution of loops on message passing machines
NASA Technical Reports Server (NTRS)
Crowley, Kay; Saltz, Joel; Mirchandaney, Ravi; Berryman, Harry
1989-01-01
Sparse system solvers and general purpose codes for solving partial differential equations are examples of the many types of problems whose irregularity can result in poor performance on distributed memory machines. Often, the data structures used in these problems are very flexible. Crucial details concerning loop dependences are encoded in these structures rather than being explicitly represented in the program. Good methods for parallelizing and partitioning these types of problems require assignment of computations in rather arbitrary ways. Naive implementations of programs on distributed memory machines requiring general loop partitions can be extremely inefficient. Instead, the scheduling mechanism needs to capture the data reference patterns of the loops in order to partition the problem. First, the indices assigned to each processor must be locally numbered. Next, it is necessary to precompute what information is needed by each processor at various points in the computation. The precomputed information is then used to generate an execution template designed to carry out the computation, communication, and partitioning of data, in an optimized manner. The design is presented for a general preprocessor and schedule executer, the structures of which do not vary, even though the details of the computation and of the type of information are problem dependent.
Run-time scheduling and execution of loops on message passing machines
NASA Technical Reports Server (NTRS)
Saltz, Joel; Crowley, Kathleen; Mirchandaney, Ravi; Berryman, Harry
1990-01-01
Sparse system solvers and general purpose codes for solving partial differential equations are examples of the many types of problems whose irregularity can result in poor performance on distributed memory machines. Often, the data structures used in these problems are very flexible. Crucial details concerning loop dependences are encoded in these structures rather than being explicitly represented in the program. Good methods for parallelizing and partitioning these types of problems require assignment of computations in rather arbitrary ways. Naive implementations of programs on distributed memory machines requiring general loop partitions can be extremely inefficient. Instead, the scheduling mechanism needs to capture the data reference patterns of the loops in order to partition the problem. First, the indices assigned to each processor must be locally numbered. Next, it is necessary to precompute what information is needed by each processor at various points in the computation. The precomputed information is then used to generate an execution template designed to carry out the computation, communication, and partitioning of data, in an optimized manner. The design is presented for a general preprocessor and schedule executer, the structures of which do not vary, even though the details of the computation and of the type of information are problem dependent.
Eroglu, Duygu Yilmaz; Ozmutlu, H Cenk
2014-01-01
We developed mixed integer programming (MIP) models and hybrid genetic-local search algorithms for the scheduling problem of unrelated parallel machines with job sequence and machine-dependent setup times and with job splitting property. The first contribution of this paper is to introduce novel algorithms which make splitting and scheduling simultaneously with variable number of subjobs. We proposed simple chromosome structure which is constituted by random key numbers in hybrid genetic-local search algorithm (GAspLA). Random key numbers are used frequently in genetic algorithms, but it creates additional difficulty when hybrid factors in local search are implemented. We developed algorithms that satisfy the adaptation of results of local search into the genetic algorithms with minimum relocation operation of genes' random key numbers. This is the second contribution of the paper. The third contribution of this paper is three developed new MIP models which are making splitting and scheduling simultaneously. The fourth contribution of this paper is implementation of the GAspLAMIP. This implementation let us verify the optimality of GAspLA for the studied combinations. The proposed methods are tested on a set of problems taken from the literature and the results validate the effectiveness of the proposed algorithms. PMID:24977204
Hidri, Lotfi; Gharbi, Anis; Louly, Mohamed Aly
2014-01-01
We focus on the two-center hybrid flow shop scheduling problem with identical parallel machines and removal times. The job removal time is the required duration to remove it from a machine after its processing. The objective is to minimize the maximum completion time (makespan). A heuristic and a lower bound are proposed for this NP-Hard problem. These procedures are based on the optimal solution of the parallel machine scheduling problem with release dates and delivery times. The heuristic is composed of two phases. The first one is a constructive phase in which an initial feasible solution is provided, while the second phase is an improvement one. Intensive computational experiments have been conducted to confirm the good performance of the proposed procedures. PMID:25610911
A Solution Method of Scheduling Problem with Worker Allocation by a Genetic Algorithm
NASA Astrophysics Data System (ADS)
Osawa, Akira; Ida, Kenichi
In a scheduling problem with worker allocation (SPWA) proposed by Iima et al, the worker's skill level to each machine is all the same. However, each worker has a different skill level for each machine in the real world. For that reason, we propose a new model of SPWA in which a worker has the different skill level to each machine. To solve the problem, we propose a new GA for SPWA consisting of the following new three procedures, shortening of idle time, modifying infeasible solution to feasible solution, and a new selection method for GA. The effectiveness of the proposed algorithm is clarified by numerical experiments using benchmark problems for job-shop scheduling.
Machine Learning Based Online Performance Prediction for Runtime Parallelization and Task Scheduling
Li, J; Ma, X; Singh, K; Schulz, M; de Supinski, B R; McKee, S A
2008-10-09
With the emerging many-core paradigm, parallel programming must extend beyond its traditional realm of scientific applications. Converting existing sequential applications as well as developing next-generation software requires assistance from hardware, compilers and runtime systems to exploit parallelism transparently within applications. These systems must decompose applications into tasks that can be executed in parallel and then schedule those tasks to minimize load imbalance. However, many systems lack a priori knowledge about the execution time of all tasks to perform effective load balancing with low scheduling overhead. In this paper, we approach this fundamental problem using machine learning techniques first to generate performance models for all tasks and then applying those models to perform automatic performance prediction across program executions. We also extend an existing scheduling algorithm to use generated task cost estimates for online task partitioning and scheduling. We implement the above techniques in the pR framework, which transparently parallelizes scripts in the popular R language, and evaluate their performance and overhead with both a real-world application and a large number of synthetic representative test scripts. Our experimental results show that our proposed approach significantly improves task partitioning and scheduling, with maximum improvements of 21.8%, 40.3% and 22.1% and average improvements of 15.9%, 16.9% and 4.2% for LMM (a real R application) and synthetic test cases with independent and dependent tasks, respectively.
Application of a hybrid generation/utility assessment heuristic to a class of scheduling problems
NASA Technical Reports Server (NTRS)
Heyward, Ann O.
1989-01-01
A two-stage heuristic solution approach for a class of multiobjective, n-job, 1-machine scheduling problems is described. Minimization of job-to-job interference for n jobs is sought. The first stage generates alternative schedule sequences by interchanging pairs of schedule elements. The set of alternative sequences can represent nodes of a decision tree; each node is reached via decision to interchange job elements. The second stage selects the parent node for the next generation of alternative sequences through automated paired comparison of objective performance for all current nodes. An application of the heuristic approach to communications satellite systems planning is presented.
Solution of the NP-hard total tardiness minimization problem in scheduling theory
NASA Astrophysics Data System (ADS)
Lazarev, A. A.
2007-06-01
The classical NP-hard (in the ordinary sense) problem of scheduling jobs in order to minimize the total tardiness for a single machine 1‖Σ T j is considered. An NP-hard instance of the problem is completely analyzed. A procedure for partitioning the initial set of jobs into subsets is proposed. Algorithms are constructed for finding an optimal schedule depending on the number of subsets. The complexity of the algorithms is O( n 2Σ p j ), where n is the number of jobs and p j is the processing time of the jth job ( j = 1, 2, …, n).
Shi, Xuefei; Xu, Dehua
2014-01-01
We consider a single machine scheduling problem with multiple maintenance activities, where the maintenance duration function is of the linear form f(t) = a+bt with a ≥ 0 and b > 1. We propose an approximation algorithm named FFD-LS2I with a worst-case bound of 2 for problem. We also show that there is no polynomial time approximation algorithm with a worst-case bound less than 2 for the problem with b ≥ 0 unless P = NP, which implies that the FFD-LS2I algorithm is the best possible algorithm for the case b > 1 and that the FFD-LS algorithm, which is proposed in the literature, is the best possible algorithm for the case b ≤ 1 both from the worst-case bound point of view. PMID:24701177
AI techniques for a space application scheduling problem
NASA Technical Reports Server (NTRS)
Thalman, N.; Sparn, T.; Jaffres, L.; Gablehouse, D.; Judd, D.; Russell, C.
1991-01-01
Scheduling is a very complex optimization problem which can be categorized as an NP-complete problem. NP-complete problems are quite diverse, as are the algorithms used in searching for an optimal solution. In most cases, the best solutions that can be derived for these combinatorial explosive problems are near-optimal solutions. Due to the complexity of the scheduling problem, artificial intelligence (AI) can aid in solving these types of problems. Some of the factors are examined which make space application scheduling problems difficult and presents a fairly new AI-based technique called tabu search as applied to a real scheduling application. the specific problem is concerned with scheduling application. The specific problem is concerned with scheduling solar and stellar observations for the SOLar-STellar Irradiance Comparison Experiment (SOLSTICE) instrument in a constrained environment which produces minimum impact on the other instruments and maximizes target observation times. The SOLSTICE instrument will gly on-board the Upper Atmosphere Research Satellite (UARS) in 1991, and a similar instrument will fly on the earth observing system (Eos).
Handling Deafness Problem of Scheduled Multi-Channel Polling MACs
NASA Astrophysics Data System (ADS)
Jiang, Fulong; Liu, Hao; Shi, Longxing
Combining scheduled channel polling with channel diversity is a promising way for a MAC protocol to achieve high energy efficiency and performance under both light and heavy traffic conditions. However, the deafness problem may cancel out the benefit of channel diversity. In this paper, we first investigate the deafness problem of scheduled multi-channel polling MACs with experiments. Then we propose and evaluate two schemes to handle the deafness problem. Our experiment shows that deafness is a significant reason for performance degradation in scheduled multi-channel polling MACs. A proper scheme should be chosen depending on the traffic pattern and the design objective.
The application of artificial intelligence to astronomical scheduling problems
NASA Technical Reports Server (NTRS)
Johnston, Mark D.
1992-01-01
Efficient utilization of expensive space- and ground-based observatories is an important goal for the astronomical community; the cost of modern observing facilities is enormous, and the available observing time is much less than the demand from astronomers around the world. The complexity and variety of scheduling constraints and goals has led several groups to investigate how artificial intelligence (AI) techniques might help solve these kinds of problems. The earliest and most successful of these projects was started at Space Telescope Science Institute in 1987 and has led to the development of the Spike scheduling system to support the scheduling of Hubble Space Telescope (HST). The aim of Spike at STScI is to allocate observations to timescales of days to a week observing all scheduling constraints and maximizing preferences that help ensure that observations are made at optimal times. Spike has been in use operationally for HST since shortly after the observatory was launched in Apr. 1990. Although developed specifically for HST scheduling, Spike was carefully designed to provide a general framework for similar (activity-based) scheduling problems. In particular, the tasks to be scheduled are defined in the system in general terms, and no assumptions about the scheduling timescale are built in. The mechanisms for describing, combining, and propagating temporal and other constraints and preferences are quite general. The success of this approach has been demonstrated by the application of Spike to the scheduling of other satellite observatories: changes to the system are required only in the specific constraints that apply, and not in the framework itself. In particular, the Spike framework is sufficiently flexible to handle both long-term and short-term scheduling, on timescales of years down to minutes or less. This talk will discuss recent progress made in scheduling search techniques, the lessons learned from early HST operations, the application of Spike
Analysis of Feeder Bus Network Design and Scheduling Problems
Almasi, Mohammad Hadi; Karim, Mohamed Rehan
2014-01-01
A growing concern for public transit is its inability to shift passenger's mode from private to public transport. In order to overcome this problem, a more developed feeder bus network and matched schedules will play important roles. The present paper aims to review some of the studies performed on Feeder Bus Network Design and Scheduling Problem (FNDSP) based on three distinctive parts of the FNDSP setup, namely, problem description, problem characteristics, and solution approaches. The problems consist of different subproblems including data preparation, feeder bus network design, route generation, and feeder bus scheduling. Subsequently, descriptive analysis and classification of previous works are presented to highlight the main characteristics and solution methods. Finally, some of the issues and trends for future research are identified. This paper is targeted at dealing with the FNDSP to exhibit strategic and tactical goals and also contributes to the unification of the field which might be a useful complement to the few existing reviews. PMID:24526890
NASA Astrophysics Data System (ADS)
Konno, Yohko; Suzuki, Keiji
This paper describes an approach to development of a solution algorithm of a general-purpose for large scale problems using “Local Clustering Organization (LCO)” as a new solution for Job-shop scheduling problem (JSP). Using a performance effective large scale scheduling in the study of usual LCO, a solving JSP keep stability induced better solution is examined. In this study for an improvement of a performance of a solution for JSP, processes to a optimization by LCO is examined, and a scheduling solution-structure is extended to a new solution-structure based on machine-division. A solving method introduced into effective local clustering for the solution-structure is proposed as an extended LCO. An extended LCO has an algorithm which improves scheduling evaluation efficiently by clustering of parallel search which extends over plural machines. A result verified by an application of extended LCO on various scale of problems proved to conduce to minimizing make-span and improving on the stable performance.
Code of Federal Regulations, 2014 CFR
2014-07-01
... machine cards available from Federal Supply Schedule contracts. 101-26.509-1 Section 101-26.509-1 Public....509-1 Requisitioning tabulating machine cards available from Federal Supply Schedule contracts... electrical and mechanical contact tabulating machines, including aperture cards and copy cards....
Code of Federal Regulations, 2012 CFR
2012-07-01
... tabulating machine cards available from Federal Supply Schedule contracts. 101-26.509-1 Section 101-26.509-1... Programs § 101-26.509-1 Requisitioning tabulating machine cards available from Federal Supply Schedule... applicable to electrical and mechanical contact tabulating machines, including aperture cards and copy...
Code of Federal Regulations, 2013 CFR
2013-07-01
... machine cards available from Federal Supply Schedule contracts. 101-26.509-1 Section 101-26.509-1 Public....509-1 Requisitioning tabulating machine cards available from Federal Supply Schedule contracts... electrical and mechanical contact tabulating machines, including aperture cards and copy cards....
Code of Federal Regulations, 2011 CFR
2011-07-01
... machine cards available from Federal Supply Schedule contracts. 101-26.509-1 Section 101-26.509-1 Public....509-1 Requisitioning tabulating machine cards available from Federal Supply Schedule contracts... electrical and mechanical contact tabulating machines, including aperture cards and copy cards....
Meta-RaPS Algorithm for the Aerial Refueling Scheduling Problem
NASA Technical Reports Server (NTRS)
Kaplan, Sezgin; Arin, Arif; Rabadi, Ghaith
2011-01-01
The Aerial Refueling Scheduling Problem (ARSP) can be defined as determining the refueling completion times for each fighter aircraft (job) on multiple tankers (machines). ARSP assumes that jobs have different release times and due dates, The total weighted tardiness is used to evaluate schedule's quality. Therefore, ARSP can be modeled as a parallel machine scheduling with release limes and due dates to minimize the total weighted tardiness. Since ARSP is NP-hard, it will be more appropriate to develop a pproimate or heuristic algorithm to obtain solutions in reasonable computation limes. In this paper, Meta-Raps-ATC algorithm is implemented to create high quality solutions. Meta-RaPS (Meta-heuristic for Randomized Priority Search) is a recent and promising meta heuristic that is applied by introducing randomness to a construction heuristic. The Apparent Tardiness Rule (ATC), which is a good rule for scheduling problems with tardiness objective, is used to construct initial solutions which are improved by an exchanging operation. Results are presented for generated instances.
NASA Astrophysics Data System (ADS)
Guo, Peng; Cheng, Wenming; Wang, Yi
2015-11-01
This article considers the parallel machine scheduling problem with step-deteriorating jobs and sequence-dependent setup times. The objective is to minimize the total tardiness by determining the allocation and sequence of jobs on identical parallel machines. In this problem, the processing time of each job is a step function dependent upon its starting time. An individual extended time is penalized when the starting time of a job is later than a specific deterioration date. The possibility of deterioration of a job makes the parallel machine scheduling problem more challenging than ordinary ones. A mixed integer programming model for the optimal solution is derived. Due to its NP-hard nature, a hybrid discrete cuckoo search algorithm is proposed to solve this problem. In order to generate a good initial swarm, a modified Biskup-Hermann-Gupta (BHG) heuristic called MBHG is incorporated into the population initialization. Several discrete operators are proposed in the random walk of Lévy flights and the crossover search. Moreover, a local search procedure based on variable neighbourhood descent is integrated into the algorithm as a hybrid strategy in order to improve the quality of elite solutions. Computational experiments are executed on two sets of randomly generated test instances. The results show that the proposed hybrid algorithm can yield better solutions in comparison with the commercial solver CPLEX® with a one hour time limit, the discrete cuckoo search algorithm and the existing variable neighbourhood search algorithm.
NASA Astrophysics Data System (ADS)
Chang, Yung-Chia; Li, Vincent C.; Chiang, Chia-Ju
2014-04-01
Make-to-order or direct-order business models that require close interaction between production and distribution activities have been adopted by many enterprises in order to be competitive in demanding markets. This article considers an integrated production and distribution scheduling problem in which jobs are first processed by one of the unrelated parallel machines and then distributed to corresponding customers by capacitated vehicles without intermediate inventory. The objective is to find a joint production and distribution schedule so that the weighted sum of total weighted job delivery time and the total distribution cost is minimized. This article presents a mathematical model for describing the problem and designs an algorithm using ant colony optimization. Computational experiments illustrate that the algorithm developed is capable of generating near-optimal solutions. The computational results also demonstrate the value of integrating production and distribution in the model for the studied problem.
NASA Astrophysics Data System (ADS)
Sodan, Angela C.
Virtual machines have become an important approach to provide performance isolation and performance guarantees (QoS) on cluster servers and on many-core SMP servers. Many-core CPUs are a current trend in CPU design and require jobs to be parallel for exploitation of the performance potential. Very promising for batch job scheduling with virtual machines on both cluster servers and many-core SMP servers is adaptive scheduling which can adjust sizes of parallel jobs to consider different load situations and different resource availability. Then, the resource allocation and resource partitioning can be determined at virtual-machine level and be propagated down to the job sizes. The paper investigates job re-sizing and virtual-machine resizing, and the effects which the efficiency curve of the jobs has on the resulting performance. Additionally, the paper presents a simple, yet effective queuing-model approach for predicting performance under different resource allocation.
Innately Split Model for Job-shop Scheduling Problem
NASA Astrophysics Data System (ADS)
Ikeda, Kokolo; Kobayashi, Sigenobu
Job-shop Scheduling Problem (JSP) is one of the most difficult benchmark problems. GA approaches often fail searching the global optimum because of the deception UV-structure of JSPs. In this paper, we introduce a novel framework model of GA, Innately Split Model (ISM) which prevents UV-phenomenon, and discuss on its power particularly. Next we analyze the structure of JSPs with the help of the UV-structure hypothesys, and finally we show ISM's excellent performance on JSP.
Extended precedence preservative crossover for job shop scheduling problems
NASA Astrophysics Data System (ADS)
Ong, Chung Sin; Moin, Noor Hasnah; Omar, Mohd
2013-04-01
Job shop scheduling problems (JSSP) is one of difficult combinatorial scheduling problems. A wide range of genetic algorithms based on the two parents crossover have been applied to solve the problem but multi parents (more than two parents) crossover in solving the JSSP is still lacking. This paper proposes the extended precedence preservative crossover (EPPX) which uses multi parents for recombination in the genetic algorithms. EPPX is a variation of the precedence preservative crossover (PPX) which is one of the crossovers that perform well to find the solutions for the JSSP. EPPX is based on a vector to determine the gene selected in recombination for the next generation. Legalization of children (offspring) can be eliminated due to the JSSP representation encoded by using permutation with repetition that guarantees the feasibility of chromosomes. The simulations are performed on a set of benchmarks from the literatures and the results are compared to ensure the sustainability of multi parents recombination in solving the JSSP.
Solving Open Job-Shop Scheduling Problems by SAT Encoding
NASA Astrophysics Data System (ADS)
Koshimura, Miyuki; Nabeshima, Hidetomo; Fujita, Hiroshi; Hasegawa, Ryuzo
This paper tries to solve open Job-Shop Scheduling Problems (JSSP) by translating them into Boolean Satisfiability Testing Problems (SAT). The encoding method is essentially the same as the one proposed by Crawford and Baker. The open problems are ABZ8, ABZ9, YN1, YN2, YN3, and YN4. We proved that the best known upper bounds 678 of ABZ9 and 884 of YN1 are indeed optimal. We also improved the upper bound of YN2 and lower bounds of ABZ8, YN2, YN3 and YN4.
A Heuristic Approach for International Crude Oil Transportation Scheduling Problems
NASA Astrophysics Data System (ADS)
Yin, Sisi; Nishi, Tatsushi; Izuno, Tsukasa
In this paper, we propose a heuristic algorithm to solve a practical ship scheduling problem for international crude oil transportation. The problem is considered as a vehicle routing problem with split deliveries. The objective of this paper is to find an optimal assignment of tankers, a sequence of visiting and loading volume simultaneously in order to minimize the total distance satisfying the capacity of tankers. A savings-based meta-heuristic algorithm with lot sizing parameters and volume assignment heuristic is developed. The proposed method is applied to solve a case study with real data. Computational results demonstrate the effectiveness of the heuristic algorithm compared with that of human operators.
Artificial immune algorithm for multi-depot vehicle scheduling problems
NASA Astrophysics Data System (ADS)
Wu, Zhongyi; Wang, Donggen; Xia, Linyuan; Chen, Xiaoling
2008-10-01
In the fast-developing logistics and supply chain management fields, one of the key problems in the decision support system is that how to arrange, for a lot of customers and suppliers, the supplier-to-customer assignment and produce a detailed supply schedule under a set of constraints. Solutions to the multi-depot vehicle scheduling problems (MDVRP) help in solving this problem in case of transportation applications. The objective of the MDVSP is to minimize the total distance covered by all vehicles, which can be considered as delivery costs or time consumption. The MDVSP is one of nondeterministic polynomial-time hard (NP-hard) problem which cannot be solved to optimality within polynomial bounded computational time. Many different approaches have been developed to tackle MDVSP, such as exact algorithm (EA), one-stage approach (OSA), two-phase heuristic method (TPHM), tabu search algorithm (TSA), genetic algorithm (GA) and hierarchical multiplex structure (HIMS). Most of the methods mentioned above are time consuming and have high risk to result in local optimum. In this paper, a new search algorithm is proposed to solve MDVSP based on Artificial Immune Systems (AIS), which are inspirited by vertebrate immune systems. The proposed AIS algorithm is tested with 30 customers and 6 vehicles located in 3 depots. Experimental results show that the artificial immune system algorithm is an effective and efficient method for solving MDVSP problems.
Code of Federal Regulations, 2012 CFR
2012-10-01
... 49 Transportation 4 2012-10-01 2012-10-01 false On-track roadway maintenance machines; inspection... RAILROAD WORKPLACE SAFETY On-Track Roadway Maintenance Machines and Hi-Rail Vehicles § 214.527 On-track roadway maintenance machines; inspection for compliance and schedule for repairs. (a) The operator of...
Code of Federal Regulations, 2014 CFR
2014-10-01
... 49 Transportation 4 2014-10-01 2014-10-01 false On-track roadway maintenance machines; inspection... RAILROAD WORKPLACE SAFETY On-Track Roadway Maintenance Machines and Hi-Rail Vehicles § 214.527 On-track roadway maintenance machines; inspection for compliance and schedule for repairs. (a) The operator of...
Code of Federal Regulations, 2011 CFR
2011-10-01
... 49 Transportation 4 2011-10-01 2011-10-01 false On-track roadway maintenance machines; inspection... RAILROAD WORKPLACE SAFETY On-Track Roadway Maintenance Machines and Hi-Rail Vehicles § 214.527 On-track roadway maintenance machines; inspection for compliance and schedule for repairs. (a) The operator of...
Code of Federal Regulations, 2013 CFR
2013-10-01
... 49 Transportation 4 2013-10-01 2013-10-01 false On-track roadway maintenance machines; inspection... RAILROAD WORKPLACE SAFETY On-Track Roadway Maintenance Machines and Hi-Rail Vehicles § 214.527 On-track roadway maintenance machines; inspection for compliance and schedule for repairs. (a) The operator of...
Code of Federal Regulations, 2010 CFR
2010-10-01
... 49 Transportation 4 2010-10-01 2010-10-01 false On-track roadway maintenance machines; inspection... RAILROAD WORKPLACE SAFETY On-Track Roadway Maintenance Machines and Hi-Rail Vehicles § 214.527 On-track roadway maintenance machines; inspection for compliance and schedule for repairs. (a) The operator of...
Automated problem scheduling and reduction of synchronization delay effects
NASA Technical Reports Server (NTRS)
Saltz, Joel H.
1987-01-01
It is anticipated that in order to make effective use of many future high performance architectures, programs will have to exhibit at least a medium grained parallelism. A framework is presented for partitioning very sparse triangular systems of linear equations that is designed to produce favorable preformance results in a wide variety of parallel architectures. Efficient methods for solving these systems are of interest because: (1) they provide a useful model problem for use in exploring heuristics for the aggregation, mapping and scheduling of relatively fine grained computations whose data dependencies are specified by directed acrylic graphs, and (2) because such efficient methods can find direct application in the development of parallel algorithms for scientific computation. Simple expressions are derived that describe how to schedule computational work with varying degrees of granularity. The Encore Multimax was used as a hardware simulator to investigate the performance effects of using the partitioning techniques presented in shared memory architectures with varying relative synchronization costs.
Problems of vibroacoustical diagnostics of textile machines
NASA Technical Reports Server (NTRS)
Ivanov, L. N.; Pobol, O. N.; Gevorkyan, G. T.
1973-01-01
The application of a vibroacoustical method for analyzing the vibration characteristics of textile machines is discussed. A drawing of a typical mechanism is provided to show the sources of vibration. The conditions under which the machine operates are defined. An accelerometer is used as a sensor. The point of installation is selected so that a dip in the frequency characteristic of the vibrating part, on which the sensor is installed, in the region of the maximum acoustical signal. This allows for a drop in the vibrations for those values of the gap in the mechanism which amount to 10 to 20 db.
Efficiently Scheduling Multi-core Guest Virtual Machines on Multi-core Hosts in Network Simulation
Yoginath, Srikanth B; Perumalla, Kalyan S
2011-01-01
Virtual machine (VM)-based simulation is a method used by network simulators to incorporate realistic application behaviors by executing actual VMs as high-fidelity surrogates for simulated end-hosts. A critical requirement in such a method is the simulation time-ordered scheduling and execution of the VMs. Prior approaches such as time dilation are less efficient due to the high degree of multiplexing possible when multiple multi-core VMs are simulated on multi-core host systems. We present a new simulation time-ordered scheduler to efficiently schedule multi-core VMs on multi-core real hosts, with a virtual clock realized on each virtual core. The distinguishing features of our approach are: (1) customizable granularity of the VM scheduling time unit on the simulation time axis, (2) ability to take arbitrary leaps in virtual time by VMs to maximize the utilization of host (real) cores when guest virtual cores idle, and (3) empirically determinable optimality in the tradeoff between total execution (real) time and time-ordering accuracy levels. Experiments show that it is possible to get nearly perfect time-ordered execution, with a slight cost in total run time, relative to optimized non-simulation VM schedulers. Interestingly, with our time-ordered scheduler, it is also possible to reduce the time-ordering error from over 50% of non-simulation scheduler to less than 1% realized by our scheduler, with almost the same run time efficiency as that of the highly efficient non-simulation VM schedulers.
An Improved Differential Evolution Solution for Software Project Scheduling Problem
Biju, A. C.; Victoire, T. Aruldoss Albert; Mohanasundaram, Kumaresan
2015-01-01
This paper proposes a differential evolution (DE) method for the software project scheduling problem (SPSP). The interest on finding a more efficient solution technique for SPSP is always a topic of interest due to the fact of ever growing challenges faced by the software industry. The curse of dimensionality is introduced in the scheduling problem by ever increasing software assignments and the number of staff who handles it. Thus the SPSP is a class of NP-hard problem, which requires a rigorous solution procedure which guarantees a reasonably better solution. Differential evolution is a direct search stochastic optimization technique that is fairly fast and reasonably robust. It is also capable of handling nondifferentiable, nonlinear, and multimodal objective functions like SPSP. This paper proposes a refined DE where a new mutation mechanism is introduced. The superiority of the proposed method is experimented and demonstrated by solving the SPSP on 50 random instances and the results are compared with some of the techniques in the literature. PMID:26495419
Petri Net Modeling and Decomposition Method for Solving Production Scheduling Problems
NASA Astrophysics Data System (ADS)
Nishi, Tatsushi; Maeno, Ryota
Considering the need to develop general scheduling problem solver, the recent integration of Petri Nets as modeling tools into effective optimization methods for scheduling problems is very promising. The paper addresses a Petri Net modeling and decomposition method for solving a wide variety of scheduling problems. The scheduling problems are represented as the optimal transition firing sequence problems for timed Petri Nets. The Petri Net is decomposed into several subnets in which each subproblem can be easily solved by Dijkstra' algorithm. The approach is applied to a flowshop scheduling problem. The performance of the proposed algorithm is compared with that of a simulated annealing method.
Problem of technological inheritance in machine engineering
NASA Astrophysics Data System (ADS)
Blumenstein, Valery; Rakhimyanov, Kharis; Heifetz, Mikhail; Kleptzov, Alexander
2016-01-01
This article demonstrates the importance of the research study with regard to the technological inheritance of the properties, which characterize the surface layer, at different stages of a part's life cycle. It looks back at the major achievements and gives the findings relating to the technological inheritance of the parameters of the surface layer strength and quality as well as to how they affect the performance properties of machine parts. It demonstrates that high rates of machine engineering development, occurrence of new materials and more complicated machine operation environment require a shorter period for design-to-manufacture facility by reducing experiments and increasing design work. That, in its turn, generates the necessity in more complex but also more accurate models of metal behavior under stressing. It is especially critical for strengthening treatment. Among them are the models developed within the mechanics of technological inheritance. It is assumed that at the stages of a part's life cycle deformation accumulates on a continuous basis and the plasticity reserve of the metal, which the surface layer is made of, depletes. The research study of technological inheritance and the discovery of physical patterns of the evolution and degradation of the structures in a thin surface layer, which occur during machining and operational stressing of parts made from existing and unique including nanopatterned metals, is a crucial scientific challenge. This leads to the acquisition of new knowledge in the plasticity of state-of-the-art metals in the conditions of complex non monotonous stressing and to the development of efficient integrated and combined methods of technological impact.
Applications of dynamic scheduling technique to space related problems: Some case studies
NASA Technical Reports Server (NTRS)
Nakasuka, Shinichi; Ninomiya, Tetsujiro
1994-01-01
The paper discusses the applications of 'Dynamic Scheduling' technique, which has been invented for the scheduling of Flexible Manufacturing System, to two space related scheduling problems: operation scheduling of a future space transportation system, and resource allocation in a space system with limited resources such as space station or space shuttle.
Applications of dynamic scheduling technique to space related problems: Some case studies
NASA Astrophysics Data System (ADS)
Nakasuka, Shinichi; Ninomiya, Tetsujiro
1994-10-01
The paper discusses the applications of 'Dynamic Scheduling' technique, which has been invented for the scheduling of Flexible Manufacturing System, to two space related scheduling problems: operation scheduling of a future space transportation system, and resource allocation in a space system with limited resources such as space station or space shuttle.
Optimized Hypervisor Scheduler for Parallel Discrete Event Simulations on Virtual Machine Platforms
Yoginath, Srikanth B; Perumalla, Kalyan S
2013-01-01
With the advent of virtual machine (VM)-based platforms for parallel computing, it is now possible to execute parallel discrete event simulations (PDES) over multiple virtual machines, in contrast to executing in native mode directly over hardware as is traditionally done over the past decades. While mature VM-based parallel systems now offer new, compelling benefits such as serviceability, dynamic reconfigurability and overall cost effectiveness, the runtime performance of parallel applications can be significantly affected. In particular, most VM-based platforms are optimized for general workloads, but PDES execution exhibits unique dynamics significantly different from other workloads. Here we first present results from experiments that highlight the gross deterioration of the runtime performance of VM-based PDES simulations when executed using traditional VM schedulers, quantitatively showing the bad scaling properties of the scheduler as the number of VMs is increased. The mismatch is fundamental in nature in the sense that any fairness-based VM scheduler implementation would exhibit this mismatch with PDES runs. We also present a new scheduler optimized specifically for PDES applications, and describe its design and implementation. Experimental results obtained from running PDES benchmarks (PHOLD and vehicular traffic simulations) over VMs show over an order of magnitude improvement in the run time of the PDES-optimized scheduler relative to the regular VM scheduler, with over 20 reduction in run time of simulations using up to 64 VMs. The observations and results are timely in the context of emerging systems such as cloud platforms and VM-based high performance computing installations, highlighting to the community the need for PDES-specific support, and the feasibility of significantly reducing the runtime overhead for scalable PDES on VM platforms.
Assessment of New Load Schedules for the Machine Calibration of a Force Balance
NASA Technical Reports Server (NTRS)
Ulbrich, N.; Gisler, R.; Kew, R.
2015-01-01
New load schedules for the machine calibration of a six-component force balance are currently being developed and evaluated at the NASA Ames Balance Calibration Laboratory. One of the proposed load schedules is discussed in the paper. It has a total of 2082 points that are distributed across 16 load series. Several criteria were applied to define the load schedule. It was decided, for example, to specify the calibration load set in force balance format as this approach greatly simplifies the definition of the lower and upper bounds of the load schedule. In addition, all loads are assumed to be applied in a calibration machine by using the one-factor-at-a-time approach. At first, all single-component loads are applied in six load series. Then, three two-component load series are applied. They consist of the load pairs (N1, N2), (S1, S2), and (RM, AF). Afterwards, four three-component load series are applied. They consist of the combinations (N1, N2, AF), (S1, S2, AF), (N1, N2, RM), and (S1, S2, RM). In the next step, one four-component load series is applied. It is the load combination (N1, N2, S1, S2). Finally, two five-component load series are applied. They are the load combination (N1, N2, S1, S2, AF) and (N1, N2, S1, S2, RM). The maximum difference between loads of two subsequent data points of the load schedule is limited to 33 % of capacity. This constraint helps avoid unwanted load "jumps" in the load schedule that can have a negative impact on the performance of a calibration machine. Only loadings of the single- and two-component load series are loaded to 100 % of capacity. This approach was selected because it keeps the total number of calibration points to a reasonable limit while still allowing for the application of some of the more complex load combinations. Data from two of NASA's force balances is used to illustrate important characteristics of the proposed 2082-point calibration load schedule.
A Solution Method of Job-shop Scheduling Problems by the Idle Time Shortening Type Genetic Algorithm
NASA Astrophysics Data System (ADS)
Ida, Kenichi; Osawa, Akira
In this paper, we propose a new idle time shortening method for Job-shop scheduling problems (JSPs). We insert its method into a genetic algorithm (GA). The purpose of JSP is to find a schedule with the minimum makespan. We suppose that it is effective to reduce idle time of a machine in order to improve the makespan. The left shift is a famous algorithm in existing algorithms for shortening idle time. The left shift can not arrange the work to idle time. For that reason, some idle times are not shortened by the left shift. We propose two kinds of algorithms which shorten such idle time. Next, we combine these algorithms and the reversal of a schedule. We apply GA with its algorithm to benchmark problems and we show its effectiveness.
NASA Astrophysics Data System (ADS)
Ausaf, Muhammad Farhan; Gao, Liang; Li, Xinyu
2015-12-01
For increasing the overall performance of modern manufacturing systems, effective integration of process planning and scheduling functions has been an important area of consideration among researchers. Owing to the complexity of handling process planning and scheduling simultaneously, most of the research work has been limited to solving the integrated process planning and scheduling (IPPS) problem for a single objective function. As there are many conflicting objectives when dealing with process planning and scheduling, real world problems cannot be fully captured considering only a single objective for optimization. Therefore considering multi-objective IPPS (MOIPPS) problem is inevitable. Unfortunately, only a handful of research papers are available on solving MOIPPS problem. In this paper, an optimization algorithm for solving MOIPPS problem is presented. The proposed algorithm uses a set of dispatching rules coupled with priority assignment to optimize the IPPS problem for various objectives like makespan, total machine load, total tardiness, etc. A fixed sized external archive coupled with a crowding distance mechanism is used to store and maintain the non-dominated solutions. To compare the results with other algorithms, a C-matric based method has been used. Instances from four recent papers have been solved to demonstrate the effectiveness of the proposed algorithm. The experimental results show that the proposed method is an efficient approach for solving the MOIPPS problem.
Nurse Scheduling System based on Dynamic Weighted Maximal Constraint Satisfaction Problem
NASA Astrophysics Data System (ADS)
Hattori, Hiromitsu; Isomura, Atsushi; Ito, Takayuki; Ozono, Tadachika; Shintani, Toramatsu
Scheduling has been an important research field in Artificial Intelligence. Because typical scheduling problems could be modeled as a Constraint Satisfaction Problem(CSP), several constraint satisfaction techniques have been proposed. In order to handle the different levels of importance of the constraints, solving a problem as a Weighted Maximal Constraint Satisfaction Problem(W-MaxCSP) is an promising approach. However, there exists the case where unexpected events are added and some sudden changes are required, i.e., the case with dynamic changes in scheduling problems. In this paper, we describe such dynamic scheduling problem as a Dynamic Weighted Maximal Constraint Satisfaction Problem(DW-MaxCSP) in which constraints would changes dynamically. Generally, it is undesirable to determine vastly modified schedule even if re-scheduling is needed. A new schedule should be close to the current one as much as possible. In order to obtain stable solutions, we propose the methodology to maintain portions of the current schedule using the provisional soft constraints, which explicitly penalize the changes from the current schedule. We have experimentally confirmed the efficacy of re-scheduling based on our method with provisional constraints. In this paper, we construct the nurse scheduling system for applying the proposed scheduling method.
Application of TRIZ approach to machine vibration condition monitoring problems
NASA Astrophysics Data System (ADS)
Cempel, Czesław
2013-12-01
Up to now machine condition monitoring has not been seriously approached by TRIZ1TRIZ= Russian acronym for Inventive Problem Solving System, created by G. Altshuller ca 50 years ago. users, and the knowledge of TRIZ methodology has not been applied there intensively. However, there are some introductory papers of present author posted on Diagnostic Congress in Cracow (Cempel, in press [11]), and Diagnostyka Journal as well. But it seems to be further need to make such approach from different sides in order to see, if some new knowledge and technology will emerge. In doing this we need at first to define the ideal final result (IFR) of our innovation problem. As a next we need a set of parameters to describe the problems of system condition monitoring (CM) in terms of TRIZ language and set of inventive principles possible to apply, on the way to IFR. This means we should present the machine CM problem by means of contradiction and contradiction matrix. When specifying the problem parameters and inventive principles, one should use analogy and metaphorical thinking, which by definition is not exact but fuzzy, and leads sometimes to unexpected results and outcomes. The paper undertakes this important problem again and brings some new insight into system and machine CM problems. This may mean for example the minimal dimensionality of TRIZ engineering parameter set for the description of machine CM problems, and the set of most useful inventive principles applied to given engineering parameter and contradictions of TRIZ.
Genetic-Annealing Algorithm in Grid Environment for Scheduling Problems
NASA Astrophysics Data System (ADS)
Cruz-Chávez, Marco Antonio; Rodríguez-León, Abelardo; Ávila-Melgar, Erika Yesenia; Juárez-Pérez, Fredy; Cruz-Rosales, Martín H.; Rivera-López, Rafael
This paper presents a parallel hybrid evolutionary algorithm executed in a grid environment. The algorithm executes local searches using simulated annealing within a Genetic Algorithm to solve the job shop scheduling problem. Experimental results of the algorithm obtained in the "Tarantula MiniGrid" are shown. Tarantula was implemented by linking two clusters from different geographic locations in Mexico (Morelos-Veracruz). The technique used to link the two clusters and configure the Tarantula MiniGrid is described. The effects of latency in communication between the two clusters are discussed. It is shown that the evolutionary algorithm presented is more efficient working in Grid environments because it can carry out major exploration and exploitation of the solution space.
NASA Technical Reports Server (NTRS)
Smith, Stephen F.; Pathak, Dhiraj K.
1991-01-01
In this paper, we report work aimed at applying concepts of constraint-based problem structuring and multi-perspective scheduling to an over-subscribed scheduling problem. Previous research has demonstrated the utility of these concepts as a means for effectively balancing conflicting objectives in constraint-relaxable scheduling problems, and our goal here is to provide evidence of their similar potential in the context of HST observation scheduling. To this end, we define and experimentally assess the performance of two time-bounded heuristic scheduling strategies in balancing the tradeoff between resource setup time minimization and satisfaction of absolute time constraints. The first strategy considered is motivated by dispatch-based manufacturing scheduling research, and employs a problem decomposition that concentrates local search on minimizing resource idle time due to setup activities. The second is motivated by research in opportunistic scheduling and advocates a problem decomposition that focuses attention on the goal activities that have the tightest temporal constraints. Analysis of experimental results gives evidence of differential superiority on the part of each strategy in different problem solving circumstances. A composite strategy based on recognition of characteristics of the current problem solving state is then defined and tested to illustrate the potential benefits of constraint-based problem structuring and multi-perspective scheduling in over-subscribe scheduling problems.
NASA Astrophysics Data System (ADS)
Tang, Dunbing; Dai, Min
2015-09-01
The traditional production planning and scheduling problems consider performance indicators like time, cost and quality as optimization objectives in manufacturing processes. However, environmentally-friendly factors like energy consumption of production have not been completely taken into consideration. Against this background, this paper addresses an approach to modify a given schedule generated by a production planning and scheduling system in a job shop floor, where machine tools can work at different cutting speeds. It can adjust the cutting speeds of the operations while keeping the original assignment and processing sequence of operations of each job fixed in order to obtain energy savings. First, the proposed approach, based on a mixed integer programming mathematical model, changes the total idle time of the given schedule to minimize energy consumption in the job shop floor while accepting the optimal solution of the scheduling objective, makespan. Then, a genetic-simulated annealing algorithm is used to explore the optimal solution due to the fact that the problem is strongly NP-hard. Finally, the effectiveness of the approach is performed smalland large-size instances, respectively. The experimental results show that the approach can save 5%-10% of the average energy consumption while accepting the optimal solution of the makespan in small-size instances. In addition, the average maximum energy saving ratio can reach to 13%. And it can save approximately 1%-4% of the average energy consumption and approximately 2.4% of the average maximum energy while accepting the near-optimal solution of the makespan in large-size instances. The proposed research provides an interesting point to explore an energy-aware schedule optimization for a traditional production planning and scheduling problem.
Problems in modeling man machine control behavior in biodynamic environments
NASA Technical Reports Server (NTRS)
Jex, H. R.
1972-01-01
Reviewed are some current problems in modeling man-machine control behavior in a biodynamic environment. It is given in two parts: (1) a review of the models which are appropriate for manual control behavior and the added elements necessary to deal with biodynamic interfaces; and (2) a review of some biodynamic interface pilot/vehicle problems which have occurred, been solved, or need to be solved.
Exploiting the ALICE HLT for PROOF by scheduling of Virtual Machines
NASA Astrophysics Data System (ADS)
Meoni, Marco; Boettger, Stefan; Zelnicek, Pierre; Lindenstruth, Volker; Kebschull, Udo
2011-12-01
The HLT (High-Level Trigger) group of the ALICE experiment at the LHC has prepared a virtual Parallel ROOT Facility (PROOF) enabled cluster (HAF - HLT Analysis Facility) for fast physics analysis, detector calibration and reconstruction of data samples. The HLT-Cluster currently consists of 2860 CPU cores and 175TB of storage. Its purpose is the online filtering of the relevant part of data produced by the particle detector. However, data taking is not running continuously and exploiting unused cluster resources for other applications is highly desirable and improves the usage-cost ratio of the HLT cluster. As such, unused computing resources are dedicated to a PROOF-enabled virtual cluster available to the entire collaboration. This setup is especially aimed at the prototyping phase of analyses that need a high number of development iterations and a short response time, e.g. tuning of analysis cuts, calibration and alignment. HAF machines are enabled and disabled upon user request to start or complete analysis tasks. This is achieved by a virtual machine scheduling framework which dynamically assigns and migrates virtual machines running PROOF workers to unused physical resources. Using this approach we extend the HLT usage scheme to running both online and offline computing, thereby optimizing the resource usage.
Full Glowworm Swarm Optimization Algorithm for Whole-Set Orders Scheduling in Single Machine
Yu, Zhang; Yang, Xiaomei
2013-01-01
By analyzing the characteristics of whole-set orders problem and combining the theory of glowworm swarm optimization, a new glowworm swarm optimization algorithm for scheduling is proposed. A new hybrid-encoding schema combining with two-dimensional encoding and random-key encoding is given. In order to enhance the capability of optimal searching and speed up the convergence rate, the dynamical changed step strategy is integrated into this algorithm. Furthermore, experimental results prove its feasibility and efficiency. PMID:24294135
Discrete Bat Algorithm for Optimal Problem of Permutation Flow Shop Scheduling
Luo, Qifang; Zhou, Yongquan; Xie, Jian; Ma, Mingzhi; Li, Liangliang
2014-01-01
A discrete bat algorithm (DBA) is proposed for optimal permutation flow shop scheduling problem (PFSP). Firstly, the discrete bat algorithm is constructed based on the idea of basic bat algorithm, which divide whole scheduling problem into many subscheduling problems and then NEH heuristic be introduced to solve subscheduling problem. Secondly, some subsequences are operated with certain probability in the pulse emission and loudness phases. An intensive virtual population neighborhood search is integrated into the discrete bat algorithm to further improve the performance. Finally, the experimental results show the suitability and efficiency of the present discrete bat algorithm for optimal permutation flow shop scheduling problem. PMID:25243220
NASA Astrophysics Data System (ADS)
Li, Wenjie; Li, Shisheng
2015-03-01
We study the online batch scheduling of equal-length jobs on two identical batch machines. Each batch machine can process up to b jobs simultaneously as a batch (where b is called the capacity of the machines). The goal is to determine a schedule that maximises the (weighted) number of early jobs. For the non-preemptive model, we first present an upper bound that depends on the machine capacity b, and then we provide a greedy online algorithm with a competitive ratio of 1/(b + 1). For the preemption-restart model with b = ∞, we first show that no online algorithm has a competitive ratio greater than 0.595, and then we design an online algorithm with a competitive ratio of ?.
An Optimization Model for Scheduling Problems with Two-Dimensional Spatial Resource Constraint
NASA Technical Reports Server (NTRS)
Garcia, Christopher; Rabadi, Ghaith
2010-01-01
Traditional scheduling problems involve determining temporal assignments for a set of jobs in order to optimize some objective. Some scheduling problems also require the use of limited resources, which adds another dimension of complexity. In this paper we introduce a spatial resource-constrained scheduling problem that can arise in assembly, warehousing, cross-docking, inventory management, and other areas of logistics and supply chain management. This scheduling problem involves a twodimensional rectangular area as a limited resource. Each job, in addition to having temporal requirements, has a width and a height and utilizes a certain amount of space inside the area. We propose an optimization model for scheduling the jobs while respecting all temporal and spatial constraints.
Code of Federal Regulations, 2010 CFR
2010-07-01
... 41 Public Contracts and Property Management 2 2010-07-01 2010-07-01 true Requisitioning tabulating machine cards available from Federal Supply Schedule contracts. 101-26.509-1 Section 101-26.509-1 Public Contracts and Property Management Federal Property Management Regulations System FEDERAL PROPERTY MANAGEMENT REGULATIONS SUPPLY AND...
Code of Federal Regulations, 2010 CFR
2010-07-01
... 41 Public Contracts and Property Management 2 2010-07-01 2010-07-01 true Requisitioning tabulating machine cards not available from Federal Supply Schedule contracts. 101-26.509-2 Section 101-26.509-2 Public Contracts and Property Management Federal Property Management Regulations System FEDERAL PROPERTY MANAGEMENT REGULATIONS SUPPLY...
NASA Astrophysics Data System (ADS)
Bai, Danyu
2015-08-01
This paper discusses the flow shop scheduling problem to minimise the total quadratic completion time (TQCT) with release dates in offline and online environments. For this NP-hard problem, the investigation is focused on the performance of two online algorithms based on the Shortest Processing Time among Available jobs rule. Theoretical results indicate the asymptotic optimality of the algorithms as the problem scale is sufficiently large. To further enhance the quality of the original solutions, the improvement scheme is provided for these algorithms. A new lower bound with performance guarantee is provided, and computational experiments show the effectiveness of these heuristics. Moreover, several results of the single-machine TQCT problem with release dates are also obtained for the deduction of the main theorem.
Optimizing scheduling problem using an estimation of distribution algorithm and genetic algorithm
NASA Astrophysics Data System (ADS)
Qun, Jiang; Yang, Ou; Dong, Shi-Du
2007-12-01
This paper presents a methodology for using heuristic search methods to optimize scheduling problem. Specifically, an Estimation of Distribution Algorithm (EDA)- Population Based Incremental Learning (PBIL), and Genetic Algorithm (GA) have been applied to finding effective arrangement of curriculum schedule of Universities. To our knowledge, EDAs have been applied to fewer real world problems compared to GAs, and the goal of the present paper is to expand the application domain of this technique. The experimental results indicate a good applicability of PBIL to optimize scheduling problem.
The problem of scheduling for the linear section of a single-track railway
NASA Astrophysics Data System (ADS)
Akimova, Elena N.; Gainanov, Damir N.; Golubev, Oleg A.; Kolmogortsev, Ilya D.; Konygin, Anton V.
2016-06-01
The paper is devoted to the problem of scheduling for the linear section of a single-track railway: how to organize the flow in both directions in the most efficient way. In this paper, the authors propose an algorithm for scheduling, examine the properties of this algorithm and perform the computational experiments.
Electric power scheduling - A distributed problem-solving approach
NASA Technical Reports Server (NTRS)
Mellor, Pamela A.; Dolce, James L.; Krupp, Joseph C.
1990-01-01
Space Station Freedom's power system, along with the spacecraft's other subsystems, needs to carefully conserve its resources and yet strive to maximize overall Station productivity. Due to Freedom's distributed design, each subsystem must work cooperatively within the Station community. There is a need for a scheduling tool which will preserve this distributed structure, allow each subsystem the latitude to satisfy its own constraints, and preserve individual value systems while maintaining Station-wide integrity.
Electric power scheduling: A distributed problem-solving approach
NASA Technical Reports Server (NTRS)
Mellor, Pamela A.; Dolce, James L.; Krupp, Joseph C.
1990-01-01
Space Station Freedom's power system, along with the spacecraft's other subsystems, needs to carefully conserve its resources and yet strive to maximize overall Station productivity. Due to Freedom's distributed design, each subsystem must work cooperatively within the Station community. There is a need for a scheduling tool which will preserve this distributed structure, allow each subsystem the latitude to satisfy its own constraints, and preserve individual value systems while maintaining Station-wide integrity. The value-driven free-market economic model is such a tool.
Solving a real-world problem using an evolving heuristically driven schedule builder.
Hart, E; Ross, P; Nelson, J
1998-01-01
This work addresses the real-life scheduling problem of a Scottish company that must produce daily schedules for the catching and transportation of large numbers of live chickens. The problem is complex and highly constrained. We show that it can be successfully solved by division into two subproblems and solving each using a separate genetic algorithm (GA). We address the problem of whether this produces locally optimal solutions and how to overcome this. We extend the traditional approach of evolving a "permutation + schedule builder" by concentrating on evolving the schedule builder itself. This results in a unique schedule builder being built for each daily scheduling problem, each individually tailored to deal with the particular features of that problem. This results in a robust, fast, and flexible system that can cope with most of the circumstances imaginable at the factory. We also compare the performance of a GA approach to several other evolutionary methods and show that population-based methods are superior to both hill-climbing and simulated annealing in the quality of solutions produced. Population-based methods also have the distinct advantage of producing multiple, equally fit solutions, which is of particular importance when considering the practical aspects of the problem. PMID:10021741
Solving scheduling tournament problems using a new version of CLONALG
NASA Astrophysics Data System (ADS)
Pérez-Cáceres, Leslie; Riff, María Cristina
2015-01-01
The travelling tournament problem (TTP) is an important and well-known problem within the collective sports research community. The problem is NP-hard which makes difficult finding quality solution in short amount of time. Recently a new kind of TTP has been proposed 'The Relaxed Travelling Tournament Problem'. This version of the problem allows teams to have some days off during the tournament. In this paper, we propose an immune algorithm that is able to solve both problem versions. The algorithm uses moves which are based on the team home/away patterns. One of these moves has been specially designed for the relaxed travel tournament instances. We have tested the algorithm using well-known problem benchmarks and the results obtained are very encouraging.
Mapping unstructured grid problems to the connection machine
NASA Technical Reports Server (NTRS)
Hammond, Steven W.; Schreiber, Robert
1990-01-01
We present a highly parallel graph mapping technique that enables one to solve unstructured grid problems on massively parallel computers. Many implicit and explicit methods for solving discretizated partial differential equations require each point in the discretization to exchange data with its neighboring points every time step or iteration. The time spent communicating can limit the high performance promised by massively parallel computing. To eliminate this bottleneck, we map the graph of the irregular problem to the graph representing the interconnection topology of the computer such that the sum of the distances that the messages travel is minimized. We show that, in comparison to a naive assignment of processors, our heuristic mapping algorithm significantly reduces the communication time on the Connection Machine, CM-2.
Three-index Model for Westenberger-Kallrath Benchmark Scheduling Problem
NASA Astrophysics Data System (ADS)
Vooradi, Ramsagar; Shaik, Munawar A.; Gupta, Nikhil M.
2010-10-01
Short-term scheduling of batch operations has become an important research area in the last two decades. Recently Shaik and Floudas (2009) proposed a novel unified model for short-term scheduling using unit-specific event based continuous time representation employing three-index binary and continuous variables. In this work, we extend this three index model to solve a challenging benchmark problem from the scheduling literature that covers most of the features contributing to the complexity of batch process scheduling in industry. In order to implement the problem, new sets of constraints and modifications are incorporated into the three-index model. The different demand instances of the benchmark problem have been solved using the developed model and the results are compared with the literature to demonstrate the effectiveness of the proposed three-index model.
On scheduling models for the frequency interval assignment problem with cumulative interferences
NASA Astrophysics Data System (ADS)
Kiatmanaroj, Kata; Artigues, Christian; Houssin, Laurent
2016-05-01
In this article, models and methods for solving a real-life frequency assignment problem based on scheduling theory are investigated. A realistic frequency assignment problem involving cumulative interference constraints in which the aim is to maximize the number of assigned users is considered. If interferences are assumed to be binary, a multiple carrier frequency assignment problem can be treated as a disjunctive scheduling problem since a user requesting a number of contiguous frequencies can be considered as a non-preemptive task with a processing time, and two interfering users can be modelled through a disjunctive constraint on the corresponding tasks. A binary interference version of the problem is constructed and a disjunctive scheduling model is derived. Based on the binary representation, two models are proposed. The first one relies on an interference matrix and the second one considers maximal cliques. A third, cumulative, model that yields a new class of scheduling problems is also proposed. Computational experiments show that the case-study frequency assignment problem can be solved efficiently with disjunctive scheduling techniques.
A modify ant colony optimization for the grid jobs scheduling problem with QoS requirements
NASA Astrophysics Data System (ADS)
Pu, Xun; Lu, XianLiang
2011-10-01
Job scheduling with customers' quality of service (QoS) requirement is challenging in grid environment. In this paper, we present a modify Ant colony optimization (MACO) for the Job scheduling problem in grid. Instead of using the conventional construction approach to construct feasible schedules, the proposed algorithm employs a decomposition method to satisfy the customer's deadline and cost requirements. Besides, a new mechanism of service instances state updating is embedded to improve the convergence of MACO. Experiments demonstrate the effectiveness of the proposed algorithm.
Neighbourhood generation mechanism applied in simulated annealing to job shop scheduling problems
NASA Astrophysics Data System (ADS)
Cruz-Chávez, Marco Antonio
2015-11-01
This paper presents a neighbourhood generation mechanism for the job shop scheduling problems (JSSPs). In order to obtain a feasible neighbour with the generation mechanism, it is only necessary to generate a permutation of an adjacent pair of operations in a scheduling of the JSSP. If there is no slack time between the adjacent pair of operations that is permuted, then it is proven, through theory and experimentation, that the new neighbour (schedule) generated is feasible. It is demonstrated that the neighbourhood generation mechanism is very efficient and effective in a simulated annealing.
ERIC Educational Resources Information Center
Tsakanikos, Elias; Underwood, Lisa; Sturmey, Peter; Bouras, Nick; McCarthy, Jane
2011-01-01
The present study employed the Disability Assessment Schedule (DAS) to assess problem behaviors in a large sample of adults with ID (N = 568) and evaluate the psychometric properties of this instrument. Although the DAS problem behaviors were found to be internally consistent (Cronbach's [alpha] = 0.87), item analysis revealed one weak item…
NASA Technical Reports Server (NTRS)
Wang, Lui; Valenzuela-Rendon, Manuel
1993-01-01
The Space Station Freedom will require the supply of items in a regular fashion. A schedule for the delivery of these items is not easy to design due to the large span of time involved and the possibility of cancellations and changes in shuttle flights. This paper presents the basic concepts of a genetic algorithm model, and also presents the results of an effort to apply genetic algorithms to the design of propellant resupply schedules. As part of this effort, a simple simulator and an encoding by which a genetic algorithm can find near optimal schedules have been developed. Additionally, this paper proposes ways in which robust schedules, i.e., schedules that can tolerate small changes, can be found using genetic algorithms.
Scheduling Earth Observing Fleets Using Evolutionary Algorithms: Problem Description and Approach
NASA Technical Reports Server (NTRS)
Globus, Al; Crawford, James; Lohn, Jason; Morris, Robert; Clancy, Daniel (Technical Monitor)
2002-01-01
We describe work in progress concerning multi-instrument, multi-satellite scheduling. Most, although not all, Earth observing instruments currently in orbit are unique. In the relatively near future, however, we expect to see fleets of Earth observing spacecraft, many carrying nearly identical instruments. This presents a substantially new scheduling challenge. Inspired by successful commercial applications of evolutionary algorithms in scheduling domains, this paper presents work in progress regarding the use of evolutionary algorithms to solve a set of Earth observing related model problems. Both the model problems and the software are described. Since the larger problems will require substantial computation and evolutionary algorithms are embarrassingly parallel, we discuss our parallelization techniques using dedicated and cycle-scavenged workstations.
Problem-Solving at a Circuit-Board Assembly Machine: A Microanalysis.
ERIC Educational Resources Information Center
Kleifgen, Jo Anne; Frenz-Belken, Patricia
A study described machine operators' problem-solving actions at a computerized circuit-board assembly machine in a small manufacturing plant located on the West Coast. Participants were a machine operator and his supervisor, both from Vietnam, who were building large prototype boards for a major computer corporation. Over a 6.5 minute interval,…
A modified genetic algorithm with fuzzy roulette wheel selection for job-shop scheduling problems
NASA Astrophysics Data System (ADS)
Thammano, Arit; Teekeng, Wannaporn
2015-05-01
The job-shop scheduling problem is one of the most difficult production planning problems. Since it is in the NP-hard class, a recent trend in solving the job-shop scheduling problem is shifting towards the use of heuristic and metaheuristic algorithms. This paper proposes a novel metaheuristic algorithm, which is a modification of the genetic algorithm. This proposed algorithm introduces two new concepts to the standard genetic algorithm: (1) fuzzy roulette wheel selection and (2) the mutation operation with tabu list. The proposed algorithm has been evaluated and compared with several state-of-the-art algorithms in the literature. The experimental results on 53 JSSPs show that the proposed algorithm is very effective in solving the combinatorial optimization problems. It outperforms all state-of-the-art algorithms on all benchmark problems in terms of the ability to achieve the optimal solution and the computational time.
Solving multi-objective job shop scheduling problems using a non-dominated sorting genetic algorithm
NASA Astrophysics Data System (ADS)
Piroozfard, Hamed; Wong, Kuan Yew
2015-05-01
The efforts of finding optimal schedules for the job shop scheduling problems are highly important for many real-world industrial applications. In this paper, a multi-objective based job shop scheduling problem by simultaneously minimizing makespan and tardiness is taken into account. The problem is considered to be more complex due to the multiple business criteria that must be satisfied. To solve the problem more efficiently and to obtain a set of non-dominated solutions, a meta-heuristic based non-dominated sorting genetic algorithm is presented. In addition, task based representation is used for solution encoding, and tournament selection that is based on rank and crowding distance is applied for offspring selection. Swapping and insertion mutations are employed to increase diversity of population and to perform intensive search. To evaluate the modified non-dominated sorting genetic algorithm, a set of modified benchmarking job shop problems obtained from the OR-Library is used, and the results are considered based on the number of non-dominated solutions and quality of schedules obtained by the algorithm.
NASA Astrophysics Data System (ADS)
Marwati, Rini; Yulianti, Kartika; Pangestu, Herny Wulandari
2016-02-01
A fuzzy evolutionary algorithm is an integration of an evolutionary algorithm and a fuzzy system. In this paper, we present an application of a genetic algorithm to a fuzzy evolutionary algorithm to detect and to solve chromosomes conflict. A chromosome conflict is identified by existence of any two genes in a chromosome that has the same values as two genes in another chromosome. Based on this approach, we construct an algorithm to solve a lecture scheduling problem. Time codes, lecture codes, lecturer codes, and room codes are defined as genes. They are collected to become chromosomes. As a result, the conflicted schedule turns into chromosomes conflict. Built in the Delphi program, results show that the conflicted lecture schedule problem is solvable by this algorithm.
Active Solution Space and Search on Job-shop Scheduling Problem
NASA Astrophysics Data System (ADS)
Watanabe, Masato; Ida, Kenichi; Gen, Mitsuo
In this paper we propose a new searching method of Genetic Algorithm for Job-shop scheduling problem (JSP). The coding method that represent job number in order to decide a priority to arrange a job to Gannt Chart (called the ordinal representation with a priority) in JSP, an active schedule is created by using left shift. We define an active solution at first. It is solution which can create an active schedule without using left shift, and set of its defined an active solution space. Next, we propose an algorithm named Genetic Algorithm with active solution space search (GA-asol) which can create an active solution while solution is evaluated, in order to search the active solution space effectively. We applied it for some benchmark problems to compare with other method. The experimental results show good performance.
ERIC Educational Resources Information Center
Borrero, Carrie S. W.; Vollmer, Timothy R.; Borrero, John C.; Bourret, Jason C.; Sloman, Kimberly N.; Samaha, Andrew L.; Dallery, Jesse
2010-01-01
This study evaluated how children who exhibited functionally equivalent problem and appropriate behavior allocate responding to experimentally arranged reinforcer rates. Relative reinforcer rates were arranged on concurrent variable-interval schedules and effects on relative response rates were interpreted using the generalized matching equation.…
An information theoretic view of the scheduling problem in whole-body CAD
NASA Astrophysics Data System (ADS)
Zhan, Yiqiang; Zhou, Xiang Sean; Krishnan, Arun
2008-03-01
Emerging whole-body imaging technologies push computer aided detection/diagnosis (CAD) to scale up to a whole-body level, which involves multiple organs or anatomical structure. To be exploited in this paper is the fact that the various tasks in whole-body CAD are often highly dependent (e.g., the localization of the femur heads strongly predicts the position of the iliac bifurcation of the aorta). One way to effectively employ task dependency is to schedule the tasks such that outputs of some tasks are used to guide the others. In this sense, optimal task scheduling is key to improve overall performance of a whole-body CAD system. In this paper, we propose a method for task scheduling that is optimal in an information-theoretic sense. The central idea is to schedule tasks in such an order that each operation achieves maximum expected information gain over all the tasks. The formulation embeds two intuitive principles: (1) a task with higher confidence tends to be scheduled earlier; (2) a task with higher predictive power for other tasks tends to be scheduled earlier. More specifically, task dependency is modeled by conditional probability; the outcome of each task is assumed to be probabilistic as well; and the objective function is based on the reduction of the summed conditional entropy over all tasks. The validation is carried out on a challenging CAD problem, multi-organ localization in whole-body CT. Compared to unscheduled and ad hoc scheduled organ detection/localization, our scheduled execution achieves higher accuracy with much less computation time.
Manipulating Slot Machine Preference in Problem Gamblers through Contextual Control
ERIC Educational Resources Information Center
Nastally, Becky L.; Dixon, Mark R.; Jackson, James W.
2010-01-01
Pathological and nonpathological gamblers completed a task that assessed preference among 2 concurrently available slot machines. Subsequent assessments of choice were conducted after various attempts to transfer contextual functions associated with irrelevant characteristics of the slot machines. Results indicated that the nonproblem gambling…
Exact and Metaheuristic Approaches for a Bi-Objective School Bus Scheduling Problem
Chen, Xiaopan; Kong, Yunfeng; Dang, Lanxue; Hou, Yane; Ye, Xinyue
2015-01-01
As a class of hard combinatorial optimization problems, the school bus routing problem has received considerable attention in the last decades. For a multi-school system, given the bus trips for each school, the school bus scheduling problem aims at optimizing bus schedules to serve all the trips within the school time windows. In this paper, we propose two approaches for solving the bi-objective school bus scheduling problem: an exact method of mixed integer programming (MIP) and a metaheuristic method which combines simulated annealing with local search. We develop MIP formulations for homogenous and heterogeneous fleet problems respectively and solve the models by MIP solver CPLEX. The bus type-based formulation for heterogeneous fleet problem reduces the model complexity in terms of the number of decision variables and constraints. The metaheuristic method is a two-stage framework for minimizing the number of buses to be used as well as the total travel distance of buses. We evaluate the proposed MIP and the metaheuristic method on two benchmark datasets, showing that on both instances, our metaheuristic method significantly outperforms the respective state-of-the-art methods. PMID:26176764
Exact and Metaheuristic Approaches for a Bi-Objective School Bus Scheduling Problem.
Chen, Xiaopan; Kong, Yunfeng; Dang, Lanxue; Hou, Yane; Ye, Xinyue
2015-01-01
As a class of hard combinatorial optimization problems, the school bus routing problem has received considerable attention in the last decades. For a multi-school system, given the bus trips for each school, the school bus scheduling problem aims at optimizing bus schedules to serve all the trips within the school time windows. In this paper, we propose two approaches for solving the bi-objective school bus scheduling problem: an exact method of mixed integer programming (MIP) and a metaheuristic method which combines simulated annealing with local search. We develop MIP formulations for homogenous and heterogeneous fleet problems respectively and solve the models by MIP solver CPLEX. The bus type-based formulation for heterogeneous fleet problem reduces the model complexity in terms of the number of decision variables and constraints. The metaheuristic method is a two-stage framework for minimizing the number of buses to be used as well as the total travel distance of buses. We evaluate the proposed MIP and the metaheuristic method on two benchmark datasets, showing that on both instances, our metaheuristic method significantly outperforms the respective state-of-the-art methods. PMID:26176764
NASA Astrophysics Data System (ADS)
Wang, Deyun; Grunder, Olivier; EL Moudni, Abdellah
2014-08-01
This paper considers an integrated lot sizing and scheduling problem for a production-distribution environment with arbitrary job volumes and distinct due dates considerations. In the problem, jobs are firstly batch processed on a batching machine at production stage and then delivered to a pre-specified customer at the subsequent delivery stage by a capacitated vehicle. Each job is associated with a distinct due date and a distinct volume, and has to be delivered to the customer before its due date, i.e. delay is not allowed. The processing time of a batch is a constant independent of the jobs it contains. In production, a constant set-up time as well as a constant set-up cost is required before the first job of this batch is processed. In delivery, a constant delivery time as well as a constant delivery cost is needed for each round-trip delivery between the factory and the customer. Moreover, it is supposed that a job that arrives at the customer before its due date will incur a customer inventory cost. The objective is to find a coordinated lot sizing and scheduling scheme such that the total cost is minimised while guaranteeing a certain customer service level. A mixed integer formulation is proposed for this problem, and then a genetic algorithm is developed to solve it. To evaluate the performance of the proposed genetic algorithm, a lower bound on the objective value is established. Computational experiments show that the proposed genetic algorithm performs well on randomly generated problem instances.
Morrow, Daniel; Raquel, Liza; Schriver, Angela; Redenbo, Seth; Rozovski, David; Weiss, Gillian
2008-09-01
Taking medication requires developing plans to accomplish the activity. This planning challenges older adults because of age-related cognitive limits and inadequate collaboration with health providers. The authors investigated whether an external aid (medtable) supports collaborative planning in the context of a simulated patient/provider task in which pairs of older adults worked together to create medication schedules. Experiment 1 compared pairs who used the medtable, blank paper (unstructured aid), or no aid to create schedules varying in complexity of medication constraints (number of medications and medication co-occurrence restrictions) and patient constraints (available times during the day to take medication). Both aids increased problem-solving accuracy and efficiency (time per unit accuracy) compared to the no-aid condition, primarily for more complex schedules. However, benefits were similar for the two aids. In Experiment 2, a redesigned medtable increased problem-solving accuracy and efficiency compared to blank paper. Both aids presumably supported problem solving by providing a jointly visible workspace for developing schedules. The medtable may be more effective because it externalizes constraints (relationships between medication and patient information), so that participants can more easily organize information. PMID:18808282
Minimizing conflicts: A heuristic repair method for constraint-satisfaction and scheduling problems
NASA Technical Reports Server (NTRS)
Minton, Steve; Johnston, Mark; Philips, Andrew; Laird, Phil
1992-01-01
This paper describes a simple heuristic approach to solving large-scale constraint satisfaction and scheduling problems. In this approach one starts with an inconsistent assignment for a set of variables and searches through the space of possible repairs. The search can be guided by a value-ordering heuristic, the min-conflicts heuristic, that attempts to minimize the number of constraint violations after each step. The heuristic can be used with a variety of different search strategies. We demonstrate empirically that on the n-queens problem, a technique based on this approach performs orders of magnitude better than traditional backtracking techniques. We also describe a scheduling application where the approach has been used successfully. A theoretical analysis is presented both to explain why this method works well on certain types of problems and to predict when it is likely to be most effective.
Genetic Algorithm to minimize flowtime in a no-wait flowshop scheduling problem
NASA Astrophysics Data System (ADS)
Chaudhry, Imran A.; Ahmed, Riaz; Munem Khan, Abdul
2014-07-01
No-wait flowshop is an important scheduling environment having application in many industries. This paper addresses a no-wait flowshop scheduling problem, where the objective function is to minimise total flowtime. A Genetic Algorithm (GA) optimization approach implemented in a spreadsheet environment is suggested to solve this important class of problem. The proposed algorithm employs a general purpose genetic algorithm which can be customised with ease to address any objective function without modifying the optimization routine. Performance of the proposed approach is compared with eight previously reported algorithms for two sets of benchmark problems. Experimental analysis shows that the performance of the suggested approach is comparable with earlier approaches in terms of quality of solution.
ERIC Educational Resources Information Center
Waters, Melissa B.; Lerman, Dorothea C.; Hovanetz, Alyson N.
2009-01-01
The separate and combined effects of visual schedules and extinction plus differential reinforcement of other behavior (DRO) were evaluated to decrease transition-related problem behavior of 2 children diagnosed with autism. Visual schedules alone were ineffective in reducing problem behavior when transitioning from preferred to nonpreferred…
NASA Astrophysics Data System (ADS)
Ramli, Razamin; Tein, Lim Huai
2016-08-01
A good work schedule can improve hospital operations by providing better coverage with appropriate staffing levels in managing nurse personnel. Hence, constructing the best nurse work schedule is the appropriate effort. In doing so, an improved selection operator in the Evolutionary Algorithm (EA) strategy for a nurse scheduling problem (NSP) is proposed. The smart and efficient scheduling procedures were considered. Computation of the performance of each potential solution or schedule was done through fitness evaluation. The best so far solution was obtained via special Maximax&Maximin (MM) parent selection operator embedded in the EA, which fulfilled all constraints considered in the NSP.
Enhancements of evolutionary algorithm for the complex requirements of a nurse scheduling problem
NASA Astrophysics Data System (ADS)
Tein, Lim Huai; Ramli, Razamin
2014-12-01
Over the years, nurse scheduling is a noticeable problem that is affected by the global nurse turnover crisis. The more nurses are unsatisfied with their working environment the more severe the condition or implication they tend to leave. Therefore, the current undesirable work schedule is partly due to that working condition. Basically, there is a lack of complimentary requirement between the head nurse's liability and the nurses' need. In particular, subject to highly nurse preferences issue, the sophisticated challenge of doing nurse scheduling is failure to stimulate tolerance behavior between both parties during shifts assignment in real working scenarios. Inevitably, the flexibility in shifts assignment is hard to achieve for the sake of satisfying nurse diverse requests with upholding imperative nurse ward coverage. Hence, Evolutionary Algorithm (EA) is proposed to cater for this complexity in a nurse scheduling problem (NSP). The restriction of EA is discussed and thus, enhancement on the EA operators is suggested so that the EA would have the characteristic of a flexible search. This paper consists of three types of constraints which are the hard, semi-hard and soft constraints that can be handled by the EA with enhanced parent selection and specialized mutation operators. These operators and EA as a whole contribute to the efficiency of constraint handling, fitness computation as well as flexibility in the search, which correspond to the employment of exploration and exploitation principles.
Duan, Qian-Qian; Yang, Gen-Ke; Pan, Chang-Chun
2014-01-01
A hybrid optimization algorithm combining finite state method (FSM) and genetic algorithm (GA) is proposed to solve the crude oil scheduling problem. The FSM and GA are combined to take the advantage of each method and compensate deficiencies of individual methods. In the proposed algorithm, the finite state method makes up for the weakness of GA which is poor at local searching ability. The heuristic returned by the FSM can guide the GA algorithm towards good solutions. The idea behind this is that we can generate promising substructure or partial solution by using FSM. Furthermore, the FSM can guarantee that the entire solution space is uniformly covered. Therefore, the combination of the two algorithms has better global performance than the existing GA or FSM which is operated individually. Finally, a real-life crude oil scheduling problem from the literature is used for conducting simulation. The experimental results validate that the proposed method outperforms the state-of-art GA method. PMID:24772031
A Novel Joint Problem of Routing, Scheduling, and Variable-Width Channel Allocation in WMNs
Liu, Wan-Yu; Chou, Chun-Hung
2014-01-01
This paper investigates a novel joint problem of routing, scheduling, and channel allocation for single-radio multichannel wireless mesh networks in which multiple channel widths can be adjusted dynamically through a new software technology so that more concurrent transmissions and suppressed overlapping channel interference can be achieved. Although the previous works have studied this joint problem, their linear programming models for the problem were not incorporated with some delicate constraints. As a result, this paper first constructs a linear programming model with more practical concerns and then proposes a simulated annealing approach with a novel encoding mechanism, in which the configurations of multiple time slots are devised to characterize the dynamic transmission process. Experimental results show that our approach can find the same or similar solutions as the optimal solutions for smaller-scale problems and can efficiently find good-quality solutions for a variety of larger-scale problems. PMID:24982990
NASA Astrophysics Data System (ADS)
Bai, Danyu; Zhang, Zhihai
2014-08-01
This article investigates the open-shop scheduling problem with the optimal criterion of minimising the sum of quadratic completion times. For this NP-hard problem, the asymptotic optimality of the shortest processing time block (SPTB) heuristic is proven in the sense of limit. Moreover, three different improvements, namely, the job-insert scheme, tabu search and genetic algorithm, are introduced to enhance the quality of the original solution generated by the SPTB heuristic. At the end of the article, a series of numerical experiments demonstrate the convergence of the heuristic, the performance of the improvements and the effectiveness of the quadratic objective.
NASA Astrophysics Data System (ADS)
Zhu, Li; He, Yongxiang; Xue, Haidong; Chen, Leichen
Traditional genetic algorithms (GA) displays a disadvantage of early-constringency in dealing with scheduling problem. To improve the crossover operators and mutation operators self-adaptively, this paper proposes a self-adaptive GA at the target of multitask scheduling optimization under limited resources. The experiment results show that the proposed algorithm outperforms the traditional GA in evolutive ability to deal with complex task scheduling optimization.
NASA Astrophysics Data System (ADS)
Jafari, Hamed; Salmasi, Nasser
2015-04-01
The nurse scheduling problem (NSP) has received a great amount of attention in recent years. In the NSP, the goal is to assign shifts to the nurses in order to satisfy the hospital's demand during the planning horizon by considering different objective functions. In this research, we focus on maximizing the nurses' preferences for working shifts and weekends off by considering several important factors such as hospital's policies, labor laws, governmental regulations, and the status of nurses at the end of the previous planning horizon in one of the largest hospitals in Iran i.e., Milad Hospital. Due to the shortage of available nurses, at first, the minimum total number of required nurses is determined. Then, a mathematical programming model is proposed to solve the problem optimally. Since the proposed research problem is NP-hard, a meta-heuristic algorithm based on simulated annealing (SA) is applied to heuristically solve the problem in a reasonable time. An initial feasible solution generator and several novel neighborhood structures are applied to enhance performance of the SA algorithm. Inspired from our observations in Milad hospital, random test problems are generated to evaluate the performance of the SA algorithm. The results of computational experiments indicate that the applied SA algorithm provides solutions with average percentage gap of 5.49 % compared to the upper bounds obtained from the mathematical model. Moreover, the applied SA algorithm provides significantly better solutions in a reasonable time than the schedules provided by the head nurses.
A time-shared machine repair problem with mixed spares under N-policy
NASA Astrophysics Data System (ADS)
Jain, Madhu; Shekhar, Chandra; Shukla, Shalini
2016-02-01
The present investigation deals with a machine repair problem consisting of cold and warm standby machines. The machines are subject to breakdown and are repaired by the permanent repairman operating under N-policy. There is provision of one additional removable repairman who is called upon when the work load of failed machines crosses a certain threshold level and is removed as soon as the work load again ceases to that level. Both repairmen recover the failed machines by following the time sharing concept which means that the repairmen share their repair job simultaneously among all the failed machines that have joined the system for repair. Markovian model has been developed by considering the queue dependent rates and solved analytically using the recursive technique. Various performance indices are derived which are further used to obtain the cost function. By taking illustration, numerical simulation and sensitivity analysis have been provided.
Minimizing the total completion time in a two-machine flowshop problem with time delays
NASA Astrophysics Data System (ADS)
Kais Msakni, Mohamed; Khallouli, Wael; Al-Salem, Mohamed; Ladhari, Talel
2016-07-01
This article proposes to solve the problem of minimizing the total completion time in a two-machine permutation flowshop environment in which time delays between the machines are considered. For this purpose, an enumeration algorithm based on the branch-and-bound framework is developed, which includes new lower and upper bounds as well as dominance rules. The computational study shows that problems with up to 40 jobs can be solved in a reasonable amount of time.
NASA Astrophysics Data System (ADS)
Guo, Peng; Cheng, Wenming; Wang, Yi
2014-10-01
The quay crane scheduling problem (QCSP) determines the handling sequence of tasks at ship bays by a set of cranes assigned to a container vessel such that the vessel's service time is minimized. A number of heuristics or meta-heuristics have been proposed to obtain the near-optimal solutions to overcome the NP-hardness of the problem. In this article, the idea of generalized extremal optimization (GEO) is adapted to solve the QCSP with respect to various interference constraints. The resulting GEO is termed the modified GEO. A randomized searching method for neighbouring task-to-QC assignments to an incumbent task-to-QC assignment is developed in executing the modified GEO. In addition, a unidirectional search decoding scheme is employed to transform a task-to-QC assignment to an active quay crane schedule. The effectiveness of the developed GEO is tested on a suite of benchmark problems introduced by K.H. Kim and Y.M. Park in 2004 (European Journal of Operational Research, Vol. 156, No. 3). Compared with other well-known existing approaches, the experiment results show that the proposed modified GEO is capable of obtaining the optimal or near-optimal solution in a reasonable time, especially for large-sized problems.
A Hybrid Cellular Genetic Algorithm for Multi-objective Crew Scheduling Problem
NASA Astrophysics Data System (ADS)
Jolai, Fariborz; Assadipour, Ghazal
Crew scheduling is one of the important problems of the airline industry. This problem aims to cover a number of flights by crew members, such that all the flights are covered. In a robust scheduling the assignment should be so that the total cost, delays, and unbalanced utilization are minimized. As the problem is NP-hard and the objectives are in conflict with each other, a multi-objective meta-heuristic called CellDE, which is a hybrid cellular genetic algorithm, is implemented as the optimization method. The proposed algorithm provides the decision maker with a set of non-dominated or Pareto-optimal solutions, and enables them to choose the best one according to their preferences. A set of problems of different sizes is generated and solved using the proposed algorithm. Evaluating the performance of the proposed algorithm, three metrics are suggested, and the diversity and the convergence of the achieved Pareto front are appraised. Finally a comparison is made between CellDE and PAES, another meta-heuristic algorithm. The results show the superiority of CellDE.
A Two-Stage Stochastic Mixed-Integer Programming Approach to the Smart House Scheduling Problem
NASA Astrophysics Data System (ADS)
Ozoe, Shunsuke; Tanaka, Yoichi; Fukushima, Masao
A “Smart House” is a highly energy-optimized house equipped with photovoltaic systems (PV systems), electric battery systems, fuel cell cogeneration systems (FC systems), electric vehicles (EVs) and so on. Smart houses are attracting much attention recently thanks to their enhanced ability to save energy by making full use of renewable energy and by achieving power grid stability despite an increased power draw for installed PV systems. Yet running a smart house's power system, with its multiple power sources and power storages, is no simple task. In this paper, we consider the problem of power scheduling for a smart house with a PV system, an FC system and an EV. We formulate the problem as a mixed integer programming problem, and then extend it to a stochastic programming problem involving recourse costs to cope with uncertain electricity demand, heat demand and PV power generation. Using our method, we seek to achieve the optimal power schedule running at the minimum expected operation cost. We present some results of numerical experiments with data on real-life demands and PV power generation to show the effectiveness of our method.
Solving a Production Scheduling Problem by Means of Two Biobjective Metaheuristic Procedures
NASA Astrophysics Data System (ADS)
Toncovich, Adrián; Oliveros Colay, María José; Moreno, José María; Corral, Jiménez; Corral, Rafael
2009-11-01
Production planning and scheduling problems emphasize the need for the availability of management tools that can help to assure proper service levels to customers, maintaining, at the same time, the production costs at acceptable levels and maximizing the utilization of the production facilities. In this case, a production scheduling problem that arises in the context of the activities of a company dedicated to the manufacturing of furniture for children and teenagers is addressed. Two bicriteria metaheuristic procedures are proposed to solve the sequencing problem in a production equipment that constitutes the bottleneck of the production process of the company. The production scheduling problem can be characterized as a general flow shop with sequence dependant setup times and additional inventory constraints. Two objectives are simultaneously taken into account when the quality of the candidate solutions is evaluated: the minimization of completion time of all jobs, or makespan, and the minimization of the total flow time of all jobs. Both procedures are based on a local search strategy that responds to the structure of the simulated annealing metaheuristic. In this case, both metaheuristic approaches generate a set of solutions that provides an approximation to the optimal Pareto front. In order to evaluate the performance of the proposed techniques a series of experiments was conducted. After analyzing the results, it can be said that the solutions provided by both approaches are adequate from the viewpoint of the quality as well as the computational effort involved in their generation. Nevertheless, a further refinement of the proposed procedures should be implemented with the aim of facilitating a quasi-automatic definition of the solution parameters.
Insight and analysis problem solving in microbes to machines.
Clark, Kevin B
2015-11-01
A key feature for obtaining solutions to difficult problems, insight is oftentimes vaguely regarded as a special discontinuous intellectual process and/or a cognitive restructuring of problem representation or goal approach. However, this nearly century-old state of art devised by the Gestalt tradition to explain the non-analytical or non-trial-and-error, goal-seeking aptitude of primate mentality tends to neglect problem-solving capabilities of lower animal phyla, Kingdoms other than Animalia, and advancing smart computational technologies built from biological, artificial, and composite media. Attempting to provide an inclusive, precise definition of insight, two major criteria of insight, discontinuous processing and problem restructuring, are here reframed using terminology and statistical mechanical properties of computational complexity classes. Discontinuous processing becomes abrupt state transitions in algorithmic/heuristic outcomes or in types of algorithms/heuristics executed by agents using classical and/or quantum computational models. And problem restructuring becomes combinatorial reorganization of resources, problem-type substitution, and/or exchange of computational models. With insight bounded by computational complexity, humans, ciliated protozoa, and complex technological networks, for example, show insight when restructuring time requirements, combinatorial complexity, and problem type to solve polynomial and nondeterministic polynomial decision problems. Similar effects are expected from other problem types, supporting the idea that insight might be an epiphenomenon of analytical problem solving and consequently a larger information processing framework. Thus, this computational complexity definition of insight improves the power, external and internal validity, and reliability of operational parameters with which to classify, investigate, and produce the phenomenon for computational agents ranging from microbes to man-made devices. PMID
A network flow model for short-term hydro-dominated hydrothermal scheduling problems
Franco, P.E.C. ); Carvalho, M.F. ); Soares, S. )
1994-05-01
This paper is concerned with the Short-Term Hydrothermal Scheduling (STHS) of hydro-dominated power systems. The problem's formulation includes the representation of operational constraints such as the hydraulic coupling between hydro plants in cascade and the transmission limits in the electric network. In order to allow the problem's decomposition into hydraulic and electric subproblems, a linear-quadratic penalty approach is applied to enforce the coupling between hydro and electric variables. As a result, the problem's natural network flow structure is fully exploited through special-purposed network flow algorithms. The technique has been implemented in FORTRAN in a SUN SPARCstation IPX and tested in a 440 KV subsystem of the main interconnected Brazilian power system.
Three-Stage Tabu Search for Solving Large-Scale Flow Shop Scheduling Problems
NASA Astrophysics Data System (ADS)
Xu, Yuedong; Tian, Yajie; Sannomiya, Nobuo
Tabu search is a meta-heuristic approach designed skillfully for finding a suboptimal solution of combinatorial optimization problems. In this paper the tabu search with three stages is proposed for solving large-scale flow shop scheduling problems. In order to obtain a better suboptimal solution in a short computation time, three different candidate lists are used to determine the incumbent solution in the respective search stages. The candidate lists are constructed by restricting the moving of each job. Test problems with four kinds of job data are examined. Based on analyzing the relationship between the candidate list and the suboptimal solution for each job data, a common parameter is given to construct the candidate list during the search process. Comparison of the computation result is made with the genetic algorithm and the basic tabu search, from which it is shown that the proposed tabu search outperforms two others.
NASA Astrophysics Data System (ADS)
Ohno, Akiyoshi; Nishi, Tatsushi; Inuiguchi, Masahiro; Takahashi, Satoru; Ueda, Kenji
In this paper, we propose a column generation for the train-set scheduling problem with regular maintenance constraints. The problem is to allocate the minimum train-set to the train operations required to operate a given train timetable. In the proposed method, a tight lower bound can be obtained from the continuous relaxation for Dantzig-Wolfe reformulation by column generation. The subproblem for the column generation is an elementary shortest path problem with resource constraints. A labeling algorithm is applied to solve the subproblem. In order to reduce the computational effort for solving subproblems, a new state space relaxation of the subproblem is developed in the labeling algorithm. An upper bound is computed by a heuristic algorithm. Computational results demonstrate the effectiveness of the proposed method.
An estimation of distribution algorithm (EDA) variant with QGA for Flowshop scheduling problem
NASA Astrophysics Data System (ADS)
Latif, Muhammad Shahid; Hong, Zhou; Ali, Amir
2014-04-01
In this research article, a hybrid approach is presented which based on well-known meta-heuristics algorithms. This study based on integration of Quantum Genetic Algorithm (QGA) and Estimation of Distribution Algorithm, EDA, (for simplicity we use Q-EDA) for flowshop scheduling, a well-known NP hard Problem, while focusing on the total flow time minimization criterion. A relatively new method has been adopted for the encoding of jobs sequence in flowshop known as angel rotations instead of random keys, so QGA become more efficient. Further, EDA has been integrated to update the population of QGA by making a probability model. This probabilistic model is built and used to generate new candidate solutions which comprised on best individuals, obtained after several repetitions of proposed (Q-EDA) approach. As both heuristics based on probabilistic characteristics, so exhibits excellent learning capability and have minimum chances of being trapped in local optima. The results obtained during this study are presented and compared with contemporary approaches in literature. The current hybrid Q-EDA has implemented on different benchmark problems. The experiments has showed better convergence and results. It is concluded that hybrid Q-EDA algorithm can generally produce better results while implemented for Flowshop Scheduling Problem (FSSP).
Sharpe, Louise; Walker, Michael; Coughlan, Maree-Jo; Enersen, Kirsten; Blaszczynski, Alex
2005-01-01
This study aimed to evaluate the effectiveness of three proposed modifications to the structural characteristics of electronic gaming machines as harm minimisation strategies for non-problem and probable problem gamblers. Structural changes included reducing the maximum bet size, reducing reel spin and removing large note acceptors. Behavioural patterns of play were observed in 779 participants attending clubs and hotels. Observations were conducted in the gaming venue during regular gaming sessions. Eight experimental machines were designed to represent every combination of the modifications. 210 participants played at least one modified and one unmodified machine. Following play, the South Oaks Gambling Screen (SOGS) was administered. More problem than non-problem gamblers used high denomination bill acceptors and bet over one-dollar per wager. Machines modified to accept the one-dollar maximum bet were played for less time and were associated with smaller losses, fewer individual wagers and lower levels of alcohol consumption and smoking. It was concluded that the reduction of maximum bet levels was the only modification likely to be effective as a harm minimization strategy for problem gamblers. PMID:16311879
Some multigrid algorithms for elliptic problems on data parallel machines
Bandy, V.A.; Dendy, J.E. Jr.; Spangenberg, W.H.
1998-01-01
Previously a semicoarsening multigrid algorithm suitable for use on data parallel architectures was investigated. Through the use of new software tools, the performance of this algorithm has been considerably improved. The method has also been extended to three space dimensions. The method performs well for strongly anisotropic problems and for problems with coefficients jumping by orders of magnitude across internal interfaces. The parallel efficiency of this method is analyzed, and its actual performance on the CM-5 is compared with its performance on the CRAY Y-MP and the Sparc-5. A standard coarsening multigrid algorithm is also considered, and they compare its performance on these three platforms as well.
On the integrability of the motion of 3D-Swinging Atwood machine and related problems
NASA Astrophysics Data System (ADS)
Elmandouh, A. A.
2016-03-01
In the present article, we study the problem of the motion of 3D- Swinging Atwood machine. A new integrable case for this problem is announced. We point out a new integrable case describing the motion of a heavy particle on a titled cone.
An Exploratory Study of Problem Gambling on Casino versus Non-Casino Electronic Gaming Machines
ERIC Educational Resources Information Center
Clarke, Dave; Pulford, Justin; Bellringer, Maria; Abbott, Max; Hodgins, David C.
2012-01-01
Electronic gaming machines (EGMs) have been frequently associated with problem gambling. Little research has compared the relative contribution of casino EGMs versus non-casino EGMs on current problem gambling, after controlling for demographic factors and gambling behaviour. Our exploratory study obtained data from questionnaires administered to…
NASA Astrophysics Data System (ADS)
Xu, Ye; Wang, Ling; Wang, Shengyao; Liu, Min
2014-09-01
In this article, an effective hybrid immune algorithm (HIA) is presented to solve the distributed permutation flow-shop scheduling problem (DPFSP). First, a decoding method is proposed to transfer a job permutation sequence to a feasible schedule considering both factory dispatching and job sequencing. Secondly, a local search with four search operators is presented based on the characteristics of the problem. Thirdly, a special crossover operator is designed for the DPFSP, and mutation and vaccination operators are also applied within the framework of the HIA to perform an immune search. The influence of parameter setting on the HIA is investigated based on the Taguchi method of design of experiment. Extensive numerical testing results based on 420 small-sized instances and 720 large-sized instances are provided. The effectiveness of the HIA is demonstrated by comparison with some existing heuristic algorithms and the variable neighbourhood descent methods. New best known solutions are obtained by the HIA for 17 out of 420 small-sized instances and 585 out of 720 large-sized instances.
Whitley, L. Darrell; Watson, Jean-Paul; Howe, Adele E.
2005-06-01
Over the last decade and a half, tabu search algorithms for machine scheduling have gained a near-mythical reputation by consistently equaling or establishing state-of-the-art performance levels on a range of academic and real-world problems. Yet, despite these successes, remarkably little research has been devoted to developing an understanding of why tabu search is so effective on this problem class. In this paper, we report results that provide significant progress in this direction. We consider Nowicki and Smutnicki's i-TSAB tabu search algorithm, which represents the current state-of-the-art for the makespan-minimization form of the classical jobshop scheduling problem. Via a series of controlled experiments, we identify those components of i-TSAB that enable it to achieve state-of-the-art performance levels. In doing so, we expose a number of misconceptions regarding the behavior and/or benefits of tabu search and other local search metaheuristics for the job-shop problem. Our results also serve to focus future research, by identifying those specific directions that are most likely to yield further improvements in performance.
Analysis problems for sequential dynamical systems and communicating state machines
Barrett, C. L.; Hunt, H. B.; Marathe, M. V.; Ravi, S. S.; Rosenkrantz, D. J.; Stearns, R. E.
2001-01-01
A simple sequential dynamical system (SDS) is a triple (G, F, {pi}), where (i) G(V, E) is an undirected graph with n nodes with each node having a 1-bit state, (ii) F = {l_brace} f{sub 1},f{sub 2},...,f{sub n}{r_brace} is a set of local transition functions with f{sub i} denoting a Boolean function associated with node Vv{sub i} and (iii) {pi} is a fixed permutation of (i.e., a total order on) the nodes in V. A single SDS transition is obtained by updating the states of the nodes in V by evaluating the function associated with each of them in the order given by {pi}. Such a (finite) SDS is a mathematical abstraction of simulation systems [BMR99, BR99]. In this paper, we characterize the computational complexity of determining several phase space properties of SDSs. The properties considered are t-REACHABILITY ('Can a given SDS starting from configuration I reach configuration B in t or fewer transitions?'), REACHABILITY('Can a given SDS starting from configuration I ever reach configuration B?') and FIXED POINT REACHABILITY ('Can a given SDS starting from configuration I ever reach configuration in which it stays for ever?'). Our main result is a sharp dichotomy between classes of SDSs whose behavior is 'easy' to predict and those whose behavior is 'hard' to predict. Specifically, we show the following. (1) The t-REACHABILITY, REACHABILITY and the FIXED POINT REACHABILITY problems for SDSs are PSPACE-complete, even when restricted to graphs of bounded bandwidth (and hence of bounded pathwidth and treewidth) and when the function associated with each node is symmetric. The result holds even for regular graphs of constant degree where all the nodes compute the same symmetric Boolean function. (2) In contrast, the t-REACHABILITYm REACHABILITY and FIXED POINT REACHABILITY problems are solvable in polynomial time for SDSs when the Boolean function associated with each node is symmetric and monotone. Two important consequences of our results are the following: (i) The
NASA Astrophysics Data System (ADS)
Gu, Cunchang; Mu, Yundong
2013-03-01
In this paper, we consider a single machine on-line scheduling problem with the special chains precedence and delivery time. All jobs arrive over time. The chains chainsi arrive at time ri , it is known that the processing and delivery time of each job on the chain satisfy one special condition CD a forehand: if the job J(i)j is the predecessor of the job J(i)k on the chain chaini, then they satisfy p(i)j = p(i)k = p >= qj >= qk , i = 1,2, ---,n , where pj and qj denote the processing time and the delivery time of the job Jj respectively. Obviously, if the arrival jobs have no chains precedence, it shows that the length of the corresponding chain is 1. The objective is to minimize the time by which all jobs have been delivered. We provide an on-line algorithm with a competitive ratio of √2 , and the result is the best possible.
A Mixed Integer Linear Program for Solving a Multiple Route Taxi Scheduling Problem
NASA Technical Reports Server (NTRS)
Montoya, Justin Vincent; Wood, Zachary Paul; Rathinam, Sivakumar; Malik, Waqar Ahmad
2010-01-01
Aircraft movements on taxiways at busy airports often create bottlenecks. This paper introduces a mixed integer linear program to solve a Multiple Route Aircraft Taxi Scheduling Problem. The outputs of the model are in the form of optimal taxi schedules, which include routing decisions for taxiing aircraft. The model extends an existing single route formulation to include routing decisions. An efficient comparison framework compares the multi-route formulation and the single route formulation. The multi-route model is exercised for east side airport surface traffic at Dallas/Fort Worth International Airport to determine if any arrival taxi time savings can be achieved by allowing arrivals to have two taxi routes: a route that crosses an active departure runway and a perimeter route that avoids the crossing. Results indicate that the multi-route formulation yields reduced arrival taxi times over the single route formulation only when a perimeter taxiway is used. In conditions where the departure aircraft are given an optimal and fixed takeoff sequence, accumulative arrival taxi time savings in the multi-route formulation can be as high as 3.6 hours more than the single route formulation. If the departure sequence is not optimal, the multi-route formulation results in less taxi time savings made over the single route formulation, but the average arrival taxi time is significantly decreased.
A stochastic model for the cell formation problem considering machine reliability
NASA Astrophysics Data System (ADS)
Esmailnezhad, Bahman; Fattahi, Parviz; Kheirkhah, Amir Saman
2015-03-01
This paper presents a new mathematical model to solve cell formation problem in cellular manufacturing systems, where inter-arrival time, processing time, and machine breakdown time are probabilistic. The objective function maximizes the number of operations of each part with more arrival rate within one cell. Because a queue behind each machine; queuing theory is used to formulate the model. To solve the model, two metaheurstic algorithms such as modified particle swarm optimization and genetic algorithm are proposed. For the generation of initial solutions in these algorithms, a new heuristic method is developed, which always creates feasible solutions. Both metaheurstic algorithms are compared against global solutions obtained from Lingo software's branch and bound (B&B). Also, a statistical method will be used for comparison of solutions of two metaheurstic algorithms. The results of numerical examples indicate that considering the machine breakdown has significant effect on block structures of machine-part matrixes.
NASA Astrophysics Data System (ADS)
Gao, Qian
For both the conventional radio frequency and the comparably recent optical wireless communication systems, extensive effort from the academia had been made in improving the network spectrum efficiency and/or reducing the error rate. To achieve these goals, many fundamental challenges such as power efficient constellation design, nonlinear distortion mitigation, channel training design, network scheduling and etc. need to be properly addressed. In this dissertation, novel schemes are proposed accordingly to deal with specific problems falling in category of these challenges. Rigorous proofs and analyses are provided for each of our work to make a fair comparison with the corresponding peer works to clearly demonstrate the advantages. The first part of this dissertation considers a multi-carrier optical wireless system employing intensity modulation (IM) and direct detection (DD). A block-wise constellation design is presented, which treats the DC-bias that conventionally used solely for biasing purpose as an information basis. Our scheme, we term it MSM-JDCM, takes advantage of the compactness of sphere packing in a higher dimensional space, and in turn power efficient constellations are obtained by solving an advanced convex optimization problem. Besides the significant power gains, the MSM-JDCM has many other merits such as being capable of mitigating nonlinear distortion by including a peak-to-power ratio (PAPR) constraint, minimizing inter-symbol-interference (ISI) caused by frequency-selective fading with a novel precoder designed and embedded, and further reducing the bit-error-rate (BER) by combining with an optimized labeling scheme. The second part addresses several optimization problems in a multi-color visible light communication system, including power efficient constellation design, joint pre-equalizer and constellation design, and modeling of different structured channels with cross-talks. Our novel constellation design scheme, termed CSK-Advanced, is
NASA Astrophysics Data System (ADS)
Izah Anuar, Nurul; Saptari, Adi
2016-02-01
This paper addresses the types of particle representation (encoding) procedures in a population-based stochastic optimization technique in solving scheduling problems known in the job-shop manufacturing environment. It intends to evaluate and compare the performance of different particle representation procedures in Particle Swarm Optimization (PSO) in the case of solving Job-shop Scheduling Problems (JSP). Particle representation procedures refer to the mapping between the particle position in PSO and the scheduling solution in JSP. It is an important step to be carried out so that each particle in PSO can represent a schedule in JSP. Three procedures such as Operation and Particle Position Sequence (OPPS), random keys representation and random-key encoding scheme are used in this study. These procedures have been tested on FT06 and FT10 benchmark problems available in the OR-Library, where the objective function is to minimize the makespan by the use of MATLAB software. Based on the experimental results, it is discovered that OPPS gives the best performance in solving both benchmark problems. The contribution of this paper is the fact that it demonstrates to the practitioners involved in complex scheduling problems that different particle representation procedures can have significant effects on the performance of PSO in solving JSP.
Three hybridization models based on local search scheme for job shop scheduling problem
NASA Astrophysics Data System (ADS)
Balbi Fraga, Tatiana
2015-05-01
This work presents three different hybridization models based on the general schema of Local Search Heuristics, named Hybrid Successive Application, Hybrid Neighborhood, and Hybrid Improved Neighborhood. Despite similar approaches might have already been presented in the literature in other contexts, in this work these models are applied to analyzes the solution of the job shop scheduling problem, with the heuristics Taboo Search and Particle Swarm Optimization. Besides, we investigate some aspects that must be considered in order to achieve better solutions than those obtained by the original heuristics. The results demonstrate that the algorithms derived from these three hybrid models are more robust than the original algorithms and able to get better results than those found by the single Taboo Search.
An extended abstract: A heuristic repair method for constraint-satisfaction and scheduling problems
NASA Technical Reports Server (NTRS)
Minton, Steven; Johnston, Mark D.; Philips, Andrew B.; Laird, Philip
1992-01-01
The work described in this paper was inspired by a surprisingly effective neural network developed for scheduling astronomical observations on the Hubble Space Telescope. Our heuristic constraint satisfaction problem (CSP) method was distilled from an analysis of the network. In the process of carrying out the analysis, we discovered that the effectiveness of the network has little to do with its connectionist implementation. Furthermore, the ideas employed in the network can be implemented very efficiently within a symbolic CSP framework. The symbolic implementation is extremely simple. It also has the advantage that several different search strategies can be employed, although we have found that hill-climbing methods are particularly well-suited for the applications that we have investigated. We begin the paper with a brief review of the neural network. Following this, we describe our symbolic method for heuristic repair.
NASA Astrophysics Data System (ADS)
Kumar, Vijay M.; Murthy, ANN; Chandrashekara, K.
2012-05-01
The production planning problem of flexible manufacturing system (FMS) concerns with decisions that have to be made before an FMS begins to produce parts according to a given production plan during an upcoming planning horizon. The main aspect of production planning deals with machine loading problem in which selection of a subset of jobs to be manufactured and assignment of their operations to the relevant machines are made. Such problems are not only combinatorial optimization problems, but also happen to be non-deterministic polynomial-time-hard, making it difficult to obtain satisfactory solutions using traditional optimization techniques. In this paper, an attempt has been made to address the machine loading problem with objectives of minimization of system unbalance and maximization of throughput simultaneously while satisfying the system constraints related to available machining time and tool slot designing and using a meta-hybrid heuristic technique based on genetic algorithm and particle swarm optimization. The results reported in this paper demonstrate the model efficiency and examine the performance of the system with respect to measures such as throughput and system utilization.
Decision theory for computing variable and value ordering decisions for scheduling problems
NASA Technical Reports Server (NTRS)
Linden, Theodore A.
1993-01-01
Heuristics that guide search are critical when solving large planning and scheduling problems, but most variable and value ordering heuristics are sensitive to only one feature of the search state. One wants to combine evidence from all features of the search state into a subjective probability that a value choice is best, but there has been no solid semantics for merging evidence when it is conceived in these terms. Instead, variable and value ordering decisions should be viewed as problems in decision theory. This led to two key insights: (1) The fundamental concept that allows heuristic evidence to be merged is the net incremental utility that will be achieved by assigning a value to a variable. Probability distributions about net incremental utility can merge evidence from the utility function, binary constraints, resource constraints, and other problem features. The subjective probability that a value is the best choice is then derived from probability distributions about net incremental utility. (2) The methods used for rumor control in Bayesian Networks are the primary way to prevent cycling in the computation of probable net incremental utility. These insights lead to semantically justifiable ways to compute heuristic variable and value ordering decisions that merge evidence from all available features of the search state.
Li, Shanlin; Li, Maoqin
2015-01-01
We consider an integrated production and distribution scheduling problem faced by a typical make-to-order manufacturer which relies on a third-party logistics (3PL) provider for finished product delivery to customers. In the beginning of a planning horizon, the manufacturer has received a set of orders to be processed on a single production line. Completed orders are delivered to customers by a finite number of vehicles provided by the 3PL company which follows a fixed daily or weekly shipping schedule such that the vehicles have fixed departure dates which are not part of the decisions. The problem is to find a feasible schedule that minimizes one of the following objective functions when processing times and weights are oppositely ordered: (1) the total weight of late orders and (2) the number of vehicles used subject to the condition that the total weight of late orders is minimum. We show that both problems are solvable in polynomial time. PMID:25785285
Li, Shanlin; Li, Maoqin
2015-01-01
We consider an integrated production and distribution scheduling problem faced by a typical make-to-order manufacturer which relies on a third-party logistics (3PL) provider for finished product delivery to customers. In the beginning of a planning horizon, the manufacturer has received a set of orders to be processed on a single production line. Completed orders are delivered to customers by a finite number of vehicles provided by the 3PL company which follows a fixed daily or weekly shipping schedule such that the vehicles have fixed departure dates which are not part of the decisions. The problem is to find a feasible schedule that minimizes one of the following objective functions when processing times and weights are oppositely ordered: (1) the total weight of late orders and (2) the number of vehicles used subject to the condition that the total weight of late orders is minimum. We show that both problems are solvable in polynomial time. PMID:25785285
Heuristic algorithms for solving of the tool routing problem for CNC cutting machines
NASA Astrophysics Data System (ADS)
Chentsov, P. A.; Petunin, A. A.; Sesekin, A. N.; Shipacheva, E. N.; Sholohov, A. E.
2015-11-01
The article is devoted to the problem of minimizing the path of the cutting tool to shape cutting machines began. This problem can be interpreted as a generalized traveling salesman problem. Earlier version of the dynamic programming method to solve this problem was developed. Unfortunately, this method allows to process an amount not exceeding thirty circuits. In this regard, the task of constructing quasi-optimal route becomes relevant. In this paper we propose options for quasi-optimal greedy algorithms. Comparison of the results of exact and approximate algorithms is given.
Duan, Qianqian; Yang, Genke; Xu, Guanglin; Pan, Changchun
2014-01-01
This paper is devoted to develop an approximation method for scheduling refinery crude oil operations by taking into consideration the demand uncertainty. In the stochastic model the demand uncertainty is modeled as random variables which follow a joint multivariate distribution with a specific correlation structure. Compared to deterministic models in existing works, the stochastic model can be more practical for optimizing crude oil operations. Using joint chance constraints, the demand uncertainty is treated by specifying proximity level on the satisfaction of product demands. However, the joint chance constraints usually hold strong nonlinearity and consequently, it is still hard to handle it directly. In this paper, an approximation method combines a relax-and-tight technique to approximately transform the joint chance constraints to a serial of parameterized linear constraints so that the complicated problem can be attacked iteratively. The basic idea behind this approach is to approximate, as much as possible, nonlinear constraints by a lot of easily handled linear constraints which will lead to a well balance between the problem complexity and tractability. Case studies are conducted to demonstrate the proposed methods. Results show that the operation cost can be reduced effectively compared with the case without considering the demand correlation. PMID:24757433
NASA Astrophysics Data System (ADS)
Motoyama, H.
1989-05-01
The present situations of superconducting electric power machines in the world and studied problems were investigated from viewpoint of the electric insulation. 50MVA generator (CRIE/Hitachi) or 120MVA generator (KWU/Siemens) where the dc superconducting technique was applied on field windings, are developed. As to Superconducting transformer, 220KVA transformer is trially manufactured and the conceptual design of 1,000MVA transformer is made by W.H. or Alstom. Future problems are the study of protecting method for the overvoltage to superconducting electric power machines and the study to prevent the quench for superconducting windings. The respective insulating characteristics of solid and liquid insulators become clear gradually under the cryogenic condition but a large part of insulating characteristics of composite insulator prepared by combination of both insulators are not clear, so that these problems must be clarified.
Non-clairvoyant Scheduling Games
NASA Astrophysics Data System (ADS)
Dürr, Christoph; Nguyen, Kim Thang
In a scheduling game, each player owns a job and chooses a machine to execute it. While the social cost is the maximal load over all machines (makespan), the cost (disutility) of each player is the completion time of its own job. In the game, players may follow selfish strategies to optimize their cost and therefore their behaviors do not necessarily lead the game to an equilibrium. Even in the case there is an equilibrium, its makespan might be much larger than the social optimum, and this inefficiency is measured by the price of anarchy - the worst ratio between the makespan of an equilibrium and the optimum. Coordination mechanisms aim to reduce the price of anarchy by designing scheduling policies that specify how jobs assigned to a same machine are to be scheduled. Typically these policies define the schedule according to the processing times as announced by the jobs. One could wonder if there are policies that do not require this knowledge, and still provide a good price of anarchy. This would make the processing times be private information and avoid the problem of truthfulness. In this paper we study these so-called non-clairvoyant policies. In particular, we study the RANDOM policy that schedules the jobs in a random order without preemption, and the EQUI policy that schedules the jobs in parallel using time-multiplexing, assigning each job an equal fraction of CPU time.
Linear-time algorithms for scheduling on parallel processors
Monma, C.L.
1982-01-01
Linear-time algorithms are presented for several problems of scheduling n equal-length tasks on m identical parallel processors subject to precedence constraints. This improves upon previous time bounds for the maximum lateness problem with treelike precedence constraints, the number-of-late-tasks problem without precedence constraints, and the one machine maximum lateness problem with general precedence constraints. 5 references.
NASA Astrophysics Data System (ADS)
Trunfio, Roberto
2015-06-01
In a recent article, Guo, Cheng and Wang proposed a randomized search algorithm, called modified generalized extremal optimization (MGEO), to solve the quay crane scheduling problem for container groups under the assumption that schedules are unidirectional. The authors claim that the proposed algorithm is capable of finding new best solutions with respect to a well-known set of benchmark instances taken from the literature. However, as shown in this note, there are some errors in their work that can be detected by analysing the Gantt charts of two solutions provided by MGEO. In addition, some comments on the method used to evaluate the schedule corresponding to a task-to-quay crane assignment and on the search scheme of the proposed algorithm are provided. Finally, to assess the effectiveness of the proposed algorithm, the computational experiments are repeated and additional computational experiments are provided.
Research on Production Scheduling System with Bottleneck Based on Multi-agent
NASA Astrophysics Data System (ADS)
Zhenqiang, Bao; Weiye, Wang; Peng, Wang; Pan, Quanke
Aimed at the imbalance problem of resource capacity in Production Scheduling System, this paper uses Production Scheduling System based on multi-agent which has been constructed, and combines the dynamic and autonomous of Agent; the bottleneck problem in the scheduling is solved dynamically. Firstly, this paper uses Bottleneck Resource Agent to find out the bottleneck resource in the production line, analyses the inherent mechanism of bottleneck, and describes the production scheduling process based on bottleneck resource. Bottleneck Decomposition Agent harmonizes the relationship of job's arrival time and transfer time in Bottleneck Resource Agent and Non-Bottleneck Resource Agents, therefore, the dynamic scheduling problem is simplified as the single machine scheduling of each resource which takes part in the scheduling. Finally, the dynamic real-time scheduling problem is effectively solved in Production Scheduling System.
A multi-objective scatter search for a bi-criteria no-wait flow shop scheduling problem
NASA Astrophysics Data System (ADS)
Rahimi-Vahed, A. R.; Javadi, B.; Rabbani, M.; Tavakkoli-Moghaddam, R.
2008-04-01
The flow shop problem as a typical manufacturing challenge has gained wide attention in academic fields. This article considers a bi-criteria no-wait flow shop scheduling problem (FSSP) in which weighted mean completion time and weighted mean tardiness are to be minimized simultaneously. Since a FSSP has been proved to be NP-hard in a strong sense, a new multi-objective scatter search (MOSS) is designed for finding the locally Pareto-optimal frontier of the problem. To prove the efficiency of the proposed algorithm, various test problems are solved and the reliability of the proposed algorithm, based on some comparison metrics, is compared with a distinguished multi-objective genetic algorithm (GA), i.e. SPEA-II. The computational results show that the proposed MOSS performs better than the above GA, especially for the large-sized problems.
Personalized Education; Solving a Group Formation and Scheduling Problem for Educational Content
ERIC Educational Resources Information Center
Bahargam, Sanaz; Erdos, Dóra; Bestavros, Azer; Terzi, Evimaria
2015-01-01
Whether teaching in a classroom or a Massive Online Open Course it is crucial to present the material in a way that benefits the audience as a whole. We identify two important tasks to solve towards this objective; (1) group students so that they can maximally benefit from peer interaction and (2) find an optimal schedule of the educational…
NASA Technical Reports Server (NTRS)
Gaspin, Christine
1989-01-01
How a neural network can work, compared to a hybrid system based on an operations research and artificial intelligence approach, is investigated through a mission scheduling problem. The characteristic features of each system are discussed.
A federated model for scheduling in wide-area systems
Weissman, J.B.; Grimshaw, A.S.
1996-12-31
In this paper a model for scheduling in wide-area systems is described. The model is federated and utilizes a collection of local site schedulers that control the use of their resources. The wide-area scheduler consults the local site schedulers to obtain candidate machine schedules. A set of issues and challenges inherent to wide-area scheduling are also described and the proposed model is shown to address many of these problems. A distributed algorithm for wide-area scheduling is presented and relies upon information made available about the resource needs of user jobs. The wide-area scheduler will be implemented in Legion, a wide-area computing system developed at the University of Virginia.
NASA Astrophysics Data System (ADS)
Wang, Hongfeng; Fu, Yaping; Huang, Min; Wang, Junwei
2016-03-01
The operation process design is one of the key issues in the manufacturing and service sectors. As a typical operation process, the scheduling with consideration of the deteriorating effect has been widely studied; however, the current literature only studied single function requirement and rarely considered the multiple function requirements which are critical for a real-world scheduling process. In this article, two function requirements are involved in the design of a scheduling process with consideration of the deteriorating effect and then formulated into two objectives of a mathematical programming model. A novel multiobjective evolutionary algorithm is proposed to solve this model with combination of three strategies, i.e. a multiple population scheme, a rule-based local search method and an elitist preserve strategy. To validate the proposed model and algorithm, a series of randomly-generated instances are tested and the experimental results indicate that the model is effective and the proposed algorithm can achieve the satisfactory performance which outperforms the other state-of-the-art multiobjective evolutionary algorithms, such as nondominated sorting genetic algorithm II and multiobjective evolutionary algorithm based on decomposition, on all the test instances.
Quay crane scheduling with dual cycling
NASA Astrophysics Data System (ADS)
Wang, Dandan; Li, Xiaoping
2015-10-01
In this article, the dual cycling quay crane scheduling problem (D-QCSP) with hatches is addressed to minimize the operation cycles of quay cranes. The problem is decomposed into two sub-problems: the intra-group stage (sequencing stacks within each hatch) and the inter-group stage (scheduling all hatches). A new stack sequencing method is constructed for stacks of each hatch, which is modelled as a two-machine non-permutation flow shop scheduling problem. By removing inner gaps using left-shifting, the adapted hatch scheduling sub-problem is modelled as a two-machine grouped flow shop scheduling problem, which contains more precise processing times. A composite heuristic is proposed for the D-QCSP. Based on the derived lower bound, the heuristic is compared with the best existing heuristics on a large number of instances. Experimental results illustrate that the proposal outperforms the existing methods on all instances and dual cycling needs many fewer quay crane operating cycles than single cycling.
NASA Astrophysics Data System (ADS)
Han, Yu-Yan; Gong, Dunwei; Sun, Xiaoyan
2015-07-01
A flow-shop scheduling problem with blocking has important applications in a variety of industrial systems but is underrepresented in the research literature. In this study, a novel discrete artificial bee colony (ABC) algorithm is presented to solve the above scheduling problem with a makespan criterion by incorporating the ABC with differential evolution (DE). The proposed algorithm (DE-ABC) contains three key operators. One is related to the employed bee operator (i.e. adopting mutation and crossover operators of discrete DE to generate solutions with good quality); the second is concerned with the onlooker bee operator, which modifies the selected solutions using insert or swap operators based on the self-adaptive strategy; and the last is for the local search, that is, the insert-neighbourhood-based local search with a small probability is adopted to improve the algorithm's capability in exploitation. The performance of the proposed DE-ABC algorithm is empirically evaluated by applying it to well-known benchmark problems. The experimental results show that the proposed algorithm is superior to the compared algorithms in minimizing the makespan criterion.
NASA Astrophysics Data System (ADS)
Basri, Azyanzuhaila Hasan; Zainuddin, Zaitul Marlizawati
2014-09-01
High efficiency of port operation is required to succeed in the competition between port container terminals. Berth Allocation and Quay Crane Scheduling are the most important part in container terminal operations. The integrated model is formulated as a MIP problem with the objective to minimize the sum of the dwell times, where a vessel's dwell time is measured between arrival and departure including both times waiting to be berthed and servicing time while berthed. The construction of suitable mathematical model is formulated by considering various practical constraints.
Agnetis, Alessandro; Coppi, Alberto; Corsini, Matteo; Dellino, Gabriella; Meloni, Carlo; Pranzo, Marco
2014-03-01
This research aims at supporting hospital management in making prompt Operating Room (OR) planning decisions, when either unpredicted events occur or alternative scenarios or configurations need to be rapidly evaluated. We design and test a planning tool enabling managers to efficiently analyse several alternatives to the current OR planning and scheduling. To this aim, we propose a decomposition approach. More specifically, we first focus on determining the Master Surgical Schedule (MSS) on a weekly basis, by assigning the different surgical disciplines to the available sessions. Next, we allocate surgeries to each session, focusing on elective patients only. Patients are selected from the waiting lists according to several parameters, including surgery duration, waiting time and priority class of the operations. We performed computational experiments to compare the performance of our decomposition approach with an (exact) integrated approach. The case study selected for our simulations is based on the characteristics of the operating theatre (OT) of a medium-size public Italian hospital. Scalability of the method is tested for different OT sizes. A pilot example is also proposed to highlight the usefulness of our approach for decision support. The proposed decomposition approach finds satisfactory solutions with significant savings in computation time. PMID:23783452
Learning to integrate reactivity and deliberation in uncertain planning and scheduling problems
NASA Technical Reports Server (NTRS)
Chien, Steve A.; Gervasio, Melinda T.; Dejong, Gerald F.
1992-01-01
This paper describes an approach to planning and scheduling in uncertain domains. In this approach, a system divides a task on a goal by goal basis into reactive and deliberative components. Initially, a task is handled entirely reactively. When failures occur, the system changes the reactive/deliverative goal division by moving goals into the deliberative component. Because our approach attempts to minimize the number of deliberative goals, we call our approach Minimal Deliberation (MD). Because MD allows goals to be treated reactively, it gains some of the advantages of reactive systems: computational efficiency, the ability to deal with noise and non-deterministic effects, and the ability to take advantage of unforseen opportunities. However, because MD can fall back upon deliberation, it can also provide some of the guarantees of classical planning, such as the ability to deal with complex goal interactions. This paper describes the Minimal Deliberation approach to integrating reactivity and deliberation and describe an ongoing application of the approach to an uncertain planning and scheduling domain.
NASA Astrophysics Data System (ADS)
Yusriski, R.; Sukoyo; Samadhi, T. M. A. A.; Halim, A. H.
2016-02-01
In the manufacturing industry, several identical parts can be processed in batches, and setup time is needed between two consecutive batches. Since the processing times of batches are not always fixed during a scheduling period due to learning and deterioration effects, this research deals with batch scheduling problems with simultaneous learning and deterioration effects. The objective is to minimize total actual flow time, defined as a time interval between the arrival of all parts at the shop and their common due date. The decision variables are the number of batches, integer batch sizes, and the sequence of the resulting batches. This research proposes a heuristic algorithm based on the Lagrange Relaxation. The effectiveness of the proposed algorithm is determined by comparing the resulting solutions of the algorithm to the respective optimal solution obtained from the enumeration method. Numerical experience results show that the average of difference among the solutions is 0.05%.
NASA Technical Reports Server (NTRS)
Phillips, K.
1976-01-01
A mathematical model for job scheduling in a specified context is presented. The model uses both linear programming and combinatorial methods. While designed with a view toward optimization of scheduling of facility and plant operations at the Deep Space Communications Complex, the context is sufficiently general to be widely applicable. The general scheduling problem including options for scheduling objectives is discussed and fundamental parameters identified. Mathematical algorithms for partitioning problems germane to scheduling are presented.
NASA Astrophysics Data System (ADS)
Cram, Ana Catalina
As worldwide environmental awareness grow, alternative sources of energy have become important to mitigate climate change. Biogas in particular reduces greenhouse gas emissions that contribute to global warming and has the potential of providing 25% of the annual demand for natural gas in the U.S. In 2011, 55,000 metric tons of methane emissions were reduced and 301 metric tons of carbon dioxide emissions were avoided through the use of biogas alone. Biogas is produced by anaerobic digestion through the fermentation of organic material. It is mainly composed of methane with a rage of 50 to 80% in its concentration. Carbon dioxide covers 20 to 50% and small amounts of hydrogen, carbon monoxide and nitrogen. The biogas production systems are anaerobic digestion facilities and the optimal operation of an anaerobic digester requires the scheduling of all batches from multiple feedstocks during a specific time horizon. The availability times, biomass quantities, biogas production rates and storage decay rates must all be taken into account for maximal biogas production to be achieved during the planning horizon. Little work has been done to optimize the scheduling of different types of feedstock in anaerobic digestion facilities to maximize the total biogas produced by these systems. Therefore, in the present thesis, a new genetic algorithm is developed with the main objective of obtaining the optimal sequence in which different feedstocks will be processed and the optimal time to allocate to each feedstock in the digester with the main objective of maximizing the production of biogas considering different types of feedstocks, arrival times and decay rates. Moreover, all batches need to be processed in the digester in a specified time with the restriction that only one batch can be processed at a time. The developed algorithm is applied to 3 different examples and a comparison with results obtained in previous studies is presented.
The Block Scheduling Handbook.
ERIC Educational Resources Information Center
Queen, J. Allen
Block scheduling encourages increased comprehensive immersion into subject matter, improved teacher-student relationships, and decreased disciplinary problems. While block scheduling may offer many advantages, moving to a block schedule from conventional scheduling can be a major adjustment for both students and teachers. This guide is intended to…
An efficient annealing in Boltzmann machine in Hopfield neural network
NASA Astrophysics Data System (ADS)
Kin, Teoh Yeong; Hasan, Suzanawati Abu; Bulot, Norhisam; Ismail, Mohammad Hafiz
2012-09-01
This paper proposes and implements Boltzmann machine in Hopfield neural network doing logic programming based on the energy minimization system. The temperature scheduling in Boltzmann machine enhancing the performance of doing logic programming in Hopfield neural network. The finest temperature is determined by observing the ratio of global solution and final hamming distance using computer simulations. The study shows that Boltzmann Machine model is more stable and competent in term of representing and solving difficult combinatory problems.
Hinselmann, Georg; Rosenbaum, Lars; Jahn, Andreas; Fechner, Nikolas; Ostermann, Claude; Zell, Andreas
2011-02-28
The goal of this study was to adapt a recently proposed linear large-scale support vector machine to large-scale binary cheminformatics classification problems and to assess its performance on various benchmarks using virtual screening performance measures. We extended the large-scale linear support vector machine library LIBLINEAR with state-of-the-art virtual high-throughput screening metrics to train classifiers on whole large and unbalanced data sets. The formulation of this linear support machine has an excellent performance if applied to high-dimensional sparse feature vectors. An additional advantage is the average linear complexity in the number of non-zero features of a prediction. Nevertheless, the approach assumes that a problem is linearly separable. Therefore, we conducted an extensive benchmarking to evaluate the performance on large-scale problems up to a size of 175000 samples. To examine the virtual screening performance, we determined the chemotype clusters using Feature Trees and integrated this information to compute weighted AUC-based performance measures and a leave-cluster-out cross-validation. We also considered the BEDROC score, a metric that was suggested to tackle the early enrichment problem. The performance on each problem was evaluated by a nested cross-validation and a nested leave-cluster-out cross-validation. We compared LIBLINEAR against a Naïve Bayes classifier, a random decision forest classifier, and a maximum similarity ranking approach. These reference approaches were outperformed in a direct comparison by LIBLINEAR. A comparison to literature results showed that the LIBLINEAR performance is competitive but without achieving results as good as the top-ranked nonlinear machines on these benchmarks. However, considering the overall convincing performance and computation time of the large-scale support vector machine, the approach provides an excellent alternative to established large-scale classification approaches. PMID
NASA Technical Reports Server (NTRS)
Rash, James
2014-01-01
NASA's space data-communications infrastructure-the Space Network and the Ground Network-provide scheduled (as well as some limited types of unscheduled) data-communications services to user spacecraft. The Space Network operates several orbiting geostationary platforms (the Tracking and Data Relay Satellite System (TDRSS)), each with its own servicedelivery antennas onboard. The Ground Network operates service-delivery antennas at ground stations located around the world. Together, these networks enable data transfer between user spacecraft and their mission control centers on Earth. Scheduling data-communications events for spacecraft that use the NASA communications infrastructure-the relay satellites and the ground stations-can be accomplished today with software having an operational heritage dating from the 1980s or earlier. An implementation of the scheduling methods and algorithms disclosed and formally specified herein will produce globally optimized schedules with not only optimized service delivery by the space data-communications infrastructure but also optimized satisfaction of all user requirements and prescribed constraints, including radio frequency interference (RFI) constraints. Evolutionary algorithms, a class of probabilistic strategies for searching large solution spaces, is the essential technology invoked and exploited in this disclosure. Also disclosed are secondary methods and algorithms for optimizing the execution efficiency of the schedule-generation algorithms themselves. The scheduling methods and algorithms as presented are adaptable to accommodate the complexity of scheduling the civilian and/or military data-communications infrastructure within the expected range of future users and space- or ground-based service-delivery assets. Finally, the problem itself, and the methods and algorithms, are generalized and specified formally. The generalized methods and algorithms are applicable to a very broad class of combinatorial
Automated Planning and Scheduling for Space Mission Operations
NASA Technical Reports Server (NTRS)
Chien, Steve; Jonsson, Ari; Knight, Russell
2005-01-01
Research Trends: a) Finite-capacity scheduling under more complex constraints and increased problem dimensionality (subcontracting, overtime, lot splitting, inventory, etc.) b) Integrated planning and scheduling. c) Mixed-initiative frameworks. d) Management of uncertainty (proactive and reactive). e) Autonomous agent architectures and distributed production management. e) Integration of machine learning capabilities. f) Wider scope of applications: 1) analysis of supplier/buyer protocols & tradeoffs; 2) integration of strategic & tactical decision-making; and 3) enterprise integration.
Integrating tactical and operational decisions in fixed job scheduling
NASA Astrophysics Data System (ADS)
Türsel Eliiyi, Deniz
2013-12-01
Two different problems are introduced in this article to handle capacity and scheduling decisions simultaneously in the fixed job scheduling framework. The combined fixed job scheduling (CFJS) problem integrates these decisions assuming fixed costs for the usage of identical parallel machines, whereas the working time determination (WTD) problem involves unit-time operating or rental costs. Mathematical models for both problems are presented along with the worst case time complexities. While an exact polynomial-time algorithm is proposed for the CFJS problem, a heuristic algorithm is developed for the WTD problem as it is shown to be strongly NP hard. Computational experiments are carried out for evaluating the performance of the algorithms. The results reveal that the solutions by the exact algorithm for the CFJS problem are much faster than a state-of-the-art commercial solver, particularly for large instances. For the WTD problem, the developed heuristic provides high-quality solutions in very short computation times.
The home health care routing and scheduling problem with interdependent services.
Mankowska, Dorota Slawa; Meisel, Frank; Bierwirth, Christian
2014-03-01
This paper presents a model for the daily planning of health care services carried out at patients' homes by staff members of a home care company. The planning takes into account individual service requirements of the patients, individual qualifications of the staff and possible interdependencies between different service operations. Interdependencies of services can include, for example, a temporal separation of two services as is required if drugs have to be administered a certain time before providing a meal. Other services like handling a disabled patient may require two staff members working together at a patient's home. The time preferences of patients are included in terms of given time windows. In this paper, we propose a planning approach for the described problem, which can be used for optimizing economical and service oriented measures of performance. A mathematical model formulation is proposed together with a powerful heuristic based on a sophisticated solution representation. PMID:23780750
Reinforcement learning in scheduling
NASA Technical Reports Server (NTRS)
Dietterich, Tom G.; Ok, Dokyeong; Zhang, Wei; Tadepalli, Prasad
1994-01-01
The goal of this research is to apply reinforcement learning methods to real-world problems like scheduling. In this preliminary paper, we show that learning to solve scheduling problems such as the Space Shuttle Payload Processing and the Automatic Guided Vehicle (AGV) scheduling can be usefully studied in the reinforcement learning framework. We discuss some of the special challenges posed by the scheduling domain to these methods and propose some possible solutions we plan to implement.
Brown, Stephen L; Rodda, Simone; Phillips, James G
2004-12-01
Arousal-based theories of gambling suggest that excitement gained from gambling reinforces further gambling behavior. However, recent theories of emotion conceptualize mood as comprising both arousal and valence dimensions. Thus, excitement comprises arousal with positive valence. We examined self-reported changes in arousal and affective valence in 27 problem and 40 nonproblem gamblers playing electronic gaming machines (EGMs). Problem gamblers reported greater arousal increases after gambling and increases in negative valence if they lost. This accords poorly with an excitement-based explanation of problem gambling. PMID:15530730
Learning dominance relations in combinatorial search problems
NASA Technical Reports Server (NTRS)
Yu, Chee-Fen; Wah, Benjamin W.
1988-01-01
Dominance relations commonly are used to prune unnecessary nodes in search graphs, but they are problem-dependent and cannot be derived by a general procedure. The authors identify machine learning of dominance relations and the applicable learning mechanisms. A study of learning dominance relations using learning by experimentation is described. This system has been able to learn dominance relations for the 0/1-knapsack problem, an inventory problem, the reliability-by-replication problem, the two-machine flow shop problem, a number of single-machine scheduling problems, and a two-machine scheduling problem. It is considered that the same methodology can be extended to learn dominance relations in general.
Integrated resource scheduling in a distributed scheduling environment
NASA Technical Reports Server (NTRS)
Zoch, David; Hall, Gardiner
1988-01-01
The Space Station era presents a highly-complex multi-mission planning and scheduling environment exercised over a highly distributed system. In order to automate the scheduling process, customers require a mechanism for communicating their scheduling requirements to NASA. A request language that a remotely-located customer can use to specify his scheduling requirements to a NASA scheduler, thus automating the customer-scheduler interface, is described. This notation, Flexible Envelope-Request Notation (FERN), allows the user to completely specify his scheduling requirements such as resource usage, temporal constraints, and scheduling preferences and options. The FERN also contains mechanisms for representing schedule and resource availability information, which are used in the inter-scheduler inconsistency resolution process. Additionally, a scheduler is described that can accept these requests, process them, generate schedules, and return schedule and resource availability information to the requester. The Request-Oriented Scheduling Engine (ROSE) was designed to function either as an independent scheduler or as a scheduling element in a network of schedulers. When used in a network of schedulers, each ROSE communicates schedule and resource usage information to other schedulers via the FERN notation, enabling inconsistencies to be resolved between schedulers. Individual ROSE schedules are created by viewing the problem as a constraint satisfaction problem with a heuristically guided search strategy.
Trajectory classification in circular restricted three-body problem using support vector machine
NASA Astrophysics Data System (ADS)
Li, Weipeng; Huang, Hai; Peng, Fujun
2015-07-01
In the circular restricted three-body problem (CR3BP), transit orbit is a class of orbit which can pass through the bottleneck region of the zero velocity curve and escapes from the vicinity of the primary or the secondary. This kind of orbit plays a very important role in the design of space exploration missions. A kind of low-energy interplanetary transfer, which is called Interplanetary Superhighway (IPS), can be realized by utilizing transit orbits. To use the transit orbit in actual mission design, a key issue is to find an algorithm which can separate the states corresponding to transit orbits from the states corresponding to other types of orbits rapidly. In fact, the distribution of transit orbit in the phase space has been investigated by numerical method, and a Fourier series approximation method has been introduced to describe the boundary of transit orbits. However, the Fourier series approximation method needs several hundred sets of Fourier series. The coefficients of these Fourier series are neither easy to be computed nor convenient to be stored, which makes the method can hardly be used in actual mission design. In this paper, the support vector machine (SVM) is used to classify the trajectories in the CR3BP. Using the Gaussian kernel, the 6-dimensional states in the CR3BP are mapped into an infinite-dimensional space, and the bound of the transit orbits is described by a hyperplane. A training data generation method is introduced, which reduces the size of training data by generating the states near the hyperplane. The numerical results show that the proposed algorithm gives the good correct rate of classification, and its computing speed is much faster than that of the Fourier series approximation method.
Protocols for distributive scheduling
NASA Technical Reports Server (NTRS)
Richards, Stephen F.; Fox, Barry
1993-01-01
The increasing complexity of space operations and the inclusion of interorganizational and international groups in the planning and control of space missions lead to requirements for greater communication, coordination, and cooperation among mission schedulers. These schedulers must jointly allocate scarce shared resources among the various operational and mission oriented activities while adhering to all constraints. This scheduling environment is complicated by such factors as the presence of varying perspectives and conflicting objectives among the schedulers, the need for different schedulers to work in parallel, and limited communication among schedulers. Smooth interaction among schedulers requires the use of protocols that govern such issues as resource sharing, authority to update the schedule, and communication of updates. This paper addresses the development and characteristics of such protocols and their use in a distributed scheduling environment that incorporates computer-aided scheduling tools. An example problem is drawn from the domain of space shuttle mission planning.
Rau, B.R.
1996-02-01
Modulo scheduling is a framework within which algorithms for software pipelining innermost loops may be defined. The framework specifies a set of constraints that must be met in order to achieve a legal modulo schedule. A wide variety of algorithms and heuristics can be defined within this framework. Little work has been done to evaluate and compare alternative algorithms and heuristics for modulo scheduling from the viewpoints of schedule quality as well as computational complexity. This, along with a vague and unfounded perception that modulo scheduling is computationally expensive as well as difficult to implement, have inhibited its corporation into product compilers. This paper presents iterative modulo scheduling, a practical algorithm that is capable of dealing with realistic machine models. The paper also characterizes the algorithm in terms of the quality of the generated schedules as well as the computational incurred.
NASA Astrophysics Data System (ADS)
Haribara, Yoshitaka; Utsunomiya, Shoko; Yamamoto, Yoshihisa
An optical parametric oscillator network driven by a quantum measurement-feedback circuit, composed of optical homodyne detectors, analog-to-digital conversion devices and field programmable gate arrays (FPGA), is proposed and analysed as a scalable coherent Ising machine. The new scheme has an advantage that a large number of optical coupling paths, which is proportional to the square of a problem size in the worst case, can be replaced by a single quantum measurement-feedback circuit. There is additional advantage in the new scheme that a three body or higher order Ising interaction can be implemented in the FPGA digital circuit. Noise associated with the measurement-feedback process is governed by the standard quantum limit. Numerical simulation based on c-number coupled Langevin equations demonstrate a satisfying performance of the proposed Ising machine against the NP-hard MAX-CUT problems.
Spike: Artificial intelligence scheduling for Hubble space telescope
NASA Technical Reports Server (NTRS)
Johnston, Mark; Miller, Glenn; Sponsler, Jeff; Vick, Shon; Jackson, Robert
1990-01-01
Efficient utilization of spacecraft resources is essential, but the accompanying scheduling problems are often computationally intractable and are difficult to approximate because of the presence of numerous interacting constraints. Artificial intelligence techniques were applied to the scheduling of the NASA/ESA Hubble Space Telescope (HST). This presents a particularly challenging problem since a yearlong observing program can contain some tens of thousands of exposures which are subject to a large number of scientific, operational, spacecraft, and environmental constraints. New techniques were developed for machine reasoning about scheduling constraints and goals, especially in cases where uncertainty is an important scheduling consideration and where resolving conflicts among conflicting preferences is essential. These technique were utilized in a set of workstation based scheduling tools (Spike) for HST. Graphical displays of activities, constraints, and schedules are an important feature of the system. High level scheduling strategies using both rule based and neural network approaches were developed. While the specific constraints implemented are those most relevant to HST, the framework developed is far more general and could easily handle other kinds of scheduling problems. The concept and implementation of the Spike system are described along with some experiments in adapting Spike to other spacecraft scheduling domains.
ERIC Educational Resources Information Center
Davis, Harold S.; Bechard, Joseph E.
A flexible schedule allows teachers to change group size, group composition, and class length according to the purpose of the lesson. This pamphlet presents various "master" schedules for flexible scheduling: (1) Simple block schedules, (2) back-to-back schedules, (3) interdisciplinary schedules, (4) school-wide block schedules, (5) open-lab…
NASA Technical Reports Server (NTRS)
Rash, James L.
2010-01-01
NASA's space data-communications infrastructure, the Space Network and the Ground Network, provide scheduled (as well as some limited types of unscheduled) data-communications services to user spacecraft via orbiting relay satellites and ground stations. An implementation of the methods and algorithms disclosed herein will be a system that produces globally optimized schedules with not only optimized service delivery by the space data-communications infrastructure but also optimized satisfaction of all user requirements and prescribed constraints, including radio frequency interference (RFI) constraints. Evolutionary search, a class of probabilistic strategies for searching large solution spaces, constitutes the essential technology in this disclosure. Also disclosed are methods and algorithms for optimizing the execution efficiency of the schedule-generation algorithm itself. The scheduling methods and algorithms as presented are adaptable to accommodate the complexity of scheduling the civilian and/or military data-communications infrastructure. Finally, the problem itself, and the methods and algorithms, are generalized and specified formally, with applicability to a very broad class of combinatorial optimization problems.
A knowledge-based system for diagnosis of mastitis problems at the herd level. 2. Machine milking.
Hogeveen, H; van Vliet, J H; Noordhuizen-Stassen, E N; De Koning, C; Tepp, D M; Brand, A
1995-07-01
A knowledge-based system for the diagnosis of mastitis problems at the herd level must search for possible causes, including malfunctioning milking machines or incorrect milking technique. A knowledge-based system on general mechanisms of mastitis infection, using hierarchical conditional causal models, was extended. Model building entailed extensive cooperation between the knowledge engineer and a domain expert. The extended knowledge-based system contains 12 submodels underlying the overview models. Nine submodels were concerned with mastitis problems arising from machine milking. These models are briefly described. The knowledge-based system has been validated by other experts after which the models were adjusted slightly. The final knowledge-based system was validated to data collected at 17 commercial dairy farms with high SCC in the bulk milk. Reports containing the farm data were accompanied by recommendations made by a dairy farm advisor. This validation showed good agreement between the knowledge-based system and the dairy farm advisors. The described knowledge-based system is a good tool for dairy farm advisors to solve herd mastitis problems caused by a malfunctioning milking machine or incorrect milking technique. PMID:7593837
Parallel scheduling algorithms
Dekel, E.; Sahni, S.
1983-01-01
Parallel algorithms are given for scheduling problems such as scheduling to minimize the number of tardy jobs, job sequencing with deadlines, scheduling to minimize earliness and tardiness penalties, channel assignment, and minimizing the mean finish time. The shared memory model of parallel computers is used to obtain fast algorithms. 26 references.
Job Shop Scheduling Focusing on Role of Buffer
NASA Astrophysics Data System (ADS)
Hino, Rei; Kusumi, Tetsuya; Yoo, Jae-Kyu; Shimizu, Yoshiaki
A scheduling problem is formulated in order to consistently manage each manufacturing resource, including machine tools, assembly robots, AGV, storehouses, material shelves, and so on. The manufacturing resources are classified into three types: producer, location, and mover. This paper focuses especially on the role of the buffer, and the differences among these types are analyzed. A unified scheduling formulation is derived from the analytical results based on the resource’s roles. Scheduling procedures based on dispatching rules are also proposed in order to numerically evaluate job shop-type production having finite buffer capacity. The influences of the capacity of bottle-necked production devices and the buffer on productivity are discussed.
Time sharing massively parallel machines. Draft
Gorda, B.; Wolski, R.
1995-03-01
As part of the Massively Parallel Computing Initiative (MPCI) at the Lawrence Livermore National Laboratory, the authors have developed a simple, effective and portable time sharing mechanism by scheduling gangs of processes on tightly coupled parallel machines. By time-sharing the resources, the system interleaves production and interactive jobs. Immediate priority is given to interactive use, maintaining good response time. Production jobs are scheduled during idle periods, making use of the otherwise unused resources. In this paper the authors discuss their experience with gang scheduling over the 3 year life-time of the project. In section 2, they motivate the project and discuss some of its details. Section 3.0 describes the general scheduling problem and how gang scheduling addresses it. In section 4.0, they describe the implementation. Section 8.0 presents results culled over the lifetime of the project. They conclude this paper with some observations and possible future directions.
Investigating the Human Computer Interaction Problems with Automated Teller Machine Navigation Menus
ERIC Educational Resources Information Center
Curran, Kevin; King, David
2008-01-01
Purpose: The automated teller machine (ATM) has become an integral part of our society. However, using the ATM can often be a frustrating experience as people frequently reinsert cards to conduct multiple transactions. This has led to the research question of whether ATM menus are designed in an optimal manner. This paper aims to address the…
Efficient static scheduling of loops on synchronous multiprocessors
Zaky, A.M.
1989-01-01
This dissertation investigates efficient compile-time scheduling techniques for exploiting parallelism on synchronous multiprocessors. Synchronous multiprocessors, e.g. Very Long Instruction Word (VLIW) machines, are very effective in utilizing unstructured fine-grained parallelism in programs. The effectiveness of such machines is crucially dependent on the static compile-time analysis and detection of potential parallelism. The first part of the dissertation focuses on scheduling sequential loops on multiprocessors with multiple identical processor units. The problem of determining the maximal initiation rate for the execution of a sequential loop with uniform dependence distances on a synchronous multiprocessor is addressed and cast as an eigenvalue problem in a path algebra. A low-order polynomial algorithm for the determination of the optimal loop initiation rate is developed, and a schedule that exploits fine-grained parallelism and achieves the optimal initiation rate is developed under an idealized unbounded processor model. Next, the concepts developed above are extended to deal with perfectly-nested loops with uniform dependences. A strategy is developed to identify both the loop level and fine-grained expression level parallelism in nested loops, and to efficiently schedule such loops on synchronous multiprocessors. Loop scheduling techniques such as Do-Across, Wavefront scheduling, and fine-grained scheduling techniques such as loop unfolding are shown to be derivable within the presented framework.
Richards, E P; Walter, C
1989-01-01
This article is the first in a series about the dilemmas posed by products-liability law. The authors point out that manufacturers of complex medical devices may have an unrealistic expectation about user expertise, the lack of which often causes injury to patients, thereby leading to litigation over the devices. The learned-intermediary problem arises when engineers and lawyers disagree over whether a device is designed for a sophisticated rather than unsophisticated user. The authors discuss why the law assumes that anesthesia machines are like lawnmowers, which are usually operated by untrained users, rather than airplanes. However, they argue that anesthesia machines, being complicated to understand as well as dangerous, are much more like airplanes. They conclude that medical-device manufacturers must develop strategies to assure that legally risky devices are restricted to competent users; otherwise, innovation will suffer and legal costs will destroy the competitiveness of the US medical device manufacturers. PMID:18238310
Engineering solution to the problem of ingot solidification in slab continuous-casting machines
NASA Astrophysics Data System (ADS)
Shichkov, A. N.; Bykasova, E. N.; Bashirov, N. G.; Klochai, V. V.; Bystrov, L. G.
1995-03-01
An engineering solution to ingot solidification and the regularities of growth of an ingot envelope thickness and the coordinate of the end of slab solidification directly on slab continuous-casting machines (SCCM) are given, and ingot solidification conditions are determined. Examples of calculation of the envelope thickness and the coordinate of the end of solidification are provided for slab continuous-casting machines utilized at the Cherepovetsk integrated metallurgical complex (CherMC) and at the cast-and-iron works of the Aisenhüttenstadt Joint-Stock Company. A graphical algorithm for determining the cooling capacity of the secondary cooling zone is presented, and a nomogram for calibration of the cooling capacity of forced secondary cooling against the major and minor radii of an SCCM is developed.
ERIC Educational Resources Information Center
Karabinus, Robert A.; Boris, Richard
This document describes the development and implementation of a computer based registration and scheduling information system at Northern Illinois University. Because of personnel shortages, the University sought and received help from commercial computer firms. Implementation of scheduling, registration, and billing systems was accomplished in a…
Approximation Schemes for Scheduling with Availability Constraints
NASA Astrophysics Data System (ADS)
Fu, Bin; Huo, Yumei; Zhao, Hairong
We investigate the problems of scheduling n weighted jobs to m identical machines with availability constraints. We consider two different models of availability constraints: the preventive model where the unavailability is due to preventive machine maintenance, and the fixed job model where the unavailability is due to a priori assignment of some of the n jobs to certain machines at certain times. Both models have applications such as turnaround scheduling or overlay computing. In both models, the objective is to minimize the total weighted completion time. We assume that m is a constant, and the jobs are non-resumable. For the preventive model, it has been shown that there is no approximation algorithm if all machines have unavailable intervals even when w i = p i for all jobs. In this paper, we assume there is one machine permanently available and the processing time of each job is equal to its weight for all jobs. We develop the first PTAS when there are constant number of unavailable intervals. One main feature of our algorithm is that the classification of large and small jobs is with respect to each individual interval, thus not fixed. This classification allows us (1) to enumerate the assignments of large jobs efficiently; (2) and to move small jobs around without increasing the objective value too much, and thus derive our PTAS. Then we show that there is no FPTAS in this case unless P = NP.
Scheduling Jobs with Genetic Algorithms
NASA Astrophysics Data System (ADS)
Ferrolho, António; Crisóstomo, Manuel
Most scheduling problems are NP-hard, the time required to solve the problem optimally increases exponentially with the size of the problem. Scheduling problems have important applications, and a number of heuristic algorithms have been proposed to determine relatively good solutions in polynomial time. Recently, genetic algorithms (GA) are successfully used to solve scheduling problems, as shown by the growing numbers of papers. GA are known as one of the most efficient algorithms for solving scheduling problems. But, when a GA is applied to scheduling problems various crossovers and mutations operators can be applicable. This paper presents and examines a new concept of genetic operators for scheduling problems. A software tool called hybrid and flexible genetic algorithm (HybFlexGA) was developed to examine the performance of various crossover and mutation operators by computing simulations of job scheduling problems.
Automated telescope scheduling
NASA Technical Reports Server (NTRS)
Johnston, Mark D.
1988-01-01
With the ever increasing level of automation of astronomical telescopes the benefits and feasibility of automated planning and scheduling are becoming more apparent. Improved efficiency and increased overall telescope utilization are the most obvious goals. Automated scheduling at some level has been done for several satellite observatories, but the requirements on these systems were much less stringent than on modern ground or satellite observatories. The scheduling problem is particularly acute for Hubble Space Telescope: virtually all observations must be planned in excruciating detail weeks to months in advance. Space Telescope Science Institute has recently made significant progress on the scheduling problem by exploiting state-of-the-art artificial intelligence software technology. What is especially interesting is that this effort has already yielded software that is well suited to scheduling groundbased telescopes, including the problem of optimizing the coordinated scheduling of more than one telescope.
Automated telescope scheduling
NASA Astrophysics Data System (ADS)
Johnston, Mark D.
1988-08-01
With the ever increasing level of automation of astronomical telescopes the benefits and feasibility of automated planning and scheduling are becoming more apparent. Improved efficiency and increased overall telescope utilization are the most obvious goals. Automated scheduling at some level has been done for several satellite observatories, but the requirements on these systems were much less stringent than on modern ground or satellite observatories. The scheduling problem is particularly acute for Hubble Space Telescope: virtually all observations must be planned in excruciating detail weeks to months in advance. Space Telescope Science Institute has recently made significant progress on the scheduling problem by exploiting state-of-the-art artificial intelligence software technology. What is especially interesting is that this effort has already yielded software that is well suited to scheduling groundbased telescopes, including the problem of optimizing the coordinated scheduling of more than one telescope.
The preview control problem with application to man-machine system analysis
NASA Technical Reports Server (NTRS)
Tomizuka, M.; Whitney, D. E.
1973-01-01
The preview control problem is formulated in a general form and its solution is obtained. The analytical tool used is discrete stochastic optimal control theory. Aiming the application to manual control situations with preview, time delay, observation noise, motor noise, etc. were included in formulating the problem. Manual preview control experiments were performed to qualitatively check the validity of the model, and it was found that the mechanism of the manual control problem was explained by the developed model.
NASA Astrophysics Data System (ADS)
Effati, Meysam; Thill, Jean-Claude; Shabani, Shahin
2015-04-01
The contention of this paper is that many social science research problems are too "wicked" to be suitably studied using conventional statistical and regression-based methods of data analysis. This paper argues that an integrated geospatial approach based on methods of machine learning is well suited to this purpose. Recognizing the intrinsic wickedness of traffic safety issues, such approach is used to unravel the complexity of traffic crash severity on highway corridors as an example of such problems. The support vector machine (SVM) and coactive neuro-fuzzy inference system (CANFIS) algorithms are tested as inferential engines to predict crash severity and uncover spatial and non-spatial factors that systematically relate to crash severity, while a sensitivity analysis is conducted to determine the relative influence of crash severity factors. Different specifications of the two methods are implemented, trained, and evaluated against crash events recorded over a 4-year period on a regional highway corridor in Northern Iran. Overall, the SVM model outperforms CANFIS by a notable margin. The combined use of spatial analysis and artificial intelligence is effective at identifying leading factors of crash severity, while explicitly accounting for spatial dependence and spatial heterogeneity effects. Thanks to the demonstrated effectiveness of a sensitivity analysis, this approach produces comprehensive results that are consistent with existing traffic safety theories and supports the prioritization of effective safety measures that are geographically targeted and behaviorally sound on regional highway corridors.
Effects of problem structure and dialogue type on the performance of the man/machine interface
Palko, J.B.
1986-01-01
This research project is intended to provide guidance for software designers who must decide on a dialogue style for interactive problem solving support for new or infrequent users. In addition, it examines the relative performance of these dialogues in environments with a varying amount of problem structure. The three dialogue styles that are recommended by various writers in the field of information systems are: (1) menu driven, (2) question/response, and (3) form filling. It is concluded that if an interface is properly designed it probably does not matter which dialogue style is used in some problem settings. It is also clear that adding problem parameters reduces the ability of the problem solver to determine the best solution.
Scheduling constrained tools using heuristic techniques
NASA Astrophysics Data System (ADS)
Maram, Venkataramana; Rahman, Syariza Abdul; Maram, Sandhya Rani
2015-12-01
One of the main challenge to the current manufacturing production planning is to provide schedules of operations to maximize resource utilization to yield highest overall productivity. This is achieved by scheduling available resources to activities. There can be many different real time scenarios with different combination of input resources to produce parts. In this paper, the problem is simplified to single machine with individual process times and due dates to represent the real world scheduling problem. The main objective function is to minimize the total tardiness or late jobs. Nearest greedy method of assignment problem algorithm is used to find the initial solution followed by Simulated Annealing (SA) algorithm for the improvement part. Simulated Annealing is one of the meta-heuristic techniques in solving combinatorial optimization problem. The general purpose Microsoft Visual C++ is used to developed algorithm for finding the best solution. The proposed hybrid approach able to generate best schedule in 7th and optimal in 170th iteration with tardiness 8 and 7 hours respectively.
NASA Technical Reports Server (NTRS)
Messing, Fredric
1993-01-01
This paper provides an analytical formulation to predict scheduling success for a class of problems frequently referred to as activity scheduling. Space Network communications scheduling is an example of activity scheduling. The principal assumption is that the activity start times are randomly distributed over the available time in the time line. The formulation makes it possible to estimate how much of the demand can be scheduled as a function of the demand, number of resources, activity duration, and activity flexibility. The paper includes computed results for a variety of resource and demand conditions. The results demonstrate that even with highly flexible activities, it is difficult to schedule demand greater than 60 percent of resources without the use of optimization and conflict resolution capabilities in the scheduling system.
Automated Scheduling Via Artificial Intelligence
NASA Technical Reports Server (NTRS)
Biefeld, Eric W.; Cooper, Lynne P.
1991-01-01
Artificial-intelligence software that automates scheduling developed in Operations Mission Planner (OMP) research project. Software used in both generation of new schedules and modification of existing schedules in view of changes in tasks and/or available resources. Approach based on iterative refinement. Although project focused upon scheduling of operations of scientific instruments and other equipment aboard spacecraft, also applicable to such terrestrial problems as scheduling production in factory.
Research on schedulers for astronomical observatories
NASA Astrophysics Data System (ADS)
Colome, Josep; Colomer, Pau; Guàrdia, Josep; Ribas, Ignasi; Campreciós, Jordi; Coiffard, Thierry; Gesa, Lluis; Martínez, Francesc; Rodler, Florian
2012-09-01
The main task of a scheduler applied to astronomical observatories is the time optimization of the facility and the maximization of the scientific return. Scheduling of astronomical observations is an example of the classical task allocation problem known as the job-shop problem (JSP), where N ideal tasks are assigned to M identical resources, while minimizing the total execution time. A problem of higher complexity, called the Flexible-JSP (FJSP), arises when the tasks can be executed by different resources, i.e. by different telescopes, and it focuses on determining a routing policy (i.e., which machine to assign for each operation) other than the traditional scheduling decisions (i.e., to determine the starting time of each operation). In most cases there is no single best approach to solve the planning system and, therefore, various mathematical algorithms (Genetic Algorithms, Ant Colony Optimization algorithms, Multi-Objective Evolutionary algorithms, etc.) are usually considered to adapt the application to the system configuration and task execution constraints. The scheduling time-cycle is also an important ingredient to determine the best approach. A shortterm scheduler, for instance, has to find a good solution with the minimum computation time, providing the system with the capability to adapt the selected task to varying execution constraints (i.e., environment conditions). We present in this contribution an analysis of the task allocation problem and the solutions currently in use at different astronomical facilities. We also describe the schedulers for three different projects (CTA, CARMENES and TJO) where the conclusions of this analysis are applied to develop a suitable routine.
SPINN: a straightforward machine learning solution to the pulsar candidate selection problem
NASA Astrophysics Data System (ADS)
Morello, V.; Barr, E. D.; Bailes, M.; Flynn, C. M.; Keane, E. F.; van Straten, W.
2014-09-01
We describe SPINN (Straightforward Pulsar Identification using Neural Networks), a high-performance machine learning solution developed to process increasingly large data outputs from pulsar surveys. SPINN has been cross-validated on candidates from the southern High Time Resolution Universe (HTRU) survey and shown to identify every known pulsar found in the survey data while maintaining a false positive rate of 0.64 per cent. Furthermore, it ranks 99 per cent of pulsars among the top 0.11 per cent of candidates, and 95 per cent among the top 0.01 per cent. In conjunction with the PEASOUP pipeline, it has already discovered four new pulsars in a re-processing of the intermediate Galactic latitude area of HTRU, three of which have spin periods shorter than 5 ms. SPINN's ability to reduce the amount of candidates to visually inspect by up to four orders of magnitude makes it a very promising tool for future large-scale pulsar surveys. In an effort to provide a common testing ground for pulsar candidate selection tools and stimulate interest in their development, we also make publicly available the set of candidates on which SPINN was cross-validated.
Engineering-Based Problem Solving in the Middle School: Design and Construction with Simple Machines
ERIC Educational Resources Information Center
English, Lyn D.; Hudson, Peter; Dawes, Les
2013-01-01
Incorporating engineering concepts into middle school curriculum is seen as an effective way to improve students' problem-solving skills. A selection of findings is reported from a science, technology, engineering and mathematics (STEM)-based unit in which students in the second year (grade 8) of a three-year longitudinal study explored…
MONTO: A Machine-Readable Ontology for Teaching Word Problems in Mathematics
ERIC Educational Resources Information Center
Lalingkar, Aparna; Ramnathan, Chandrashekar; Ramani, Srinivasan
2015-01-01
The Indian National Curriculum Framework has as one of its objectives the development of mathematical thinking and problem solving ability. However, recent studies conducted in Indian metros have expressed concern about students' mathematics learning. Except in some private coaching academies, regular classroom teaching does not include problem…
NASA Astrophysics Data System (ADS)
Chen, Xili; Hao, Xinchang; Lin, Hao Wen; Murata, Tomohiro
The applications of composite dispatching rules for multi objective dynamic scheduling have been widely studied in literature. In general, a composite dispatching rule is a combination of several elementary dispatching rules, which is designed to optimize multiple objectives of interest under a certain scheduling environment. The relative importance of elementary dispatching rules is modeled by weight factors. A critical issue for implementation of composite dispatching rule is that the inappropriate weight values may result in poor performance. This paper presents an offline scheduling knowledge acquisition method based on reinforcement learning using simulation technique. The scheduling knowledge is applied to adjust the appropriate weight values of elementary dispatching rules in composite manner with respect to work in process fluctuation of machines during online scheduling. Implementation of the proposed method in a two objectives dynamic job shop scheduling problem is demonstrated and the results are satisfactory.
Completable scheduling: An integrated approach to planning and scheduling
NASA Technical Reports Server (NTRS)
Gervasio, Melinda T.; Dejong, Gerald F.
1992-01-01
The planning problem has traditionally been treated separately from the scheduling problem. However, as more realistic domains are tackled, it becomes evident that the problem of deciding on an ordered set of tasks to achieve a set of goals cannot be treated independently of the problem of actually allocating resources to the tasks. Doing so would result in losing the robustness and flexibility needed to deal with imperfectly modeled domains. Completable scheduling is an approach which integrates the two problems by allowing an a priori planning module to defer particular planning decisions, and consequently the associated scheduling decisions, until execution time. This allows a completable scheduling system to maximize plan flexibility by allowing runtime information to be taken into consideration when making planning and scheduling decision. Furthermore, through the criteria of achievability placed on deferred decision, a completable scheduling system is able to retain much of the goal-directedness and guarantees of achievement afforded by a priori planning. The completable scheduling approach is further enhanced by the use of contingent explanation-based learning, which enables a completable scheduling system to learn general completable plans from example and improve its performance through experience. Initial experimental results show that completable scheduling outperforms classical scheduling as well as pure reactive scheduling in a simple scheduling domain.
Planning and scheduling research at NASA Ames Research Center
NASA Technical Reports Server (NTRS)
Friedland, Peter
1990-01-01
Planning and scheduling is the area of artificial intelligence research that focuses on the determination of a series of operations to achieve some set of (possibly) interacting goals and the placement of those operations in a timeline that allows them to be accomplished given available resources. Work in this area at the NASA Ames Research Center ranging from basic research in constrain-based reasoning and machine learning, to the development of efficient scheduling tools, to the application of such tools to complex agency problems is described.
Adaptive Parallel Job Scheduling with Flexible CoScheduling
Frachtenberg, Eitan; Feitelson, Dror; Petrini, Fabrizio; Fernandez, Juan
2005-11-01
Abstract—Many scientific and high-performance computing applications consist of multiple processes running on different processors that communicate frequently. Because of their synchronization needs, these applications can suffer severe performance penalties if their processes are not all coscheduled to run together. Two common approaches to coscheduling jobs are batch scheduling, wherein nodes are dedicated for the duration of the run, and gang scheduling, wherein time slicing is coordinated across processors. Both work well when jobs are load-balanced and make use of the entire parallel machine. However, these conditions are rarely met and most realistic workloads consequently suffer from both internal and external fragmentation, in which resources and processors are left idle because jobs cannot be packed with perfect efficiency. This situation leads to reduced utilization and suboptimal performance. Flexible CoScheduling (FCS) addresses this problem by monitoring each job’s computation granularity and communication pattern and scheduling jobs based on their synchronization and load-balancing requirements. In particular, jobs that do not require stringent synchronization are identified, and are not coscheduled; instead, these processes are used to reduce fragmentation. FCS has been fully implemented on top of the STORM resource manager on a 256-processor Alpha cluster and compared to batch, gang, and implicit coscheduling algorithms. This paper describes in detail the implementation of FCS and its performance evaluation with a variety of workloads, including large-scale benchmarks, scientific applications, and dynamic workloads. The experimental results show that FCS saturates at higher loads than other algorithms (up to 54 percent higher in some cases), and displays lower response times and slowdown than the other algorithms in nearly all scenarios.
Multiagent scheduling method with earliness and tardiness objectives in flexible job shops.
Wu, Zuobao; Weng, Michael X
2005-04-01
Flexible job-shop scheduling problems are an important extension of the classical job-shop scheduling problems and present additional complexity. Such problems are mainly due to the existence of a considerable amount of overlapping capacities with modern machines. Classical scheduling methods are generally incapable of addressing such capacity overlapping. We propose a multiagent scheduling method with job earliness and tardiness objectives in a flexible job-shop environment. The earliness and tardiness objectives are consistent with the just-in-time production philosophy which has attracted significant attention in both industry and academic community. A new job-routing and sequencing mechanism is proposed. In this mechanism, two kinds of jobs are defined to distinguish jobs with one operation left from jobs with more than one operation left. Different criteria are proposed to route these two kinds of jobs. Job sequencing enables to hold a job that may be completed too early. Two heuristic algorithms for job sequencing are developed to deal with these two kinds of jobs. The computational experiments show that the proposed multiagent scheduling method significantly outperforms the existing scheduling methods in the literature. In addition, the proposed method is quite fast. In fact, the simulation time to find a complete schedule with over 2000 jobs on ten machines is less than 1.5 min. PMID:15828657
Wayne F. Boyer; Gurdeep S. Hura
2005-09-01
The Problem of obtaining an optimal matching and scheduling of interdependent tasks in distributed heterogeneous computing (DHC) environments is well known to be an NP-hard problem. In a DHC system, task execution time is dependent on the machine to which it is assigned and task precedence constraints are represented by a directed acyclic graph. Recent research in evolutionary techniques has shown that genetic algorithms usually obtain more efficient schedules that other known algorithms. We propose a non-evolutionary random scheduling (RS) algorithm for efficient matching and scheduling of inter-dependent tasks in a DHC system. RS is a succession of randomized task orderings and a heuristic mapping from task order to schedule. Randomized task ordering is effectively a topological sort where the outcome may be any possible task order for which the task precedent constraints are maintained. A detailed comparison to existing evolutionary techniques (GA and PSGA) shows the proposed algorithm is less complex than evolutionary techniques, computes schedules in less time, requires less memory and fewer tuning parameters. Simulation results show that the average schedules produced by RS are approximately as efficient as PSGA schedules for all cases studied and clearly more efficient than PSGA for certain cases. The standard formulation for the scheduling problem addressed in this paper is Rm|prec|Cmax.,
NASA Technical Reports Server (NTRS)
Tanner, Steve; Hughes, Angi; Byrd, Jim
1987-01-01
Resupply scheduling for the Space Station presents some formidable logistics problems. One of the most basic problems is assigning supplies to a series of shuttle resupply missions. A prototype logistics expert system which constructs resupply schedules was developed. This prototype is able to reconstruct feasible resupply plans. In addition, analysts can use the system to evaluate the impact of adding, deleting or modifying launches, cargo space, experiments, etc.
State-based scheduling: An architecture for telescope observation scheduling
NASA Technical Reports Server (NTRS)
Muscettola, Nicola; Smith, Stephen F.
1989-01-01
The applicability of constraint-based scheduling, a methodology previously developed and validated in the domain of factory scheduling, is extended to problem domains that require attendance to a wider range of state-dependent constraints. The problem of constructing and maintaining a short-term observation schedule for the Hubble Space Telescope (HST), which typifies this type of domain is the focus of interest. The nature of the constraints encountered in the HST domain is examined, system requirements are discussed with respect to utilization of a constraint-based scheduling methodology in such domains, and a general framework for state-based scheduling is presented.
... Labor & birth > Scheduling a c-section Scheduling a c-section E-mail to a friend Please fill ... develop before she’s born. Why can scheduling a c-section for non-medical reasons be a problem? ...
Sun, Yan; Lang, Maoxiang; Wang, Danzhu
2016-01-01
The transportation of hazardous materials is always accompanied by considerable risk that will impact public and environment security. As an efficient and reliable transportation organization, a multimodal service should participate in the transportation of hazardous materials. In this study, we focus on transporting hazardous materials through the multimodal service network and explore the hazardous materials multimodal routing problem from the operational level of network planning. To formulate this problem more practicably, minimizing the total generalized costs of transporting the hazardous materials and the social risk along the planned routes are set as the optimization objectives. Meanwhile, the following formulation characteristics will be comprehensively modelled: (1) specific customer demands; (2) multiple hazardous material flows; (3) capacitated schedule-based rail service and uncapacitated time-flexible road service; and (4) environmental risk constraint. A bi-objective mixed integer nonlinear programming model is first built to formulate the routing problem that combines the formulation characteristics above. Then linear reformations are developed to linearize and improve the initial model so that it can be effectively solved by exact solution algorithms on standard mathematical programming software. By utilizing the normalized weighted sum method, we can generate the Pareto solutions to the bi-objective optimization problem for a specific case. Finally, a large-scale empirical case study from the Beijing-Tianjin-Hebei Region in China is presented to demonstrate the feasibility of the proposed methods in dealing with the practical problem. Various scenarios are also discussed in the case study. PMID:27483294
Sun, Yan; Lang, Maoxiang; Wang, Danzhu
2016-01-01
The transportation of hazardous materials is always accompanied by considerable risk that will impact public and environment security. As an efficient and reliable transportation organization, a multimodal service should participate in the transportation of hazardous materials. In this study, we focus on transporting hazardous materials through the multimodal service network and explore the hazardous materials multimodal routing problem from the operational level of network planning. To formulate this problem more practicably, minimizing the total generalized costs of transporting the hazardous materials and the social risk along the planned routes are set as the optimization objectives. Meanwhile, the following formulation characteristics will be comprehensively modelled: (1) specific customer demands; (2) multiple hazardous material flows; (3) capacitated schedule-based rail service and uncapacitated time-flexible road service; and (4) environmental risk constraint. A bi-objective mixed integer nonlinear programming model is first built to formulate the routing problem that combines the formulation characteristics above. Then linear reformations are developed to linearize and improve the initial model so that it can be effectively solved by exact solution algorithms on standard mathematical programming software. By utilizing the normalized weighted sum method, we can generate the Pareto solutions to the bi-objective optimization problem for a specific case. Finally, a large-scale empirical case study from the Beijing–Tianjin–Hebei Region in China is presented to demonstrate the feasibility of the proposed methods in dealing with the practical problem. Various scenarios are also discussed in the case study. PMID:27483294
Conway, L.
1984-01-01
To meet the challenge of certain critical problems in defense, the Defense Advanced Research Projects Agency (DARPA) is initiating an important new program in strategic computing. By seizing an opportunity to leverage recent advances in artificial intelligence, computer science, and microelectronics, the agency plans to create a new generation of machine-intelligence technology.
Minimizing makespan on parallel machines with batch arrivals
NASA Astrophysics Data System (ADS)
Chung, Tsui-Ping; Liao, Ching-Jong; Lin, Chien-Hung
2012-04-01
Most studies in the scheduling literature assume that jobs arrive at time zero, while some studies assume that jobs arrive individually at non-zero times. However, both assumptions may not be valid in practice because jobs usually arrive in batches. In this article, a scheduling model for an identical parallel machine problem with batch arrivals is formulated. Because of the NP-hardness of the problem, a heuristic based on a simplified version of lexicographical search is proposed. To verify the heuristic, two lower bounding schemes are developed, where one lower bound is tight, and the list scheduling heuristic is compared. Extensive computational experiments demonstrate that the proposed heuristic is quite efficient in obtaining near optimal solution with an average error of less than 1.58%. The percentage improvement (from the lower bound) of the heuristic solution on the solution by the list scheduling is as large as 31.68.
NASA Astrophysics Data System (ADS)
Kalsom Yusof, Umi; Nor Akmal Khalid, Mohd
2015-05-01
Semiconductor industries need to constantly adjust to the rapid pace of change in the market. Most manufactured products usually have a very short life cycle. These scenarios imply the need to improve the efficiency of capacity planning, an important aspect of the machine allocation plan known for its complexity. Various studies have been performed to balance productivity and flexibility in the flexible manufacturing system (FMS). Many approaches have been developed by the researchers to determine the suitable balance between exploration (global improvement) and exploitation (local improvement). However, not much work has been focused on the domain of machine allocation problem that considers the effects of machine breakdowns. This paper develops a model to minimize the effect of machine breakdowns, thus increasing the productivity. The objectives are to minimize system unbalance and makespan as well as increase throughput while satisfying the technological constraints such as machine time availability. To examine the effectiveness of the proposed model, results for throughput, system unbalance and makespan on real industrial datasets were performed with applications of intelligence techniques, that is, a hybrid of genetic algorithm and harmony search. The result aims to obtain a feasible solution to the domain problem.
Cakar, Tarik; Koker, Rasit
2015-01-01
A particle swarm optimization algorithm (PSO) has been used to solve the single machine total weighted tardiness problem (SMTWT) with unequal release date. To find the best solutions three different solution approaches have been used. To prepare subhybrid solution system, genetic algorithms (GA) and simulated annealing (SA) have been used. In the subhybrid system (GA and SA), GA obtains a solution in any stage, that solution is taken by SA and used as an initial solution. When SA finds better solution than this solution, it stops working and gives this solution to GA again. After GA finishes working the obtained solution is given to PSO. PSO searches for better solution than this solution. Later it again sends the obtained solution to GA. Three different solution systems worked together. Neurohybrid system uses PSO as the main optimizer and SA and GA have been used as local search tools. For each stage, local optimizers are used to perform exploitation to the best particle. In addition to local search tools, neurodominance rule (NDR) has been used to improve performance of last solution of hybrid-PSO system. NDR checked sequential jobs according to total weighted tardiness factor. All system is named as neurohybrid-PSO solution system. PMID:26221134
Cakar, Tarik; Koker, Rasit
2015-01-01
A particle swarm optimization algorithm (PSO) has been used to solve the single machine total weighted tardiness problem (SMTWT) with unequal release date. To find the best solutions three different solution approaches have been used. To prepare subhybrid solution system, genetic algorithms (GA) and simulated annealing (SA) have been used. In the subhybrid system (GA and SA), GA obtains a solution in any stage, that solution is taken by SA and used as an initial solution. When SA finds better solution than this solution, it stops working and gives this solution to GA again. After GA finishes working the obtained solution is given to PSO. PSO searches for better solution than this solution. Later it again sends the obtained solution to GA. Three different solution systems worked together. Neurohybrid system uses PSO as the main optimizer and SA and GA have been used as local search tools. For each stage, local optimizers are used to perform exploitation to the best particle. In addition to local search tools, neurodominance rule (NDR) has been used to improve performance of last solution of hybrid-PSO system. NDR checked sequential jobs according to total weighted tardiness factor. All system is named as neurohybrid-PSO solution system. PMID:26221134
NASA Astrophysics Data System (ADS)
Pei, Jun; Liu, Xinbao; Pardalos, Panos M.; Fan, Wenjuan; Wang, Ling; Yang, Shanlin
2016-03-01
Motivated by applications in manufacturing industry, we consider a supply chain scheduling problem, where each job is characterised by non-identical sizes, different release times and unequal processing times. The objective is to minimise the makespan by making batching and sequencing decisions. The problem is formalised as a mixed integer programming model and proved to be strongly NP-hard. Some structural properties are presented for both the general case and a special case. Based on these properties, a lower bound is derived, and a novel two-phase heuristic (TP-H) is developed to solve the problem, which guarantees to obtain a worst case performance ratio of ?. Computational experiments with a set of different sizes of random instances are conducted to evaluate the proposed approach TP-H, which is superior to another two heuristics proposed in the literature. Furthermore, the experimental results indicate that TP-H can effectively and efficiently solve large-size problems in a reasonable time.
Genetic algorithm based system for patient scheduling in highly constrained situations.
Podgorelec, V; Kokol, P
1997-12-01
In medicine and health care there are a lot of situations when patients have to be scheduled on different devices and/or with different physicians or therapists. It may concern preventive examinations, laboratory tests or convalescent therapies, therefore we are always looking for an optimal schedule that would result in finishing all the activities scheduled as soon as possible, with the least patient waiting time and maximum device utilization. Since patient scheduling is a highly complex problem, it is impossible to make a qualitative schedule by hand or even with exact heuristic methods. Therefore we developed a powerful automated scheduling method for highly constrained situations based on genetic algorithms and machine learning. In this paper we present the method, together with the whole process of schedule generation, the important parameters to direct the evolution and how the algorithm is guaranteed to produce only feasible solutions, not breaking any of the required constraints. We applied the described method to a problem of scheduling patients with different therapy needs to a limited number of therapeutic devices, but the algorithm can be easily modified for use in similar situations. The results are quite encouraging and since all the solutions are feasible, the method can be easily incorporated into an interactive user interface, which can be of major importance when scheduling patients, and human resources in general, is considered. PMID:9555628
Tricker, Christopher; Rock, Adam J; Clark, Gavin I
2016-06-01
In order to enhance our understanding of the nature of poker-machine problem-gambling, a community sample of 37 poker-machine gamblers (M age = 32 years, M PGSI = 5; PGSI = Problem Gambling Severity Index) were assessed for urge to gamble (responses on a visual analogue scale) and altered state of consciousness (assessed by the Altered State of Awareness dimension of the Phenomenology of Consciousness Inventory) at baseline, after a neutral cue, and after a gambling cue. It was found that (a) problem-gambling severity (PGSI score) predicted increase in urge (from neutral cue to gambling cue, controlling for baseline; sr (2) = .19, p = .006) and increase in altered state of consciousness (from neutral cue to gambling cue, controlling for baseline; sr (2) = .57, p < .001), and (b) increase in altered state of consciousness (from neutral cue to gambling cue) mediated the relationship between problem-gambling severity and increase in urge (from neutral cue to gambling cue; κ(2) = .40, 99 % CI [.08, .71]). These findings suggest that cue-reactive altered state of consciousness is an important component of cue-reactive urge in poker-machine problem-gamblers. PMID:26026986
NASA Astrophysics Data System (ADS)
Paksi, A. B. N.; Ma'ruf, A.
2016-02-01
In general, both machines and human resources are needed for processing a job on production floor. However, most classical scheduling problems have ignored the possible constraint caused by availability of workers and have considered only machines as a limited resource. In addition, along with production technology development, routing flexibility appears as a consequence of high product variety and medium demand for each product. Routing flexibility is caused by capability of machines that offers more than one machining process. This paper presents a method to address scheduling problem constrained by both machines and workers, considering routing flexibility. Scheduling in a Dual-Resource Constrained shop is categorized as NP-hard problem that needs long computational time. Meta-heuristic approach, based on Genetic Algorithm, is used due to its practical implementation in industry. Developed Genetic Algorithm uses indirect chromosome representative and procedure to transform chromosome into Gantt chart. Genetic operators, namely selection, elitism, crossover, and mutation are developed to search the best fitness value until steady state condition is achieved. A case study in a manufacturing SME is used to minimize tardiness as objective function. The algorithm has shown 25.6% reduction of tardiness, equal to 43.5 hours.
A Genetic Algorithm for Flow Shop Scheduling with Assembly Operations to Minimize Makespan
NASA Astrophysics Data System (ADS)
Bhongade, A. S.; Khodke, P. M.
2014-04-01
Manufacturing systems, in which, several parts are processed through machining workstations and later assembled to form final products, is common. Though scheduling of such problems are solved using heuristics, available solution approaches can provide solution for only moderate sized problems due to large computation time required. In this work, scheduling approach is developed for such flow-shop manufacturing system having machining workstations followed by assembly workstations. The initial schedule is generated using Disjunctive method and genetic algorithm (GA) is applied further for generating schedule for large sized problems. GA is found to give near optimal solution based on the deviation of makespan from lower bound. The lower bound of makespan of such problem is estimated and percent deviation of makespan from lower bounds is used as a performance measure to evaluate the schedules. Computational experiments are conducted on problems developed using fractional factorial orthogonal array, varying the number of parts per product, number of products, and number of workstations (ranging upto 1,520 number of operations). A statistical analysis indicated the significance of all the three factors considered. It is concluded that GA method can obtain optimal makespan.