Multi-objective Mobile Robot Scheduling Problem with Dynamic Time Windows

DEFF Research Database (Denmark)

Dang, Vinh Quang; Nielsen, Izabela Ewa; Steger-Jensen, Kenn

2012-01-01

This paper deals with the problem of scheduling feeding tasks of a single mobile robot which has capability of supplying parts to feeders on pro-duction lines. The performance criterion is to minimize the total traveling time of the robot and the total tardiness of the feeding tasks being scheduled...

Comparison of heuristics for an economic lot scheduling problem with deliberated coproduction

Directory of Open Access Journals (Sweden)

Pilar I. Vidal-Carreras

2009-12-01

Full Text Available We built on the Economic Lot Scheduling Problem Scheduling (ELSP literature by making some modifications in order to introduce new constraints which had not been thoroughly studied with a view to simulating specific real situations. Specifically, our aim is to propose and simulate different scheduling policies for a new ELSP variant: Deliberated Coproduction. This problem comprises a product system in an ELSP environment in which we may choose if more than one product can be produced on the machine at a given time. We expressly consider the option of coproducing two products whose demand is not substitutable. In order to draw conclusions, a simulation model and its results were developed in the article by employing modified Bomberger data which include two items that could be produced simultaneously.

Joint optimization of production scheduling and machine group preventive maintenance

International Nuclear Information System (INIS)

Xiao, Lei; Song, Sanling; Chen, Xiaohui; Coit, David W.

2016-01-01

Joint optimization models were developed combining group preventive maintenance of a series system and production scheduling. In this paper, we propose a joint optimization model to minimize the total cost including production cost, preventive maintenance cost, minimal repair cost for unexpected failures and tardiness cost. The total cost depends on both the production process and the machine maintenance plan associated with reliability. For the problems addressed in this research, any machine unavailability leads to system downtime. Therefore, it is important to optimize the preventive maintenance of machines because their performance impacts the collective production processing associated with all machines. Too lengthy preventive maintenance intervals may be associated with low scheduled machine maintenance cost, but may incur expensive costs for unplanned failure due to low machine reliability. Alternatively, too frequent preventive maintenance activities may achieve the desired high reliability machines, but unacceptably high scheduled maintenance cost. Additionally, product scheduling plans affect tardiness and maintenance cost. Two results are obtained when solving the problem; the optimal group preventive maintenance interval for machines, and the assignment of each job, including the corresponding start time and completion time. To solve this non-deterministic polynomial-time problem, random keys genetic algorithms are used, and a numerical example is solved to illustrate the proposed model. - Highlights: • Group preventive maintenance (PM) planning and production scheduling are jointed. • Maintenance interval and assignment of jobs are decided by minimizing total cost. • Relationships among system age, PM, job processing time are quantified. • Random keys genetic algorithms (GA) are used to solve the NP-hard problem. • Random keys GA and Particle Swarm Optimization (PSO) are compared.

Refinery scheduling

Energy Technology Data Exchange (ETDEWEB)

Magalhaes, Marcus V.; Fraga, Eder T. [PETROBRAS, Rio de Janeiro, RJ (Brazil); Shah, Nilay [Imperial College, London (United Kingdom)

2004-07-01

This work addresses the refinery scheduling problem using mathematical programming techniques. The solution adopted was to decompose the entire refinery model into a crude oil scheduling and a product scheduling problem. The envelope for the crude oil scheduling problem is composed of a terminal, a pipeline and the crude area of a refinery, including the crude distillation units. The solution method adopted includes a decomposition technique based on the topology of the system. The envelope for the product scheduling comprises all tanks, process units and products found in a refinery. Once crude scheduling decisions are Also available the product scheduling is solved using a rolling horizon algorithm. All models were tested with real data from PETROBRAS' REFAP refinery, located in Canoas, Southern Brazil. (author)

Research on the ITOC based scheduling system for ship piping production

Science.gov (United States)

Li, Rui; Liu, Yu-Jun; Hamada, Kunihiro

2010-12-01

Manufacturing of ship piping systems is one of the major production activities in shipbuilding. The schedule of pipe production has an important impact on the master schedule of shipbuilding. In this research, the ITOC concept was introduced to solve the scheduling problems of a piping factory, and an intelligent scheduling system was developed. The system, in which a product model, an operation model, a factory model, and a knowledge database of piping production were integrated, automated the planning process and production scheduling. Details of the above points were discussed. Moreover, an application of the system in a piping factory, which achieved a higher level of performance as measured by tardiness, lead time, and inventory, was demonstrated.

Uncertainty management by relaxation of conflicting constraints in production process scheduling

Science.gov (United States)

Dorn, Juergen; Slany, Wolfgang; Stary, Christian

1992-01-01

Mathematical-analytical methods as used in Operations Research approaches are often insufficient for scheduling problems. This is due to three reasons: the combinatorial complexity of the search space, conflicting objectives for production optimization, and the uncertainty in the production process. Knowledge-based techniques, especially approximate reasoning and constraint relaxation, are promising ways to overcome these problems. A case study from an industrial CIM environment, namely high-grade steel production, is presented to demonstrate how knowledge-based scheduling with the desired capabilities could work. By using fuzzy set theory, the applied knowledge representation technique covers the uncertainty inherent in the problem domain. Based on this knowledge representation, a classification of jobs according to their importance is defined which is then used for the straightforward generation of a schedule. A control strategy which comprises organizational, spatial, temporal, and chemical constraints is introduced. The strategy supports the dynamic relaxation of conflicting constraints in order to improve tentative schedules.

Integrated network design and scheduling problems :

Energy Technology Data Exchange (ETDEWEB)

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.

Multiobjective Joint Optimization of Production Scheduling and Maintenance Planning in the Flexible Job-Shop Problem

Directory of Open Access Journals (Sweden)

Jianfei Ye

2015-01-01

Full Text Available In order to solve the joint optimization of production scheduling and maintenance planning problem in the flexible job-shop, a multiobjective joint optimization model considering the maximum completion time and maintenance costs per unit time is established based on the concept of flexible job-shop and preventive maintenance. A weighted sum method is adopted to eliminate the index dimension. In addition, a double-coded genetic algorithm is designed according to the problem characteristics. The best result under the circumstances of joint decision-making is obtained through multiple simulation experiments, which proves the validity of the algorithm. We can prove the superiority of joint optimization model by comparing the result of joint decision-making project with the result of independent decision-making project under fixed preventive maintenance period. This study will enrich and expand the theoretical framework and analytical methods of this problem; it provides a scientific decision analysis method for enterprise to make production plan and maintenance plan.

Scheduling in Engineering, Project, and Production Management

OpenAIRE

Chien-Ho Ko

2015-01-01

This issue presents five papers selected from the 2013 (4th) International Conference on Engineering, Project, and Production Management (EPPM2013) held in Bangkok, Thailand. Three of the papers deal with scheduling problems faced in project and production management, while the remaining two focus on engineering management issues.

Job shop scheduling problem with late work criterion

Science.gov (United States)

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.

Energy-Efficient Scheduling Problem Using an Effective Hybrid Multi-Objective Evolutionary Algorithm

Directory of Open Access Journals (Sweden)

Lvjiang Yin

2016-12-01

Full Text Available Nowadays, manufacturing enterprises face the challenge of just-in-time (JIT production and energy saving. Therefore, study of JIT production and energy consumption is necessary and important in manufacturing sectors. Moreover, energy saving can be attained by the operational method and turn off/on idle machine method, which also increases the complexity of problem solving. Thus, most researchers still focus on small scale problems with one objective: a single machine environment. However, the scheduling problem is a multi-objective optimization problem in real applications. In this paper, a single machine scheduling model with controllable processing and sequence dependence setup times is developed for minimizing the total earliness/tardiness (E/T, cost, and energy consumption simultaneously. An effective multi-objective evolutionary algorithm called local multi-objective evolutionary algorithm (LMOEA is presented to tackle this multi-objective scheduling problem. To accommodate the characteristic of the problem, a new solution representation is proposed, which can convert discrete combinational problems into continuous problems. Additionally, a multiple local search strategy with self-adaptive mechanism is introduced into the proposed algorithm to enhance the exploitation ability. The performance of the proposed algorithm is evaluated by instances with comparison to other multi-objective meta-heuristics such as Nondominated Sorting Genetic Algorithm II (NSGA-II, Strength Pareto Evolutionary Algorithm 2 (SPEA2, Multiobjective Particle Swarm Optimization (OMOPSO, and Multiobjective Evolutionary Algorithm Based on Decomposition (MOEA/D. Experimental results demonstrate that the proposed LMOEA algorithm outperforms its counterparts for this kind of scheduling problems.

Technical Report: Optimizing the Slab Yard Planning and Crane Scheduling Problem using a Two-Stage Approach

DEFF Research Database (Denmark)

Hansen, Anders Dohn; Clausen, Jens

2008-01-01

In this paper, we present The Slab Yard Planning and Crane Scheduling Problem. The problem has its origin in steel production facilities with a large throughput. A slab yard is used as a buffer for slabs that are needed in the upcoming production. Slabs are transported by cranes and the problem...... considered here, is concerned with the generation of schedules for these. The problem is decomposed and modeled in two parts, namely a planning problem and a scheduling problem. In the planning problem a set of crane operations is created to take the yard from its current state to a desired goal state...... schedule for the cranes is generated, where each operation is assigned to a crane and is given a specific time of initiation. For both models, a thorough description of the modeling details is given along with a specification of objective criteria. Variants of the models are presented as well. Preliminary...

MULTICRITERIA HYBRID FLOW SHOP SCHEDULING PROBLEM: LITERATURE REVIEW, ANALYSIS, AND FUTURE RESEARCH

Directory of Open Access Journals (Sweden)

Marcia de Fatima Morais

2014-12-01

Full Text Available This research focuses on the Hybrid Flow Shop production scheduling problem, which is one of the most difficult problems to solve. The literature points to several studies that focus the Hybrid Flow Shop scheduling problem with monocriteria functions. Despite of the fact that, many real world problems involve several objective functions, they can often compete and conflict, leading researchers to concentrate direct their efforts on the development of methods that take consider this variant into consideration. The goal of the study is to review and analyze the methods in order to solve the Hybrid Flow Shop production scheduling problem with multicriteria functions in the literature. The analyses were performed using several papers that have been published over the years, also the parallel machines types, the approach used to develop solution methods, the type of method develop, the objective function, the performance criterion adopted, and the additional constraints considered. The results of the reviewing and analysis of 46 papers showed opportunities for future research on this topic, including the following: (i use uniform and dedicated parallel machines, (ii use exact and metaheuristics approaches, (iv develop lower and uppers bounds, relations of dominance and different search strategies to improve the computational time of the exact methods,  (v develop  other types of metaheuristic, (vi work with anticipatory setups, and (vii add constraints faced by the production systems itself.

The role of the production scheduling system in rescheduling

Science.gov (United States)

Kalinowski, K.; Grabowik, C.; Kempa, W.; Paprocka, I.

2015-11-01

The paper presents the rescheduling problem in the context of cooperation between production scheduling system (PSS) and other units in an integrated manufacturing environment - decision makers and software systems. The main aim is to discuss the PSS functionality for maximizing automation of the rescheduling process, reducing the response time and improving the quality of generated solutions. PSSs operate in the meeting of tactical and operational level of planning and control, and play an important role in the production preparation and control. On the basis of information about orders, technology and production system state (e.g. resources availability) they prepare and/or update a detailed plan of production flow - a schedule. All necessary data for scheduling and rescheduling are usually collected in other systems both from organizational and technical production preparation, e.g. ERP, PLM, MES, CAPP or others, as well as they are entered directly by the decision- makers/operators. Data acquired in this way are often incomplete and inconsistent. Therefore the existing rescheduling software works according to interactive method - rather support but does not replace the human decision maker in tasks planning. When rescheduling, due to the limited amount of time to make a decision this interaction is particularly important. An additional problem arises in data acquisition, in the process of data exchanging between systems or in the identification of new data sources and their processing. Different approaches to rescheduling were characterized, including those solutions, where all these operations are carried out by an autonomous system and those in which scheduling is performed only upon request from the outside, for the newly created scheduling data representing the current state of the production system.

Unit-time scheduling problems with time dependent resources

NARCIS (Netherlands)

Tautenhahn, T.; Woeginger, G.

1997-01-01

We investigate the computational complexity of scheduling problems, where the operations consume certain amounts of renewable resources which are available in time-dependent quantities. In particular, we consider unit-time open shop problems and unit-time scheduling problems with identical parallel

A new mathematical programming model for long-term production scheduling considering geological uncertainty

OpenAIRE

Gholamnejad, J.; Moosavi, E.

2012-01-01

Determination of the optimum production schedules over the life of a mine is a critical mechanism in open pit mine planning procedures. Long-term production scheduling is used to maximize the net present value of the project under technical, financial, and environmental constraints. Mathematical programming models are well suited for optimizing long-term production schedules of open pit mines. There are two approaches to solving long-term production problems: deterministic- and uncertainty- b...

Problem specific heuristics for group scheduling problems in cellular manufacturing

OpenAIRE

Neufeld, Janis Sebastian

2016-01-01

The group scheduling problem commonly arises in cellular manufacturing systems, where parts are grouped into part families. It is characterized by a sequencing task on two levels: on the one hand, a sequence of jobs within each part family has to be identified while, on the other hand, a family sequence has to be determined. In order to solve this NP-hard problem usually heuristic solution approaches are used. In this thesis different aspects of group scheduling are discussed and problem spec...

Optimising the Slab Yard Planning and Crane Scheduling Problem using a two-stage heuristic

DEFF Research Database (Denmark)

Hansen, Anders Dohn; Clausen, Jens

2010-01-01

In this paper, we present the Slab Yard Planning and Crane Scheduling Problem. The problem has its origin in steel production facilities with a large throughput. A slab yard is used as a buffer for slabs that are needed in the upcoming production. Slabs are transported by cranes and the problem...

Decision Model for Planning and Scheduling of Seafood Product Considering Traceability

Science.gov (United States)

Agustin; Mawengkang, Herman; Mathelinea, Devy

2018-01-01

Due to the global challenges, it is necessary for an industrial company to integrate production scheduling and distribution planning, in order to be more efficient and to get more economics advantages. This paper presents seafood production planning and scheduling of a seafood manufacture company which produces simultaneously multi kind of seafood products, located at Aceh Province, Indonesia. The perishability nature of fish highly restricts its storage duration and delivery conditions. Traceability is a tracking requirement to check whether the quality of the product is satisfied. The production and distribution planning problem aims to meet customer demand subject to traceability of the seafood product and other restrictions. The problem is modeled as a mixed integer linear program, and then it is solved using neighborhood search approach.

Simulation of less master production schedule nervousness model

OpenAIRE

Herrera , Carlos; Thomas , André

2009-01-01

International audience; In production decision making systems, Master Production Schedule (MPS) states the requirements for individual end items by date and quantity. The solution sensitivity to demand forecast changes, unforeseen supplier and production problem occurrences, is known as nervousness. This feature cause undesirable effects at tactical and operational levels. Some of these effects are production and inventory cost increases and, also, negative impacts on overall and labor produc...

Energy-efficient approach to minimizing the energy consumption in an extended job-shop scheduling problem

Science.gov (United States)

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.

Sharing Data for Production Scheduling Using the ISA-95 Standard

Energy Technology Data Exchange (ETDEWEB)

Harjunkoski, Iiro, E-mail: iiro.harjunkoski@de.abb.com; Bauer, Reinhard [ABB Corporate Research, Industrial Software and Applications, Ladenburg (Germany)

2014-10-21

In the development and deployment of production scheduling solutions, one major challenge is to establish efficient information sharing with industrial production management systems. Information comprising production orders to be scheduled, processing plant structure, product recipes, available equipment, and other resources are necessary for producing a realistic short-term production plan. Currently, a widely accepted standard for information sharing is missing. This often leads to the implementation of costly custom-tailored interfaces, or in the worst case the scheduling solution will be abandoned. Additionally, it becomes difficult to easily compare different methods on various problem instances, which complicates the re-use of existing scheduling solutions. In order to overcome these hurdles, a platform-independent and holistic approach is needed. Nevertheless, it is difficult for any new solution to gain wide acceptance within industry as new standards are often refused by companies already using a different established interface. From an acceptance point of view, the ISA-95 standard could act as a neutral data-exchange platform. In this paper, we assess if this already widespread standard is simple, yet powerful enough to act as the desired holistic data exchange for scheduling solutions.

Sharing Data for Production Scheduling Using the ISA-95 Standard

International Nuclear Information System (INIS)

Harjunkoski, Iiro; Bauer, Reinhard

2014-01-01

In the development and deployment of production scheduling solutions, one major challenge is to establish efficient information sharing with industrial production management systems. Information comprising production orders to be scheduled, processing plant structure, product recipes, available equipment, and other resources are necessary for producing a realistic short-term production plan. Currently, a widely accepted standard for information sharing is missing. This often leads to the implementation of costly custom-tailored interfaces, or in the worst case the scheduling solution will be abandoned. Additionally, it becomes difficult to easily compare different methods on various problem instances, which complicates the re-use of existing scheduling solutions. In order to overcome these hurdles, a platform-independent and holistic approach is needed. Nevertheless, it is difficult for any new solution to gain wide acceptance within industry as new standards are often refused by companies already using a different established interface. From an acceptance point of view, the ISA-95 standard could act as a neutral data-exchange platform. In this paper, we assess if this already widespread standard is simple, yet powerful enough to act as the desired holistic data exchange for scheduling solutions.

Sharing data for production scheduling using the ISA-95 standard

Directory of Open Access Journals (Sweden)

Iiro eHarjunkoski

2014-10-01

Full Text Available In the development and deployment of production scheduling solutions one major challenge is to establish efficient information sharing with industrial production management systems. Information comprising production orders to be scheduled, processing plant structure, product recipes, available equipment and other resources are necessary for producing a realistic short-term production plan. Currently, a widely-accepted standard for information sharing is missing. This often leads to the implementation of costly custom-tailored interfaces, or in the worst case the scheduling solution will be abandoned. Additionally, it becomes difficult to easily compare different methods on various problem instances, which complicates the re-use of existing scheduling solutions. In order to overcome these hurdles, a platform-independent and holistic approach is needed. Nevertheless, it is difficult for any new solution to gain wide acceptance within industry as new standards are often refused by companies already using a different established interface. From an acceptance point of view, the ISA-95 standard could act as a neutral data-exchange platform. In this paper, we assess if this already widespread standard is simple, yet powerful enough to act as the desired holistic data-exchange for scheduling solutions.

The comparison of predictive scheduling algorithms for different sizes of job shop scheduling problems

Science.gov (United States)

Paprocka, I.; Kempa, W. M.; Grabowik, C.; Kalinowski, K.; Krenczyk, D.

2016-08-01

In the paper a survey of predictive and reactive scheduling methods is done in order to evaluate how the ability of prediction of reliability characteristics influences over robustness criteria. The most important reliability characteristics are: Mean Time to Failure, Mean Time of Repair. Survey analysis is done for a job shop scheduling problem. The paper answers the question: what method generates robust schedules in the case of a bottleneck failure occurrence before, at the beginning of planned maintenance actions or after planned maintenance actions? Efficiency of predictive schedules is evaluated using criteria: makespan, total tardiness, flow time, idle time. Efficiency of reactive schedules is evaluated using: solution robustness criterion and quality robustness criterion. This paper is the continuation of the research conducted in the paper [1], where the survey of predictive and reactive scheduling methods is done only for small size scheduling problems.

Multi-objective problem of the modified distributed parallel machine and assembly scheduling problem (MDPMASP) with eligibility constraints

Science.gov (United States)

Amallynda, I.; Santosa, B.

2017-11-01

This paper proposes a new generalization of the distributed parallel machine and assembly scheduling problem (DPMASP) with eligibility constraints referred to as the modified distributed parallel machine and assembly scheduling problem (MDPMASP) with eligibility constraints. Within this generalization, we assume that there are a set non-identical factories or production lines, each one with a set unrelated parallel machine with different speeds in processing them disposed to a single assembly machine in series. A set of different products that are manufactured through an assembly program of a set of components (jobs) according to the requested demand. Each product requires several kinds of jobs with different sizes. Beside that we also consider to the multi-objective problem (MOP) of minimizing mean flow time and the number of tardy products simultaneously. This is known to be NP-Hard problem, is important to practice, as the former criterions to reflect the customer's demand and manufacturer's perspective. This is a realistic and complex problem with wide range of possible solutions, we propose four simple heuristics and two metaheuristics to solve it. Various parameters of the proposed metaheuristic algorithms are discussed and calibrated by means of Taguchi technique. All proposed algorithms are tested by Matlab software. Our computational experiments indicate that the proposed problem and fourth proposed algorithms are able to be implemented and can be used to solve moderately-sized instances, and giving efficient solutions, which are close to optimum in most cases.

Distributing Flexibility to Enhance Robustness in Task Scheduling Problems

NARCIS (Netherlands)

Wilmer, D.; Klos, T.B.; Wilson, M.

2013-01-01

Temporal scheduling problems occur naturally in many diverse application domains such as manufacturing, transportation, health and education. A scheduling problem arises if we have a set of temporal events (or variables) and some constraints on those events, and we have to find a schedule, which is

A meta-heuristic method for solving scheduling problem: crow search algorithm

Science.gov (United States)

Adhi, Antono; Santosa, Budi; Siswanto, Nurhadi

2018-04-01

Scheduling is one of the most important processes in an industry both in manufacturingand services. The scheduling process is the process of selecting resources to perform an operation on tasks. Resources can be machines, peoples, tasks, jobs or operations.. The selection of optimum sequence of jobs from a permutation is an essential issue in every research in scheduling problem. Optimum sequence becomes optimum solution to resolve scheduling problem. Scheduling problem becomes NP-hard problem since the number of job in the sequence is more than normal number can be processed by exact algorithm. In order to obtain optimum results, it needs a method with capability to solve complex scheduling problems in an acceptable time. Meta-heuristic is a method usually used to solve scheduling problem. The recently published method called Crow Search Algorithm (CSA) is adopted in this research to solve scheduling problem. CSA is an evolutionary meta-heuristic method which is based on the behavior in flocks of crow. The calculation result of CSA for solving scheduling problem is compared with other algorithms. From the comparison, it is found that CSA has better performance in term of optimum solution and time calculation than other algorithms.

Solving a chemical batch scheduling problem by local search

NARCIS (Netherlands)

Brucker, P.; Hurink, Johann L.

1999-01-01

A chemical batch scheduling problem is modelled in two different ways as a discrete optimization problem. Both models are used to solve the batch scheduling problem in a two-phase tabu search procedure. The method is tested on real-world data.

Flexible Job Shop Scheduling Problem Using an Improved Ant Colony Optimization

Directory of Open Access Journals (Sweden)

Lei Wang

2017-01-01

Full Text Available As an extension of the classical job shop scheduling problem, the flexible job shop scheduling problem (FJSP plays an important role in real production systems. In FJSP, an operation is allowed to be processed on more than one alternative machine. It has been proven to be a strongly NP-hard problem. Ant colony optimization (ACO has been proven to be an efficient approach for dealing with FJSP. However, the basic ACO has two main disadvantages including low computational efficiency and local optimum. In order to overcome these two disadvantages, an improved ant colony optimization (IACO is proposed to optimize the makespan for FJSP. The following aspects are done on our improved ant colony optimization algorithm: select machine rule problems, initialize uniform distributed mechanism for ants, change pheromone’s guiding mechanism, select node method, and update pheromone’s mechanism. An actual production instance and two sets of well-known benchmark instances are tested and comparisons with some other approaches verify the effectiveness of the proposed IACO. The results reveal that our proposed IACO can provide better solution in a reasonable computational time.

An Improved Genetic Algorithm for Single-Machine Inverse Scheduling Problem

Directory of Open Access Journals (Sweden)

Jianhui Mou

2014-01-01

Full Text Available The goal of the scheduling is to arrange operations on suitable machines with optimal sequence for corresponding objectives. In order to meet market requirements, scheduling systems must own enough flexibility against uncertain events. These events can change production status or processing parameters, even causing the original schedule to no longer be optimal or even to be infeasible. Traditional scheduling strategies, however, cannot cope with these cases. Therefore, a new idea of scheduling called inverse scheduling has been proposed. In this paper, the inverse scheduling with weighted completion time (SMISP is considered in a single-machine shop environment. In this paper, an improved genetic algorithm (IGA with a local searching strategy is proposed. To improve the performance of IGA, efficient encoding scheme, fitness evaluation mechanism, feasible initialization methods, and a local search procedure have been employed in the paper. Because of the local improving method, the proposed IGA can balance its exploration ability and exploitation ability. We adopt 27 instances to verify the effectiveness of the proposed algorithm. The experimental results illustrated that the proposed algorithm can generate satisfactory solutions. This approach also has been applied to solve the scheduling problem in the real Chinese shipyard and can bring some benefits.

Solving project scheduling problems by minimum cut computations

NARCIS (Netherlands)

Möhring, R.H.; Schulz, A.S.; Stork, F.; Uetz, Marc Jochen

In project scheduling, a set of precedence-constrained jobs has to be scheduled so as to minimize a given objective. In resource-constrained project scheduling, the jobs additionally compete for scarce resources. Due to its universality, the latter problem has a variety of applications in

Two parameter-tuned metaheuristic algorithms for the multi-level lot sizing and scheduling problem

Directory of Open Access Journals (Sweden)

S.M.T. Fatemi Ghomi

2012-10-01

Full Text Available This paper addresses the problem of lot sizing and scheduling problem for n-products and m-machines in flow shop environment where setups among machines are sequence-dependent and can be carried over. Many products must be produced under capacity constraints and allowing backorders. Since lot sizing and scheduling problems are well-known strongly NP-hard, much attention has been given to heuristics and metaheuristics methods. This paper presents two metaheuristics algorithms namely, Genetic Algorithm (GA and Imperialist Competitive Algorithm (ICA. Moreover, Taguchi robust design methodology is employed to calibrate the parameters of the algorithms for different size problems. In addition, the parameter-tuned algorithms are compared against a presented lower bound on randomly generated problems. At the end, comprehensive numerical examples are presented to demonstrate the effectiveness of the proposed algorithms. The results showed that the performance of both GA and ICA are very promising and ICA outperforms GA statistically.

The Vessel Schedule Recovery Problem

DEFF Research Database (Denmark)

Brouer, Berit Dangaard; Plum, Christian Edinger Munk; Vaaben, Bo

Maritime transportation is the backbone of world trade and is accountable for around 3% of the worlds CO2 emissions. We present the Vessel Schedule Recovery Problem (VSRP) to evaluate a given disruption scenario and to select a recovery action balancing the trade off between increased bunker cons...... consumption and the impact on the remaining network and the customer service level. The model is applied to 4 real cases from Maersk Line. Solutions are comparable or superior to those chosen by operations managers. Cost savings of up to 58% may be achieved.......Maritime transportation is the backbone of world trade and is accountable for around 3% of the worlds CO2 emissions. We present the Vessel Schedule Recovery Problem (VSRP) to evaluate a given disruption scenario and to select a recovery action balancing the trade off between increased bunker...

Integrating Preventive Maintenance Scheduling As Probability Machine Failure And Batch Production Scheduling

Directory of Open Access Journals (Sweden)

Zahedi Zahedi

2016-06-01

Full Text Available This paper discusses integrated model of batch production scheduling and machine maintenance scheduling. Batch production scheduling uses minimize total actual flow time criteria and machine maintenance scheduling uses the probability of machine failure based on Weibull distribution. The model assumed no nonconforming parts in a planning horizon. The model shows an increase in the number of the batch (length of production run up to a certain limit will minimize the total actual flow time. Meanwhile, an increase in the length of production run will implicate an increase in the number of PM. An example was given to show how the model and algorithm work.

Production and Resource Scheduling in Mass Customization with Dependent Setup Consideration

DEFF Research Database (Denmark)

Nielsen, Izabela Ewa; Bocewicz, G.; Do, Ngoc Anh Dung

2014-01-01

will contribute to the success of mass customization. This paper addresses the problem of production and resource scheduling for a production system with dependent setup and internal transportation such as AGVs in a mass customization environment. A constraint-programming-based methodology is developed to satisfy...

Global Optimization of Nonlinear Blend-Scheduling Problems

Directory of Open Access Journals (Sweden)

Pedro A. Castillo Castillo

2017-04-01

Full Text Available The scheduling of gasoline-blending operations is an important problem in the oil refining industry. This problem not only exhibits the combinatorial nature that is intrinsic to scheduling problems, but also non-convex nonlinear behavior, due to the blending of various materials with different quality properties. In this work, a global optimization algorithm is proposed to solve a previously published continuous-time mixed-integer nonlinear scheduling model for gasoline blending. The model includes blend recipe optimization, the distribution problem, and several important operational features and constraints. The algorithm employs piecewise McCormick relaxation (PMCR and normalized multiparametric disaggregation technique (NMDT to compute estimates of the global optimum. These techniques partition the domain of one of the variables in a bilinear term and generate convex relaxations for each partition. By increasing the number of partitions and reducing the domain of the variables, the algorithm is able to refine the estimates of the global solution. The algorithm is compared to two commercial global solvers and two heuristic methods by solving four examples from the literature. Results show that the proposed global optimization algorithm performs on par with commercial solvers but is not as fast as heuristic approaches.

A random-key encoded harmony search approach for energy-efficient production scheduling with shared resources

Science.gov (United States)

Garcia-Santiago, C. A.; Del Ser, J.; Upton, C.; Quilligan, F.; Gil-Lopez, S.; Salcedo-Sanz, S.

2015-11-01

When seeking near-optimal solutions for complex scheduling problems, meta-heuristics demonstrate good performance with affordable computational effort. This has resulted in a gravitation towards these approaches when researching industrial use-cases such as energy-efficient production planning. However, much of the previous research makes assumptions about softer constraints that affect planning strategies and about how human planners interact with the algorithm in a live production environment. This article describes a job-shop problem that focuses on minimizing energy consumption across a production facility of shared resources. The application scenario is based on real facilities made available by the Irish Center for Manufacturing Research. The formulated problem is tackled via harmony search heuristics with random keys encoding. Simulation results are compared to a genetic algorithm, a simulated annealing approach and a first-come-first-served scheduling. The superior performance obtained by the proposed scheduler paves the way towards its practical implementation over industrial production chains.

Cost Minimization for Joint Energy Management and Production Scheduling Using Particle Swarm Optimization

Science.gov (United States)

Shah, Rahul H.

Production costs account for the largest share of the overall cost of manufacturing facilities. With the U.S. industrial sector becoming more and more competitive, manufacturers are looking for more cost and resource efficient working practices. Operations management and production planning have shown their capability to dramatically reduce manufacturing costs and increase system robustness. When implementing operations related decision making and planning, two fields that have shown to be most effective are maintenance and energy. Unfortunately, the current research that integrates both is limited. Additionally, these studies fail to consider parameter domains and optimization on joint energy and maintenance driven production planning. Accordingly, production planning methodology that considers maintenance and energy is investigated. Two models are presented to achieve well-rounded operating strategy. The first is a joint energy and maintenance production scheduling model. The second is a cost per part model considering maintenance, energy, and production. The proposed methodology will involve a Time-of-Use electricity demand response program, buffer and holding capacity, station reliability, production rate, station rated power, and more. In practice, the scheduling problem can be used to determine a joint energy, maintenance, and production schedule. Meanwhile, the cost per part model can be used to: (1) test the sensitivity of the obtained optimal production schedule and its corresponding savings by varying key production system parameters; and (2) to determine optimal system parameter combinations when using the joint energy, maintenance, and production planning model. Additionally, a factor analysis on the system parameters is conducted and the corresponding performance of the production schedule under variable parameter conditions, is evaluated. Also, parameter optimization guidelines that incorporate maintenance and energy parameter decision making in the

A basic period approach to the economic lot scheduling problem with shelf life considerations

NARCIS (Netherlands)

Soman, C.A.; van Donk, D.P.; Gaalman, G.J.C.

2004-01-01

Almost all the research on the economic lot scheduling problem (ELSP) considering limited shelf life of products has assumed a common cycle approach and an unrealistic assumption of possibility of deliberately reducing the production rate. In many cases, like in food processing industry where

A Literature Survey for Earliness/Tardiness Scheduling Problems with Learning Effect

Directory of Open Access Journals (Sweden)

Mesut Cemil İŞLER

2009-02-01

Full Text Available When a task or work is done continuously, there will be an experience so following times needs of required resources (manpower, materials, etc. will be reduced. This learning curve described first by Wright. Wright determined how workmanship costs decreased while proceed plain increasing. This investigations correctness found consistent by plain producers. Learning effect is an effect that, works can be done in shorter time in the rate of repeat of work with repeating same or similar works in production process. Nowadays classical production systems adapted more acceptable systems with new approaches. Just in time production system (JIT philosophy is one of the most important production system philosophies. JIT which is known production without stock stands on using all product resources optimum. Minimization problem of Earliness/Tardiness finishing penalty, which we can describe Just in time scheduling, appeared by inspired from JIT philosophy. In this study, there is literature survey which directed to earliness/tardiness performance criteria and learning effect processing in scheduling and as a result of this it is obtained some establishing for literature.

Approximating multi-objective scheduling problems

NARCIS (Netherlands)

Dabia, S.; Talbi, El-Ghazali; Woensel, van T.; Kok, de A.G.

2013-01-01

In many practical situations, decisions are multi-objective by nature. In this paper, we propose a generic approach to deal with multi-objective scheduling problems (MOSPs). The aim is to determine the set of Pareto solutions that represent the interactions between the different objectives. Due to

Discrete harmony search algorithm for scheduling and rescheduling the reprocessing problems in remanufacturing: a case study

Science.gov (United States)

Gao, Kaizhou; Wang, Ling; Luo, Jianping; Jiang, Hua; Sadollah, Ali; Pan, Quanke

2018-06-01

In this article, scheduling and rescheduling problems with increasing processing time and new job insertion are studied for reprocessing problems in the remanufacturing process. To handle the unpredictability of reprocessing time, an experience-based strategy is used. Rescheduling strategies are applied for considering the effect of increasing reprocessing time and the new subassembly insertion. To optimize the scheduling and rescheduling objective, a discrete harmony search (DHS) algorithm is proposed. To speed up the convergence rate, a local search method is designed. The DHS is applied to two real-life cases for minimizing the maximum completion time and the mean of earliness and tardiness (E/T). These two objectives are also considered together as a bi-objective problem. Computational optimization results and comparisons show that the proposed DHS is able to solve the scheduling and rescheduling problems effectively and productively. Using the proposed approach, satisfactory optimization results can be achieved for scheduling and rescheduling on a real-life shop floor.

A review on application of neural networks and fuzzy logic to solve hydrothermal scheduling problem

International Nuclear Information System (INIS)

Haroon, S.; Malik, T.N.; Zafar, S.

2014-01-01

Electrical power system is highly complicated having hydro and thermal mix with large number of machines. To reduce power production cost, hydro and thermal resources are mixed. Hydrothermal scheduling is the optimal coordination of hydro and thermal plants to meet the system load demand at minimum possible operational cost while satisfying the system constraints. Hydrothermal scheduling is dynamic, large scale, non-linear and non-convex optimization problem. The classical techniques have failed in solving such problem. Artificial Intelligence Tools based techniques are used now a day to solve this complex optimization problem because of their no requirements on the nature of the problem. The aim of this research paper is to provide a comprehensive survey of literature related to both Artificial Neural Network (ANN) and Fuzzy Logic (FL) as effective optimization algorithms for the hydrothermal scheduling problem. The outcomes along with the merits and demerits of individual techniques are also discussed. (author)

Performance comparison of some evolutionary algorithms on job shop scheduling problems

Science.gov (United States)

Mishra, S. K.; Rao, C. S. P.

2016-09-01

Job Shop Scheduling as a state space search problem belonging to NP-hard category due to its complexity and combinational explosion of states. Several naturally inspire evolutionary methods have been developed to solve Job Shop Scheduling Problems. In this paper the evolutionary methods namely Particles Swarm Optimization, Artificial Intelligence, Invasive Weed Optimization, Bacterial Foraging Optimization, Music Based Harmony Search Algorithms are applied and find tuned to model and solve Job Shop Scheduling Problems. To compare about 250 Bench Mark instances have been used to evaluate the performance of these algorithms. The capabilities of each these algorithms in solving Job Shop Scheduling Problems are outlined.

Multi-Agent Based Beam Search for Real-Time Production Scheduling and Control Method, Software and Industrial Application

CERN Document Server

Kang, Shu Gang

2013-01-01

The Multi-Agent Based Beam Search (MABBS) method systematically integrates four major requirements of manufacturing production - representation capability, solution quality, computation efficiency, and implementation difficulty - within a unified framework to deal with the many challenges of complex real-world production planning and scheduling problems. Multi-agent Based Beam Search for Real-time Production Scheduling and Control introduces this method, together with its software implementation and industrial applications.  This book connects academic research with industrial practice, and develops a practical solution to production planning and scheduling problems. To simplify implementation, a reusable software platform is developed to build the MABBS method into a generic computation engine.  This engine is integrated with a script language, called the Embedded Extensible Application Script Language (EXASL), to provide a flexible and straightforward approach to representing complex real-world problems. ...

Genetic algorithm parameters tuning for resource-constrained project scheduling problem

Science.gov (United States)

Tian, Xingke; Yuan, Shengrui

2018-04-01

Project Scheduling Problem (RCPSP) is a kind of important scheduling problem. To achieve a certain optimal goal such as the shortest duration, the smallest cost, the resource balance and so on, it is required to arrange the start and finish of all tasks under the condition of satisfying project timing constraints and resource constraints. In theory, the problem belongs to the NP-hard problem, and the model is abundant. Many combinatorial optimization problems are special cases of RCPSP, such as job shop scheduling, flow shop scheduling and so on. At present, the genetic algorithm (GA) has been used to deal with the classical RCPSP problem and achieved remarkable results. Vast scholars have also studied the improved genetic algorithm for the RCPSP problem, which makes it to solve the RCPSP problem more efficiently and accurately. However, for the selection of the main parameters of the genetic algorithm, there is no parameter optimization in these studies. Generally, we used the empirical method, but it cannot ensure to meet the optimal parameters. In this paper, the problem was carried out, which is the blind selection of parameters in the process of solving the RCPSP problem. We made sampling analysis, the establishment of proxy model and ultimately solved the optimal parameters.

SOLVING FLOWSHOP SCHEDULING PROBLEMS USING A DISCRETE AFRICAN WILD DOG ALGORITHM

Directory of Open Access Journals (Sweden)

M. K. Marichelvam

2013-04-01

Full Text Available The problem of m-machine permutation flowshop scheduling is considered in this paper. The objective is to minimize the makespan. The flowshop scheduling problem is a typical combinatorial optimization problem and has been proved to be strongly NP-hard. Hence, several heuristics and meta-heuristics were addressed by the researchers. In this paper, a discrete African wild dog algorithm is applied for solving the flowshop scheduling problems. Computational results using benchmark problems show that the proposed algorithm outperforms many other algorithms addressed in the literature.

Dynamic Scheduling for Cloud Reliability using Transportation Problem

OpenAIRE

P. Balasubramanie; S. K. Senthil Kumar

2012-01-01

Problem statement: Cloud is purely a dynamic environment and the existing task scheduling algorithms are mostly static and considered various parameters like time, cost, make span, speed, scalability, throughput, resource utilization, scheduling success rate and so on. Available scheduling algorithms are mostly heuristic in nature and more complex, time consuming and does not consider reliability and availability of the cloud computing environment. Therefore there is a need to implement a sch...

A decomposition heuristics based on multi-bottleneck machines for large-scale job shop scheduling problems

Directory of Open Access Journals (Sweden)

Yingni Zhai

2014-10-01

Full Text Available Purpose: A decomposition heuristics based on multi-bottleneck machines for large-scale job shop scheduling problems (JSP is proposed.Design/methodology/approach: In the algorithm, a number of sub-problems are constructed by iteratively decomposing the large-scale JSP according to the process route of each job. And then the solution of the large-scale JSP can be obtained by iteratively solving the sub-problems. In order to improve the sub-problems' solving efficiency and the solution quality, a detection method for multi-bottleneck machines based on critical path is proposed. Therewith the unscheduled operations can be decomposed into bottleneck operations and non-bottleneck operations. According to the principle of “Bottleneck leads the performance of the whole manufacturing system” in TOC (Theory Of Constraints, the bottleneck operations are scheduled by genetic algorithm for high solution quality, and the non-bottleneck operations are scheduled by dispatching rules for the improvement of the solving efficiency.Findings: In the process of the sub-problems' construction, partial operations in the previous scheduled sub-problem are divided into the successive sub-problem for re-optimization. This strategy can improve the solution quality of the algorithm. In the process of solving the sub-problems, the strategy that evaluating the chromosome's fitness by predicting the global scheduling objective value can improve the solution quality.Research limitations/implications: In this research, there are some assumptions which reduce the complexity of the large-scale scheduling problem. They are as follows: The processing route of each job is predetermined, and the processing time of each operation is fixed. There is no machine breakdown, and no preemption of the operations is allowed. The assumptions should be considered if the algorithm is used in the actual job shop.Originality/value: The research provides an efficient scheduling method for the

Simulation methods for nuclear production scheduling

International Nuclear Information System (INIS)

Miles, W.T.; Markel, L.C.

1975-01-01

Recent developments and applications of simulation methods for use in nuclear production scheduling and fuel management are reviewed. The unique characteristics of the nuclear fuel cycle as they relate to the overall optimization of a mixed nuclear-fossil system in both the short-and mid-range time frame are described. Emphasis is placed on the various formulations and approaches to the mid-range planning problem, whose objective is the determination of an optimal (least cost) system operation strategy over a multi-year planning horizon. The decomposition of the mid-range problem into power system simulation, reactor core simulation and nuclear fuel management optimization, and system integration models is discussed. Present utility practices, requirements, and research trends are described. 37 references

Analyzing scheduling in the food-processing industry

DEFF Research Database (Denmark)

Akkerman, Renzo; van Donk, Dirk Pieter

2009-01-01

Production scheduling has been widely studied in several research areas, resulting in a large number of methods, prescriptions, and approaches. However, the impact on scheduling practice seems relatively low. This is also the case in the food-processing industry, where industry......-specific characteristics induce specific and complex scheduling problems. Based on ideas about decomposition of the scheduling task and the production process, we develop an analysis methodology for scheduling problems in food processing. This combines an analysis of structural (technological) elements of the production...... process with an analysis of the tasks of the scheduler. This helps to understand, describe, and structure scheduling problems in food processing, and forms a basis for improving scheduling and applying methods developed in literature. It also helps in evaluating the organisational structures...

Preventive Maintenance Scheduling for Multicogeneration Plants with Production Constraints Using Genetic Algorithms

Directory of Open Access Journals (Sweden)

Khaled Alhamad

2015-01-01

Full Text Available This paper describes a method developed to schedule the preventive maintenance tasks of the generation and desalination units in separate and linked cogeneration plants provided that all the necessary maintenance and production constraints are satisfied. The proposed methodology is used to generate two preventing maintenance schedules, one for electricity and the other for distiller. Two types of crossover operators were adopted, 2-point and 4-point. The objective function of the model is to maximize the available number of operational units in each plant. The results obtained were satisfying the problem parameters. However, 4-point slightly produce better solution than 2-point ones for both electricity and water distiller. The performance as well as the effectiveness of the genetic algorithm in solving preventive maintenance scheduling is applied and tested on a real system of 21 units for electricity and 21 units for water. The results presented here show a great potential for utility applications for effective energy management over a time horizon of 52 weeks. The model presented is an effective decision tool that optimizes the solution of the maintenance scheduling problem for cogeneration plants under maintenance and production constraints.

A Hybrid Metaheuristic Approach for Minimizing the Total Flow Time in A Flow Shop Sequence Dependent Group Scheduling Problem

Directory of Open Access Journals (Sweden)

Antonio Costa

2014-07-01

Full Text Available Production processes in Cellular Manufacturing Systems (CMS often involve groups of parts sharing the same technological requirements in terms of tooling and setup. The issue of scheduling such parts through a flow-shop production layout is known as the Flow-Shop Group Scheduling (FSGS problem or, whether setup times are sequence-dependent, the Flow-Shop Sequence-Dependent Group Scheduling (FSDGS problem. This paper addresses the FSDGS issue, proposing a hybrid metaheuristic procedure integrating features from Genetic Algorithms (GAs and Biased Random Sampling (BRS search techniques with the aim of minimizing the total flow time, i.e., the sum of completion times of all jobs. A well-known benchmark of test cases, entailing problems with two, three, and six machines, is employed for both tuning the relevant parameters of the developed procedure and assessing its performances against two metaheuristic algorithms recently presented by literature. The obtained results and a properly arranged ANOVA analysis highlight the superiority of the proposed approach in tackling the scheduling problem under investigation.

Refinery production planning and scheduling: the refining core business

Directory of Open Access Journals (Sweden)

M. Joly

2012-06-01

Full Text Available Intelligent production planning and scheduling are of paramount importance to ensure refinery profitability, logistic reliability and safety at the local and corporate levels. In Brazil, such activities play a particularly critical role, since the Brazilian downstream model is moving towards a demand-driven model rather than a supply-driven one. Moreover, new and specialized non-linear constraints are continuously being incorporated into these large-scale problems: increases in oil prices implying the need for processing poor quality crudes, increasing demand and new demand patterns for petroleum products, new stringent environmental regulations related to clean fuels and start-up of new production technologies embedded into more complex refining schemes. This paper aims at clarifying the central role of refinery planning and scheduling activities in the Petrobras refining business. Major past and present results are outlined and corporate long-term strategies to deal with present and future challenges are presented.

A branch and cut approach to the multiproduct pipeline scheduling problem

Energy Technology Data Exchange (ETDEWEB)

Souza Filho, Erito Marques de; Bahiense, Laura; Ferreira Filho, Virgilio Jose Martins [Universidade Federal do Rio de Janeiro (UFRJ), RJ (Brazil)

2009-07-01

Pipelines are known as the most reliable and economical mode of transportation for petroleum and its derivatives, especially when large amounts of products have to be pumped for large distances. We address the short-term schedule of a pipeline system comprising the distribution of several petroleum derivatives from a single oil refinery to several depots, connected to local consumer markets, through a single multi-product pipeline. The major difficulties faced in these operations are related to the satisfaction of product demands by the various consumer markets, and operational constraints such as the maximum sizes of contiguous pumping packs, and the immiscible products. Several researchers have developed models and techniques for this short-term pipeline scheduling problem. Two different methodologies have been proposed in the literature: heuristic search techniques and exact methods. In this paper, we use a branch-and cut algorithm, performed in Xpress-MP{sup T}M, and compare the solutions obtained with that ones obtained before using the Variable Neighborhood Search metaheuristic. The computational results showed a significant improvement of performance in relation to previous algorithm. (author)

Periodic Heterogeneous Vehicle Routing Problem With Driver Scheduling

Science.gov (United States)

Mardiana Panggabean, Ellis; Mawengkang, Herman; Azis, Zainal; Filia Sari, Rina

2018-01-01

The paper develops a model for the optimal management of logistic delivery of a given commodity. The company has different type of vehicles with different capacity to deliver the commodity for customers. The problem is then called Periodic Heterogeneous Vehicle Routing Problem (PHVRP). The goal is to schedule the deliveries according to feasible combinations of delivery days and to determine the scheduling of fleet and driver and routing policies of the vehicles. The objective is to minimize the sum of the costs of all routes over the planning horizon. We propose a combined approach of heuristic algorithm and exact method to solve the problem.

The application of artificial intelligence to astronomical scheduling problems

Science.gov (United States)

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

A novel integrated condition-based maintenance and stochastic flexible job shop scheduling problem

DEFF Research Database (Denmark)

Rahmati, Seyed Habib A.; Ahmadi, Abbas; Govindan, Kannan

2018-01-01

the level of the system optimization. By means of this equipment, managers can benefit from a condition-based maintenance (CBM) for monitoring and managing their system. The chief aim of the paper is to develop a stochastic maintenance problem based on CBM activities engaged with a complex applied......Integrated consideration of production planning and maintenance processes is a real world assumption. Specifically, by improving the monitoring equipment such as various sensors or product-embedded information devices in recent years, joint assessment of these processes is inevitable for enhancing...... production problem called flexible job shop scheduling problem (FJSP). This integrated problem considers two maintenance scenarios in terms of corrective maintenance (CM) and preventive maintenance (PM). The activation of scenario is done by monitoring the degradation condition of the system and comparing...

The Simultaneous Vehicle Scheduling and Passenger Service Problem

DEFF Research Database (Denmark)

Petersen, Hanne Løhmann; Larsen, Allan; Madsen, Oli B.G.

2013-01-01

, by modifying the timetable. The planning approach is referred to as the simultaneous vehicle scheduling and passenger service problem (SVSPSP). The SVSPSP is modelled as an integer programming problem and solved using a large neighborhood search metaheuristic. The proposed framework is tested on data inspired......Passengers using public transport systems often experience waiting times when transferring between two scheduled services. In this paper we propose a planning approach that seeks to obtain a favourable trade-off between the two contrasting objectives, passenger service and operating cost...

Optimizing the Steel Plate Storage Yard Crane Scheduling Problem Using a Two Stage Planning/Scheduling Approach

DEFF Research Database (Denmark)

Hansen, Anders Dohn; Clausen, Jens

This paper presents the Steel Plate Storage Yard Crane Scheduling Problem. The task is to generate a schedule for two gantry cranes sharing tracks. The schedule must comply with a number of constraints and at the same time be cost efficient. We propose some ideas for a two stage planning...

A review of scheduling problem and resolution methods in flexible flow shop

Directory of Open Access Journals (Sweden)

Tian-Soon Lee

2019-01-01

Full Text Available The Flexible flow shop (FFS is defined as a multi-stage flow shops with multiple parallel machines. FFS scheduling problem is a complex combinatorial problem which has been intensively studied in many real world industries. This review paper gives a comprehensive exploration review on the FFS scheduling problem and guides the reader by considering and understanding different environmental assumptions, system constraints and objective functions for future research works. The published papers are classified into two categories. First is the FFS system characteristics and constraints including the problem differences and limitation defined by different studies. Second, the scheduling performances evaluation are elaborated and categorized into time, job and multi related objectives. In addition, the resolution approaches that have been used to solve FFS scheduling problems are discussed. This paper gives a comprehensive guide for the reader with respect to future research work on the FFS scheduling problem.

A modified genetic algorithm with fuzzy roulette wheel selection for job-shop scheduling problems

Science.gov (United States)

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.

Discrete Bat Algorithm for Optimal Problem of Permutation Flow Shop Scheduling

Science.gov (United States)

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

Discrete bat algorithm for optimal problem of permutation flow shop scheduling.

Science.gov (United States)

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.

Robust Parallel Machine Scheduling Problem with Uncertainties and Sequence-Dependent Setup Time

Directory of Open Access Journals (Sweden)

Hongtao Hu

2016-01-01

Full Text Available A parallel machine scheduling problem in plastic production is studied in this paper. In this problem, the processing time and arrival time are uncertain but lie in their respective intervals. In addition, each job must be processed together with a mold while jobs which belong to one family can share the same mold. Therefore, time changing mold is required for two consecutive jobs that belong to different families, which is known as sequence-dependent setup time. This paper aims to identify a robust schedule by min–max regret criterion. It is proved that the scenario incurring maximal regret for each feasible solution lies in finite extreme scenarios. A mixed integer linear programming formulation and an exact algorithm are proposed to solve the problem. Moreover, a modified artificial bee colony algorithm is developed to solve large-scale problems. The performance of the presented algorithm is evaluated through extensive computational experiments and the results show that the proposed algorithm surpasses the exact method in terms of objective value and computational time.

A DIFFERENTIAL EVOLUTION ALGORITHM DEVELOPED FOR A NURSE SCHEDULING PROBLEM

Directory of Open Access Journals (Sweden)

Shahnazari-Shahrezaei, P.

2012-11-01

Full Text Available Nurse scheduling is a type of manpower allocation problem that tries to satisfy hospital managers objectives and nurses preferences as much as possible by generating fair shift schedules. This paper presents a nurse scheduling problem based on a real case study, and proposes two meta-heuristics a differential evolution algorithm (DE and a greedy randomised adaptive search procedure (GRASP to solve it. To investigate the efficiency of the proposed algorithms, two problems are solved. Furthermore, some comparison metrics are applied to examine the reliability of the proposed algorithms. The computational results in this paper show that the proposed DE outperforms the GRASP.

The Liner Shipping Routing and Scheduling Problem Under Environmental Considerations

DEFF Research Database (Denmark)

Dithmer, Philip; Reinhardt, Line Blander; Kontovas, Christos

2017-01-01

This paper deals with the Liner Shipping Routing and Scheduling Problem (LSRSP), which consists of designing the time schedule for a vessel to visit a fixed set of ports while minimizing costs. We extend the classical problem to include the external cost of ship air emissions and we present some...

Increasing the reliability of production schedules in a pharmaceutical packaging department.

Science.gov (United States)

Pacciarelli, Dario; D'Ariano, Andrea

2012-12-01

This paper studies quantitative methods for evaluating the potential benefits of introducing new advanced tracking technologies in the pharmaceutical industry with special reference to radio frequency identification (RFID). RFID technology is an effective way for increasing the quality of the data that are used to generate production schedules, but there is a lack of scientific research to quantify the return on investment that can be achieved in practice. In this work, we distinguish two major sources of data unreliability: one is the inherent stochasticity of operations, which cannot be reduced by RFID, and the other one is the data estimation error, which can be significantly reduced by RFID. We focus on the marginal contribution of the latter quantity to the productivity of the packaging department of a pharmaceutical plant, propose a systematic method for assessing this impact and discuss its implementation in a practical test case. Our results confirm that advanced tracking technologies in combination with effective scheduling procedures show a significant potential for improving productivity. Extensions to other production environments and their issues associated with scheduling problems are also discussed.

Discrete particle swarm optimization to solve multi-objective limited-wait hybrid flow shop scheduling problem

Science.gov (United States)

Santosa, B.; Siswanto, N.; Fiqihesa

2018-04-01

This paper proposes a discrete Particle Swam Optimization (PSO) to solve limited-wait hybrid flowshop scheduing problem with multi objectives. Flow shop schedulimg represents the condition when several machines are arranged in series and each job must be processed at each machine with same sequence. The objective functions are minimizing completion time (makespan), total tardiness time, and total machine idle time. Flow shop scheduling model always grows to cope with the real production system accurately. Since flow shop scheduling is a NP-Hard problem then the most suitable method to solve is metaheuristics. One of metaheuristics algorithm is Particle Swarm Optimization (PSO), an algorithm which is based on the behavior of a swarm. Originally, PSO was intended to solve continuous optimization problems. Since flow shop scheduling is a discrete optimization problem, then, we need to modify PSO to fit the problem. The modification is done by using probability transition matrix mechanism. While to handle multi objectives problem, we use Pareto Optimal (MPSO). The results of MPSO is better than the PSO because the MPSO solution set produced higher probability to find the optimal solution. Besides the MPSO solution set is closer to the optimal solution

Step-by-step cyclic processes scheduling

DEFF Research Database (Denmark)

Bocewicz, G.; Nielsen, Izabela Ewa; Banaszak, Z.

2013-01-01

Automated Guided Vehicles (AGVs) fleet scheduling is one of the big problems in Flexible Manufacturing System (FMS) control. The problem is more complicated when concurrent multi-product manufacturing and resource deadlock avoidance policies are considered. The objective of the research is to pro......Automated Guided Vehicles (AGVs) fleet scheduling is one of the big problems in Flexible Manufacturing System (FMS) control. The problem is more complicated when concurrent multi-product manufacturing and resource deadlock avoidance policies are considered. The objective of the research...... is to provide a declarative model enabling to state a constraint satisfaction problem aimed at AGVs fleet scheduling subject to assumed itineraries of concurrently manufactured product types. In other words, assuming a given layout of FMS’s material handling and production routes of simultaneously manufactured...... orders, the main objective is to provide the declarative framework aimed at conditions allowing one to calculate the AGVs fleet schedule in online mode. An illustrative example of the relevant algebra-like driven step-by-stem cyclic scheduling is provided....

Diversity Controlling Genetic Algorithm for Order Acceptance and Scheduling Problem

Directory of Open Access Journals (Sweden)

Cheng Chen

2014-01-01

Full Text Available Selection and scheduling are an important topic in production systems. To tackle the order acceptance and scheduling problem on a single machine with release dates, tardiness penalty, and sequence-dependent setup times, in this paper a diversity controlling genetic algorithm (DCGA is proposed, in which a diversified population is maintained during the whole search process through survival selection considering both the fitness and the diversity of individuals. To measure the similarity between individuals, a modified Hamming distance without considering the unaccepted orders in the chromosome is adopted. The proposed DCGA was validated on 1500 benchmark instances with up to 100 orders. Compared with the state-of-the-art algorithms, the experimental results show that DCGA improves the solution quality obtained significantly, in terms of the deviation from upper bound.

The Simultaneous Vehicle Scheduling and Passenger Service Problem

DEFF Research Database (Denmark)

Petersen, Hanne Løhmann; Larsen, Allan; Madsen, Oli B.G.

modifications of the timetable during the vehicle scheduling phase. This planning approach is referred to as the Simultaneous Vehicle Scheduling and Passenger Service Problem (SVSPSP). The SVSPSP is solved using a large neighbourhood search metaheuristic. The proposed framework is tested on data inspired......Passengers using public transport systems often experience waiting times when transferring between two scheduled services. We propose a planning approach which seeks to obtain a favorable trade-off between the conflicting objectives passenger service and operating cost, by allowing some moderate...

Algorithms for classical and modern scheduling problems

OpenAIRE

Ott, Sebastian

2016-01-01

Subject of this thesis is the design and the analysis of algorithms for scheduling problems. In the first part, we focus on energy-efficient scheduling, where one seeks to minimize the energy needed for processing certain jobs via dynamic adjustments of the processing speed (speed scaling). We consider variations and extensions of the standard model introduced by Yao, Demers, and Shenker in 1995 [79], including the addition of a sleep state, the avoidance of preemption, and variable speed lim...

Integration of scheduling and discrete event simulation systems to improve production flow planning

Science.gov (United States)

Krenczyk, D.; Paprocka, I.; Kempa, W. M.; Grabowik, C.; Kalinowski, K.

2016-08-01

The increased availability of data and computer-aided technologies such as MRPI/II, ERP and MES system, allowing producers to be more adaptive to market dynamics and to improve production scheduling. Integration of production scheduling and computer modelling, simulation and visualization systems can be useful in the analysis of production system constraints related to the efficiency of manufacturing systems. A integration methodology based on semi-automatic model generation method for eliminating problems associated with complexity of the model and labour-intensive and time-consuming process of simulation model creation is proposed. Data mapping and data transformation techniques for the proposed method have been applied. This approach has been illustrated through examples of practical implementation of the proposed method using KbRS scheduling system and Enterprise Dynamics simulation system.

Producing Satisfactory Solutions to Scheduling Problems: An Iterative Constraint Relaxation Approach

Science.gov (United States)

Chien, S.; Gratch, J.

1994-01-01

One drawback to using constraint-propagation in planning and scheduling systems is that when a problem has an unsatisfiable set of constraints such algorithms typically only show that no solution exists. While, technically correct, in practical situations, it is desirable in these cases to produce a satisficing solution that satisfies the most important constraints (typically defined in terms of maximizing a utility function). This paper describes an iterative constraint relaxation approach in which the scheduler uses heuristics to progressively relax problem constraints until the problem becomes satisfiable. We present empirical results of applying these techniques to the problem of scheduling spacecraft communications for JPL/NASA antenna resources.

The operational flight and multi-crew scheduling problem

Directory of Open Access Journals (Sweden)

Stojković Mirela

2005-01-01

Full Text Available This paper introduces a new kind of operational multi-crew scheduling problem which consists in simultaneously modifying, as necessary, the existing flight departure times and planned individual work days (duties for the set of crew members, while respecting predefined aircraft itineraries. The splitting of a planned crew is allowed during a day of operations, where it is more important to cover a flight than to keep planned crew members together. The objective is to cover a maximum number of flights from a day of operations while minimizing changes in both the flight schedule and the next-day planned duties for the considered crew members. A new type of the same flight departure time constraints is introduced. They ensure that a flight which belongs to several personalized duties, where the number of duties is equal to the number of crew members assigned to the flight, will have the same departure time in each of these duties. Two variants of the problem are considered. The first variant allows covering of flights by less than the planned number of crew members, while the second one requires covering of flights by a complete crew. The problem is mathematically formulated as an integer nonlinear multi-commodity network flow model with time windows and supplementary constraints. The optimal solution approach is based on Dantzig-Wolfe decomposition/column generation embedded into a branch-and-bound scheme. The resulting computational times on commercial-size problems are very good. Our new simultaneous approach produces solutions whose quality is far better than that of the traditional sequential approach where the flight schedule has been changed first and then input as a fixed data to the crew scheduling problem.

Innovative Production Scheduling with Customer Satisfaction Based Measurement for the Sustainability of Manufacturing Firms

Directory of Open Access Journals (Sweden)

Sang-Oh Shim

2017-12-01

Full Text Available Scheduling problems for the sustainability of manufacturing firms in the era of the fourth industrial revolution is addressed in this research. In terms of open innovation, innovative production scheduling can be defined as scheduling using big data, cyber-physical systems, internet of things, cloud computing, mobile network, and so on. In this environment, one of the most important things is to develop an innovative scheduling algorithm for the sustainability of manufacturing firms. In this research, a flexible flowshop scheduling problem is considered with the properties of sequence-dependent setup and different process plans for jobs. In a flexible flowshop, there are serial workstations with multiple pieces of equipment that are able to process multiple lots simultaneously. Since the scheduling in this workshop is known to be extremely difficult, it is important to devise an efficient and effective scheduling algorithm. In this research, a heuristic algorithm is proposed based on a few dispatching rules and economic lot size model with the objective of minimizing total tardiness of orders. For the purposes of performance evaluation, a simulation study is conducted on randomly generated problem instances. The results imply that our proposed method outperforms the existing ones, and greatly enhances the sustainability of manufacturing firms.

Off-Line and Dynamic Production Scheduling – A Comparative Case Study

OpenAIRE

Bożek Andrzej; Wysocki Marian

2016-01-01

A comprehensive case study of manufacturing scheduling solutions development is given. It includes highly generalized scheduling problem as well as a few scheduling modes, methods and problem models. The considered problem combines flexible job shop structure, lot streaming with variable sublots, transport times, setup times, and machine calendars. Tabu search metaheuristic and constraint programming methods have been used for the off-line scheduling. Two dynamic scheduling methods have also ...

Modeling the Hybrid Flow Shop Scheduling Problem Followed by an Assembly Stage Considering Aging Effects and Preventive Maintenance Activities

Directory of Open Access Journals (Sweden)

Seyyed Mohammad Hassan Hosseini

2016-05-01

Full Text Available Scheduling problem for the hybrid flow shop scheduling problem (HFSP followed by an assembly stage considering aging effects additional preventive and maintenance activities is studied in this paper. In this production system, a number of products of different kinds are produced. Each product is assembled with a set of several parts. The first stage is a hybrid flow shop to produce parts. All machines can process all kinds of parts in this stage but each machine can process only one part at the same time. The second stage is a single assembly machine or a single assembly team of workers. The aim is to schedule the parts on the machines and assembly sequence and also determine when the preventive maintenance activities get done in order to minimize the completion time of all products (makespan. A mathematical modeling is presented and its validation is shown by solving an example in small scale. Since this problem has been proved strongly NP-hard, in order to solve the problem in medium and large scale, four heuristic algorithms is proposed based on the Johnson’s algorithm. The numerical experiments are used to run the mathematical model and evaluate the performance of the proposed algorithms.

JIT single machine scheduling problem with periodic preventive maintenance

Science.gov (United States)

Shahriari, Mohammadreza; Shoja, Naghi; Zade, Amir Ebrahimi; Barak, Sasan; Sharifi, Mani

2016-09-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.

Sustainable Scheduling of Cloth Production Processes by Multi-Objective Genetic Algorithm with Tabu-Enhanced Local Search

Directory of Open Access Journals (Sweden)

Rui Zhang

2017-09-01

Full Text Available The dyeing of textile materials is the most critical process in cloth production because of the strict technological requirements. In addition to the technical aspect, there have been increasing concerns over how to minimize the negative environmental impact of the dyeing industry. The emissions of pollutants are mainly caused by frequent cleaning operations which are necessary for initializing the dyeing equipment, as well as idled production capacity which leads to discharge of unconsumed chemicals. Motivated by these facts, we propose a methodology to reduce the pollutant emissions by means of systematic production scheduling. Firstly, we build a three-objective scheduling model that incorporates both the traditional tardiness objective and the environmentally-related objectives. A mixed-integer programming formulation is also provided to accurately define the problem. Then, we present a novel solution method for the sustainable scheduling problem, namely, a multi-objective genetic algorithm with tabu-enhanced iterated greedy local search strategy (MOGA-TIG. Finally, we conduct extensive computational experiments to investigate the actual performance of the MOGA-TIG. Based on a fair comparison with two state-of-the-art multi-objective optimizers, it is concluded that the MOGA-TIG is able to achieve satisfactory solution quality within tight computational time budget for the studied scheduling problem.

Research on Energy-Saving Production Scheduling Based on a Clustering Algorithm for a Forging Enterprise

Directory of Open Access Journals (Sweden)

Yifei Tong

2016-02-01

Full Text Available Energy efficiency is a buzzword of the 21st century. With the ever growing need for energy efficient and low-carbon production, it is a big challenge for high energy-consumption enterprises to reduce their energy consumption. To this aim, a forging enterprise, DVR (the abbreviation of a forging enterprise, is researched. Firstly, an investigation into the production processes of DVR is given as well as an analysis of forging production. Then, the energy-saving forging scheduling is decomposed into two sub-problems. One is for cutting and machining scheduling, which is similar to traditional machining scheduling. The other one is for forging and heat treatment scheduling. Thirdly, former forging production scheduling is presented and solved based on an improved genetic algorithm. Fourthly, the latter is discussed in detail, followed by proposed dynamic clustering and stacking combination optimization. The proposed stacking optimization requires making the gross weight of forgings as close to the maximum batch capacity as possible. The above research can help reduce the heating times, and increase furnace utilization with high energy efficiency and low carbon emissions.

Project scheduling with resources constraints: application in the equipment production for the oil industry; Scheduling de projetos com restricao de recursos: aplicacao na producao de equipamentos para a industria de petroleo

Energy Technology Data Exchange (ETDEWEB)

Cruz, Carolina A.O.; Ferreira Filho, Virgilio J.M. [Universidade Federal do Rio de Janeiro (UFRJ), Rio de Janeiro, RJ (Brazil). Coordenacao dos Programas de Pos-graduacao de Engenharia (COPPE)

2008-07-01

One of the essential steps in the main scope Project Management is the Time Management made by the planning and control of the project schedule. In this work is presented the resource constrained scheduling problem beyond its mathematical formulation and a review of papers about this issue. In sequence is presented a practical example of this model considering a simplified model of an engineering project schedule of oil production equipment. The results obtained with the model application are shown and the conclusions about the work with resource constrained scheduling problems. (author)

Off-Line and Dynamic Production Scheduling – A Comparative Case Study

Directory of Open Access Journals (Sweden)

Bożek Andrzej

2016-03-01

Full Text Available A comprehensive case study of manufacturing scheduling solutions development is given. It includes highly generalized scheduling problem as well as a few scheduling modes, methods and problem models. The considered problem combines flexible job shop structure, lot streaming with variable sublots, transport times, setup times, and machine calendars. Tabu search metaheuristic and constraint programming methods have been used for the off-line scheduling. Two dynamic scheduling methods have also been implemented, i.e., dispatching rules for the completely reactive scheduling and a multi-agent system for the predictivereactive scheduling. In these implementations three distinct models of the problem have been used, based on: graph representation, optimal constraint satisfaction, and Petri net formalism. Each of these solutions has been verified in computational experiments. The results are compared and some findings about advantages, disadvantages, and suggestions on using the solutions are formulated.

A Hybrid Genetic Algorithm with a Knowledge-Based Operator for Solving the Job Shop Scheduling Problems

Directory of Open Access Journals (Sweden)

Hamed Piroozfard

2016-01-01

Full Text Available Scheduling is considered as an important topic in production management and combinatorial optimization in which it ubiquitously exists in most of the real-world applications. The attempts of finding optimal or near optimal solutions for the job shop scheduling problems are deemed important, because they are characterized as highly complex and NP-hard problems. This paper describes the development of a hybrid genetic algorithm for solving the nonpreemptive job shop scheduling problems with the objective of minimizing makespan. In order to solve the presented problem more effectively, an operation-based representation was used to enable the construction of feasible schedules. In addition, a new knowledge-based operator was designed based on the problem’s characteristics in order to use machines’ idle times to improve the solution quality, and it was developed in the context of function evaluation. A machine based precedence preserving order-based crossover was proposed to generate the offspring. Furthermore, a simulated annealing based neighborhood search technique was used to improve the local exploitation ability of the algorithm and to increase its population diversity. In order to prove the efficiency and effectiveness of the proposed algorithm, numerous benchmarked instances were collected from the Operations Research Library. Computational results of the proposed hybrid genetic algorithm demonstrate its effectiveness.

The Home Care Crew Scheduling Problem:

DEFF Research Database (Denmark)

Rasmussen, Matias Sevel; Justesen, Tor; Dohn, Anders

In the Home Care Crew Scheduling Problem a staff of caretakers has to be assigned a number of visits to patients' homes, such that the overall service level is maximised. The problem is a generalisation of the vehicle routing problem with time windows. Required travel time between visits and time...... preference constraints. The algorithm is tested both on real-life problem instances and on generated test instances inspired by realistic settings. The use of the specialised branching scheme on real-life problems is novel. The visit clustering decreases run times significantly, and only gives a loss...... windows of the visits must be respected. The challenge when assigning visits to caretakers lies in the existence of soft preference constraints and in temporal dependencies between the start times of visits. We model the problem as a set partitioning problem with side constraints and develop an exact...

A novel modeling approach for job shop scheduling problem under uncertainty

Directory of Open Access Journals (Sweden)

Behnam Beheshti Pur

2013-11-01

Full Text Available When aiming on improving efficiency and reducing cost in manufacturing environments, production scheduling can play an important role. Although a common workshop is full of uncertainties, when using mathematical programs researchers have mainly focused on deterministic problems. After briefly reviewing and discussing popular modeling approaches in the field of stochastic programming, this paper proposes a new approach based on utility theory for a certain range of problems and under some practical assumptions. Expected utility programming, as the proposed approach, will be compared with the other well-known methods and its meaningfulness and usefulness will be illustrated via a numerical examples and a real case.

Algorithms for Scheduling and Network Problems

Science.gov (United States)

1991-09-01

time. We already know, by Lemma 2.2.1, that WOPT = O(log( mpU )), so if we could solve this integer program optimally we would be done. However, the...Folydirat, 15:177-191, 1982. [6] I.S. Belov and Ya. N. Stolin. An algorithm in a single path operations scheduling problem. In Mathematical Economics and

Permutation flow-shop scheduling problem to optimize a quadratic objective function

Science.gov (United States)

Ren, Tao; Zhao, Peng; Zhang, Da; Liu, Bingqian; Yuan, Huawei; Bai, Danyu

2017-09-01

A flow-shop scheduling model enables appropriate sequencing for each job and for processing on a set of machines in compliance with identical processing orders. The objective is to achieve a feasible schedule for optimizing a given criterion. Permutation is a special setting of the model in which the processing order of the jobs on the machines is identical for each subsequent step of processing. This article addresses the permutation flow-shop scheduling problem to minimize the criterion of total weighted quadratic completion time. With a probability hypothesis, the asymptotic optimality of the weighted shortest processing time schedule under a consistency condition (WSPT-CC) is proven for sufficiently large-scale problems. However, the worst case performance ratio of the WSPT-CC schedule is the square of the number of machines in certain situations. A discrete differential evolution algorithm, where a new crossover method with multiple-point insertion is used to improve the final outcome, is presented to obtain high-quality solutions for moderate-scale problems. A sequence-independent lower bound is designed for pruning in a branch-and-bound algorithm for small-scale problems. A set of random experiments demonstrates the performance of the lower bound and the effectiveness of the proposed algorithms.

New Mathematical Model and Algorithm for Economic Lot Scheduling Problem in Flexible Flow Shop

Directory of Open Access Journals (Sweden)

H. Zohali

2018-03-01

Full Text Available This paper addresses the lot sizing and scheduling problem for a number of products in flexible flow shop with identical parallel machines. The production stages are in series, while separated by finite intermediate buffers. The objective is to minimize the sum of setup and inventory holding costs per unit of time. The available mathematical model of this problem in the literature suffers from huge complexity in terms of size and computation. In this paper, a new mixed integer linear program is developed for delay with the huge dimentions of the problem. Also, a new meta heuristic algorithm is developed for the problem. The results of the numerical experiments represent a significant advantage of the proposed model and algorithm compared with the available models and algorithms in the literature.

Genetic algorithm to solve the problems of lectures and practicums scheduling

Science.gov (United States)

Syahputra, M. F.; Apriani, R.; Sawaluddin; Abdullah, D.; Albra, W.; Heikal, M.; Abdurrahman, A.; Khaddafi, M.

2018-02-01

Generally, the scheduling process is done manually. However, this method has a low accuracy level, along with possibilities that a scheduled process collides with another scheduled process. When doing theory class and practicum timetable scheduling process, there are numerous problems, such as lecturer teaching schedule collision, schedule collision with another schedule, practicum lesson schedules that collides with theory class, and the number of classrooms available. In this research, genetic algorithm is implemented to perform theory class and practicum timetable scheduling process. The algorithm will be used to process the data containing lists of lecturers, courses, and class rooms, obtained from information technology department at University of Sumatera Utara. The result of scheduling process using genetic algorithm is the most optimal timetable that conforms to available time slots, class rooms, courses, and lecturer schedules.

Hybrid Pareto artificial bee colony algorithm for multi-objective single machine group scheduling problem with sequence-dependent setup times and learning effects.

Science.gov (United States)

Yue, Lei; Guan, Zailin; Saif, Ullah; Zhang, Fei; Wang, Hao

2016-01-01

Group scheduling is significant for efficient and cost effective production system. However, there exist setup times between the groups, which require to decrease it by sequencing groups in an efficient way. Current research is focused on a sequence dependent group scheduling problem with an aim to minimize the makespan in addition to minimize the total weighted tardiness simultaneously. In most of the production scheduling problems, the processing time of jobs is assumed as fixed. However, the actual processing time of jobs may be reduced due to "learning effect". The integration of sequence dependent group scheduling problem with learning effects has been rarely considered in literature. Therefore, current research considers a single machine group scheduling problem with sequence dependent setup times and learning effects simultaneously. A novel hybrid Pareto artificial bee colony algorithm (HPABC) with some steps of genetic algorithm is proposed for current problem to get Pareto solutions. Furthermore, five different sizes of test problems (small, small medium, medium, large medium, large) are tested using proposed HPABC. Taguchi method is used to tune the effective parameters of the proposed HPABC for each problem category. The performance of HPABC is compared with three famous multi objective optimization algorithms, improved strength Pareto evolutionary algorithm (SPEA2), non-dominated sorting genetic algorithm II (NSGAII) and particle swarm optimization algorithm (PSO). Results indicate that HPABC outperforms SPEA2, NSGAII and PSO and gives better Pareto optimal solutions in terms of diversity and quality for almost all the instances of the different sizes of problems.

Flexible job shop scheduling problem in manufacturing

OpenAIRE

Curralo, Ana; Pereira, Ana I.; Barbosa, José; Leitão, Paulo

2013-01-01

This paper addresses a real assembly cell: the AIP-PRIMECA cell at the Université de Valenciennes et du Hainaut-Cambrésis, in France. This system can be viewed as a Flexible Job Shop, leading to the formulation of a Flexible Job Shop Scheduling Problem (FJSSP).

Resource-constrained project scheduling: computing lower bounds by solving minimum cut problems

NARCIS (Netherlands)

Möhring, R.H.; Nesetril, J.; Schulz, A.S.; Stork, F.; Uetz, Marc Jochen

1999-01-01

We present a novel approach to compute Lagrangian lower bounds on the objective function value of a wide class of resource-constrained project scheduling problems. The basis is a polynomial-time algorithm to solve the following scheduling problem: Given a set of activities with start-time dependent

Modeling of Agile Intelligent Manufacturing-oriented Production Scheduling System

Institute of Scientific and Technical Information of China (English)

Zhong-Qi Sheng; Chang-Ping Tang; Ci-Xing Lv

2010-01-01

Agile intelligent manufacturing is one of the new manufacturing paradigms that adapt to the fierce globalizing market competition and meet the survival needs of the enterprises, in which the management and control of the production system have surpassed the scope of individual enterprise and embodied some new features including complexity, dynamicity, distributivity, and compatibility. The agile intelligent manufacturing paradigm calls for a production scheduling system that can support the cooperation among various production sectors, the distribution of various resources to achieve rational organization, scheduling and management of production activities. This paper uses multi-agents technology to build an agile intelligent manufacturing-oriented production scheduling system. Using the hybrid modeling method, the resources and functions of production system are encapsulated, and the agent-based production system model is established. A production scheduling-oriented multi-agents architecture is constructed and a multi-agents reference model is given in this paper.

An Improved Multiobjective PSO for the Scheduling Problem of Panel Block Construction

Directory of Open Access Journals (Sweden)

Zhi Yang

2016-01-01

Full Text Available Uncertainty is common in ship construction. However, few studies have focused on scheduling problems under uncertainty in shipbuilding. This paper formulates the scheduling problem of panel block construction as a multiobjective fuzzy flow shop scheduling problem (FSSP with a fuzzy processing time, a fuzzy due date, and the just-in-time (JIT concept. An improved multiobjective particle swarm optimization called MOPSO-M is developed to solve the scheduling problem. MOPSO-M utilizes a ranked-order-value rule to convert the continuous position of particles into the discrete permutations of jobs, and an available mapping is employed to obtain the precedence-based permutation of the jobs. In addition, to improve the performance of MOPSO-M, archive maintenance is combined with global best position selection, and mutation and a velocity constriction mechanism are introduced into the algorithm. The feasibility and effectiveness of MOPSO-M are assessed in comparison with general MOPSO and nondominated sorting genetic algorithm-II (NSGA-II.

The Application of Artificial Intelligence to Astronomical Scheduling Problems

Science.gov (United States)

Johnston, Mark D.

1993-01-01

As artificial intelligence (AI) technology has moved from the research laboratory into more and more widespread use, one of the leading applications in astronomy has been to high-profile observation scheduling. The Spike scheduling system was developed by the Space Telescope Science Institute (STScI) for the purpose of long-range scheduling of Hubble Space Telescope (HST). Spike has been in daily operational use at STScI since well before HST launch in April 1990. The system has also been adapted to schedule other missions: one of these missions (EUVE) is currently operational, while another (ASTRO-D) will be launched in February 1993. Some other future space astronomy missions (XTE, SWAS, and AXAF) are making tentative plans to use Spike. Spike has proven to be a powerful and flexible scheduling framework with applicability to a wide variety of problems.

Integrated Job Scheduling and Network Routing

DEFF Research Database (Denmark)

Gamst, Mette; Pisinger, David

2013-01-01

We consider an integrated job scheduling and network routing problem which appears in Grid Computing and production planning. The problem is to schedule a number of jobs at a finite set of machines, such that the overall profit of the executed jobs is maximized. Each job demands a number of resou...... indicate that the algorithm can be used as an actual scheduling algorithm in the Grid or as a tool for analyzing Grid performance when adding extra machines or jobs. © 2012 Wiley Periodicals, Inc.......We consider an integrated job scheduling and network routing problem which appears in Grid Computing and production planning. The problem is to schedule a number of jobs at a finite set of machines, such that the overall profit of the executed jobs is maximized. Each job demands a number...... of resources which must be sent to the executing machine through a network with limited capacity. A job cannot start before all of its resources have arrived at the machine. The scheduling problem is formulated as a Mixed Integer Program (MIP) and proved to be NP-hard. An exact solution approach using Dantzig...

A fast method for the unit scheduling problem with significant renewable power generation

International Nuclear Information System (INIS)

Osório, G.J.; Lujano-Rojas, J.M.; Matias, J.C.O.; Catalão, J.P.S.

2015-01-01

Highlights: • A model to the scheduling of power systems with significant renewable power generation is provided. • A new methodology that takes information from the analysis of each scenario separately is proposed. • Based on a probabilistic analysis, unit scheduling and corresponding economic dispatch are estimated. • A comparison with others methodologies is in favour of the proposed approach. - Abstract: Optimal operation of power systems with high integration of renewable power sources has become difficult as a consequence of the random nature of some sources like wind energy and photovoltaic energy. Nowadays, this problem is solved using Monte Carlo Simulation (MCS) approach, which allows considering important statistical characteristics of wind and solar power production such as the correlation between consecutive observations, the diurnal profile of the forecasted power production, and the forecasting error. However, MCS method requires the analysis of a representative amount of trials, which is an intensive calculation task that increases considerably with the number of scenarios considered. In this paper, a model to the scheduling of power systems with significant renewable power generation based on scenario generation/reduction method, which establishes a proportional relationship between the number of scenarios and the computational time required to analyse them, is proposed. The methodology takes information from the analysis of each scenario separately to determine the probabilistic behaviour of each generator at each hour in the scheduling problem. Then, considering a determined significance level, the units to be committed are selected and the load dispatch is determined. The proposed technique was illustrated through a case study and the comparison with stochastic programming approach was carried out, concluding that the proposed methodology can provide an acceptable solution in a reduced computational time

Discrete Optimization Model for Vehicle Routing Problem with Scheduling Side Cosntraints

Science.gov (United States)

Juliandri, Dedy; Mawengkang, Herman; Bu'ulolo, F.

2018-01-01

Vehicle Routing Problem (VRP) is an important element of many logistic systems which involve routing and scheduling of vehicles from a depot to a set of customers node. This is a hard combinatorial optimization problem with the objective to find an optimal set of routes used by a fleet of vehicles to serve the demands a set of customers It is required that these vehicles return to the depot after serving customers’ demand. The problem incorporates time windows, fleet and driver scheduling, pick-up and delivery in the planning horizon. The goal is to determine the scheduling of fleet and driver and routing policies of the vehicles. The objective is to minimize the overall costs of all routes over the planning horizon. We model the problem as a linear mixed integer program. We develop a combination of heuristics and exact method for solving the model.

Production Planning and Planting Pattern Scheduling Information System for Horticulture

Science.gov (United States)

Vitadiar, Tanhella Zein; Farikhin; Surarso, Bayu

2018-02-01

This paper present the production of planning and planting pattern scheduling faced by horticulture farmer using two methods. Fuzzy time series method use to predict demand on based on sales amount, while linear programming is used to assist horticulture farmers in making production planning decisions and determining the schedule of cropping patterns in accordance with demand predictions of the fuzzy time series method, variable use in this paper is size of areas, production advantage, amount of seeds and age of the plants. This research result production planning and planting patterns scheduling information system with the output is recommendations planting schedule, harvest schedule and the number of seeds will be plant.

Hybrid Genetic Algorithm with Multiparents Crossover for Job Shop Scheduling Problems

Directory of Open Access Journals (Sweden)

Noor Hasnah Moin

2015-01-01

Full Text Available The job shop scheduling problem (JSSP is one of the well-known hard combinatorial scheduling problems. This paper proposes a hybrid genetic algorithm with multiparents crossover for JSSP. The multiparents crossover operator known as extended precedence preservative crossover (EPPX is able to recombine more than two parents to generate a single new offspring distinguished from common crossover operators that recombine only two parents. This algorithm also embeds a schedule generation procedure to generate full-active schedule that satisfies precedence constraints in order to reduce the search space. Once a schedule is obtained, a neighborhood search is applied to exploit the search space for better solutions and to enhance the GA. This hybrid genetic algorithm is simulated on a set of benchmarks from the literatures and the results are compared with other approaches to ensure the sustainability of this algorithm in solving JSSP. The results suggest that the implementation of multiparents crossover produces competitive results.

Solving cyclical nurse scheduling problem using preemptive goal programming

Science.gov (United States)

Sundari, V. E.; Mardiyati, S.

2017-07-01

Nurse scheduling system in a hospital is being modeled as a preemptive goal programming problem that is solved by using LINGO software with the objective function to minimize deviation variable at each goal. The scheduling is done cyclically, so every nurse is treated fairly since they have the same work shift portion with the other nurses. By paying attention to the hospital's rules regarding nursing work shift cyclically, it can be obtained that numbers of nurse needed in every ward are 18 nurses and the numbers of scheduling periods are 18 periods where every period consists of 21 days.

Recent Research Trends in Genetic Algorithm Based Flexible Job Shop Scheduling Problems

OpenAIRE

Amjad, Muhammad Kamal; Butt, Shahid Ikramullah; Kousar, Rubeena; Ahmad, Riaz; Agha, Mujtaba Hassan; Faping, Zhang; Anjum, Naveed; Asgher, Umer

2018-01-01

Flexible Job Shop Scheduling Problem (FJSSP) is an extension of the classical Job Shop Scheduling Problem (JSSP). The FJSSP is known to be NP-hard problem with regard to optimization and it is very difficult to find reasonably accurate solutions of the problem instances in a rational time. Extensive research has been carried out in this area especially over the span of the last 20 years in which the hybrid approaches involving Genetic Algorithm (GA) have gained the most popularity. Keeping in...

Resource-constrained project scheduling problem: review of past and recent developments

Directory of Open Access Journals (Sweden)

Farhad Habibi

2018-01-01

Full Text Available The project scheduling problem is both practically and theoretically of paramount importance. From the practical perspective, improvement of project scheduling as a critical part of project management process can lead to successful project completion and significantly decrease of the relevant costs. From the theoretical perspective, project scheduling is regarded as one of the in-teresting optimization issues, which has attracted the attention of many researchers in the area of operations research. Therefore, the project scheduling issue has been significantly evaluated over time and has been developed from various aspects. In this research, the topics related to Re-source-Constrained Project Scheduling Problem (RCPSP are reviewed, recent developments in this field are evaluated, and the results are presented for future studies. In this regard, first, the standard problem of RCPSP is expressed and related developments are presented from four as-pects of resources, characteristics of activities, type of objective functions, and availability level of information. Following that, details about 216 articles conducted on RCPSP during 1980-2017 are expressed. At the end, in line with the statistics obtained from the evaluation of previ-ous articles, suggestions are made for the future studies in order to help the development of new issues in this area.

A new genetic algorithm for flexible job-shop scheduling problems

International Nuclear Information System (INIS)

Driss, Imen; Mouss, Kinza Nadia; Laggoun, Assia

2015-01-01

Flexible job-shop scheduling problem (FJSP), which is proved to be NP-hard, is an extension of the classical job-shop scheduling problem. In this paper, we propose a new genetic algorithm (NGA) to solve FJSP to minimize makespan. This new algorithm uses a new chromosome representation and adopts different strategies for crossover and mutation. The proposed algorithm is validated on a series of benchmark data sets and tested on data from a drug manufacturing company. Experimental results prove that the NGA is more efficient and competitive than some other existing algorithms.

A new genetic algorithm for flexible job-shop scheduling problems

Energy Technology Data Exchange (ETDEWEB)

Driss, Imen; Mouss, Kinza Nadia; Laggoun, Assia [University of Batna, Batna (Algeria)

2015-03-15

Flexible job-shop scheduling problem (FJSP), which is proved to be NP-hard, is an extension of the classical job-shop scheduling problem. In this paper, we propose a new genetic algorithm (NGA) to solve FJSP to minimize makespan. This new algorithm uses a new chromosome representation and adopts different strategies for crossover and mutation. The proposed algorithm is validated on a series of benchmark data sets and tested on data from a drug manufacturing company. Experimental results prove that the NGA is more efficient and competitive than some other existing algorithms.

Flowshop Scheduling Problems with a Position-Dependent Exponential Learning Effect

Directory of Open Access Journals (Sweden)

Mingbao Cheng

2013-01-01

Full Text Available We consider a permutation flowshop scheduling problem with a position-dependent exponential learning effect. The objective is to minimize the performance criteria of makespan and the total flow time. For the two-machine flow shop scheduling case, we show that Johnson’s rule is not an optimal algorithm for minimizing the makespan given the exponential learning effect. Furthermore, by using the shortest total processing times first (STPT rule, we construct the worst-case performance ratios for both criteria. Finally, a polynomial-time algorithm is proposed for special cases of the studied problem.

An Artificial Bee Colony Algorithm for the Job Shop Scheduling Problem with Random Processing Times

Directory of Open Access Journals (Sweden)

Rui Zhang

2011-09-01

Full Text Available Due to the influence of unpredictable random events, the processing time of each operation should be treated as random variables if we aim at a robust production schedule. However, compared with the extensive research on the deterministic model, the stochastic job shop scheduling problem (SJSSP has not received sufficient attention. In this paper, we propose an artificial bee colony (ABC algorithm for SJSSP with the objective of minimizing the maximum lateness (which is an index of service quality. First, we propose a performance estimate for preliminary screening of the candidate solutions. Then, the K-armed bandit model is utilized for reducing the computational burden in the exact evaluation (through Monte Carlo simulation process. Finally, the computational results on different-scale test problems validate the effectiveness and efficiency of the proposed approach.

The Home Care Crew Scheduling Problem

DEFF Research Database (Denmark)

Rasmussen, Matias Sevel; Justesen, Tor

In the Home Care Crew Scheduling Problem (HCCSP) a staff of caretakers has to be assigned a number of visits, such that the total number of assigned visits is maximised. The visits have different locations and positions in time, and travelling time and time windows must be respected. The challenge...... when assigning visits to caretakers lies in the existence of soft constraints and indeed also in temporal dependencies between the starting times of visits. Most former approaches to solving the HCCSP involve the use of heuristic methods. Here we develop an exact branch-and-price algorithm that uses...... clustering of the visits based on the problem structure. The algorithm is tested on real-life problem instances and we obtain solutions that are better than current practice in all cases....

Variable Neighborhood Search for Parallel Machines Scheduling Problem with Step Deteriorating Jobs

Directory of Open Access Journals (Sweden)

Wenming Cheng

2012-01-01

Full Text Available In many real scheduling environments, a job processed later needs longer time than the same job when it starts earlier. This phenomenon is known as scheduling with deteriorating jobs to many industrial applications. In this paper, we study a scheduling problem of minimizing the total completion time on identical parallel machines where the processing time of a job is a step function of its starting time and a deteriorating date that is individual to all jobs. Firstly, a mixed integer programming model is presented for the problem. And then, a modified weight-combination search algorithm and a variable neighborhood search are employed to yield optimal or near-optimal schedule. To evaluate the performance of the proposed algorithms, computational experiments are performed on randomly generated test instances. Finally, computational results show that the proposed approaches obtain near-optimal solutions in a reasonable computational time even for large-sized problems.

Automated scheduling and planning from theory to practice

CERN Document Server

Ozcan, Ender; Urquhart, Neil

2013-01-01

  Solving scheduling problems has long presented a challenge for computer scientists and operations researchers. The field continues to expand as researchers and practitioners examine ever more challenging problems and develop automated methods capable of solving them. This book provides 11 case studies in automated scheduling, submitted by leading researchers from across the world. Each case study examines a challenging real-world problem by analysing the problem in detail before investigating how the problem may be solved using state of the art techniques.The areas covered include aircraft scheduling, microprocessor instruction scheduling, sports fixture scheduling, exam scheduling, personnel scheduling and production scheduling.  Problem solving methodologies covered include exact as well as (meta)heuristic approaches, such as local search techniques, linear programming, genetic algorithms and ant colony optimisation.The field of automated scheduling has the potential to impact many aspects of our lives...

Automated Scheduling Via Artificial Intelligence

Science.gov (United States)

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.

Advances in mixed-integer programming methods for chemical production scheduling.

Science.gov (United States)

Velez, Sara; Maravelias, Christos T

2014-01-01

The goal of this paper is to critically review advances in the area of chemical production scheduling over the past three decades and then present two recently proposed solution methods that have led to dramatic computational enhancements. First, we present a general framework and problem classification and discuss modeling and solution methods with an emphasis on mixed-integer programming (MIP) techniques. Second, we present two solution methods: (a) a constraint propagation algorithm that allows us to compute parameters that are then used to tighten MIP scheduling models and (b) a reformulation that introduces new variables, thus leading to effective branching. We also present computational results and an example illustrating how these methods are implemented, as well as the resulting enhancements. We close with a discussion of open research challenges and future research directions.

Flexible ship loading problem with transfer vehicle assignment and scheduling

DEFF Research Database (Denmark)

Iris, Çağatay; Christensen, Jonas; Pacino, Dario

2018-01-01

This paper presents the flexible containership loading problem for seaport container terminals. The integrated management of loading operations, planning of the transport vehicles to use and their scheduling is what we define as the Flexible Ship Loading Problem (FSLP). The flexibility comes from...

Interface between the production plan and the master production schedule in assembly environments

OpenAIRE

Moya Navarro, Marcos; Sánchez Brenes, Magaly

2012-01-01

In a production environment there is a direct relationship between the market and the manufacturing process of goods.When production is immersed in an assembly environment, the process of production planning and scheduling becomes complex, and the enterprises have the risk of losing competitive advantages in terms of not meeting delivery dates and production high costs. Linear programming has become an appropriate tool for production planning and scheduling in complex manufacturing environmen...

Extended precedence preservative crossover for job shop scheduling problems

Science.gov (United States)

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.

A Distributed Particle Swarm Optimization Zlgorithmfor Flexible Job-hop Scheduling Problem

Directory of Open Access Journals (Sweden)

LIU Sheng--hui

2017-06-01

Full Text Available According to the characteristics of the Flexible job shop scheduling problem the minimum makespan as measures we proposed a distributed particle swarm optimization algorithm aiming to solve flexible job shop scheduling problem. The algorithm adopts the method of distributed ideas to solve problems and we are established for two multi agent particle swarm optimization model in this algorithm it can solve the traditional particle swarm optimization algorithm when making decisions in real time according to the emergencies. Finally some benthmark problems were experimented and the results are compared with the traditional algorithm. Experimental results proved that the developed distributed PSO is enough effective and efficient to solve the FJSP and it also verified the reasonableness of the multi}gent particle swarm optimization model.

A Study on the Enhanced Best Performance Algorithm for the Just-in-Time Scheduling Problem

Directory of Open Access Journals (Sweden)

Sivashan Chetty

2015-01-01

Full Text Available The Just-In-Time (JIT scheduling problem is an important subject of study. It essentially constitutes the problem of scheduling critical business resources in an attempt to optimize given business objectives. This problem is NP-Hard in nature, hence requiring efficient solution techniques. To solve the JIT scheduling problem presented in this study, a new local search metaheuristic algorithm, namely, the enhanced Best Performance Algorithm (eBPA, is introduced. This is part of the initial study of the algorithm for scheduling problems. The current problem setting is the allocation of a large number of jobs required to be scheduled on multiple and identical machines which run in parallel. The due date of a job is characterized by a window frame of time, rather than a specific point in time. The performance of the eBPA is compared against Tabu Search (TS and Simulated Annealing (SA. SA and TS are well-known local search metaheuristic algorithms. The results show the potential of the eBPA as a metaheuristic algorithm.

Erratum to ''Johnson's algorithm : A key to solve optimally or approximately flowshop scheduling problems with unavailability periods'' [International Journal of Production Economics 121 (2009) 81-87

OpenAIRE

Rapine , Christophe

2013-01-01

International audience; In Allaoui H., Artiba A, ''Johnson's algorithm : A key to solve optimally or approximately flowshop scheduling problems with unavailability periods'' [International Journal of Production Economics 121 (2009)] the authors propose optimality conditions for the Johnson sequence in presence of one unavailability period on the first machine and pretend for a performance guarantee of 2 when several unavailability periods may occur. We establish in this note that these condit...

Rework Impacts Evaluation Through System Dynamics Approach in Overlapped Product Development Schedule

Directory of Open Access Journals (Sweden)

Lino Guimarães Marujo

2009-07-01

Full Text Available This work aims to explore a novel framework to analyze the planning concepts in product development projects employing techniques to reduce the lead-time of activities, such as overlapping of a pair of each. With the System Dynamics methodology a model to evaluate the rework fraction needed to accommodate the deviations proportional to the overlapping grade of the activities. A numerical example is provided to demonstrate the validity of the model. Although problems encountered during the project management are dynamic, they have been treated on a static basis, what has as result, chronic schedules delays, overruns and cost overspent persist in follow the managers’ (reactions. In this work, we have addressed this known problem by introducing and reviewing some characteristics of the concept of rework in overlapped schedules. This consists in observe and capture the relations feedbacks among the original planned project schedule, the overlapping strategy and the inherent uncertainty in a work being done with poor information. To realize this concept, we have faced with many behaviors patterns (e.g. rework, new duration, non-conformity, and analyze the output behavior pattern, produced by the proposed model.

Solving a manpower scheduling problem for airline catering using metaheuristics

DEFF Research Database (Denmark)

Ho, Sin C.; Leung, Janny M. Y.

2010-01-01

We study a manpower scheduling problem with job time-windows and job-skills compatibility constraints. This problem is motivated by airline catering operations, whereby airline meals and other supplies are delivered to aircrafts on the tarmac just before the flights take-off.  Jobs (flights) must...

Gaussian variable neighborhood search for the file transfer scheduling problem

Directory of Open Access Journals (Sweden)

Dražić Zorica

2016-01-01

Full Text Available This paper presents new modifications of Variable Neighborhood Search approach for solving the file transfer scheduling problem. To obtain better solutions in a small neighborhood of a current solution, we implement two new local search procedures. As Gaussian Variable Neighborhood Search showed promising results when solving continuous optimization problems, its implementation in solving the discrete file transfer scheduling problem is also presented. In order to apply this continuous optimization method to solve the discrete problem, mapping of uncountable set of feasible solutions into a finite set is performed. Both local search modifications gave better results for the large size instances, as well as better average performance for medium and large size instances. One local search modification achieved significant acceleration of the algorithm. The numerical experiments showed that the results obtained by Gaussian modifications are comparable with the results obtained by standard VNS based algorithms, developed for combinatorial optimization. In some cases Gaussian modifications gave even better results. [Projekat Ministarstava nauke Republike Srbije, br. 174010

A Pareto archive floating search procedure for solving multi-objective flexible job shop scheduling problem

Directory of Open Access Journals (Sweden)

J. S. Sadaghiani

2014-04-01

Full Text Available Flexible job shop scheduling problem is a key factor of using efficiently in production systems. This paper attempts to simultaneously optimize three objectives including minimization of the make span, total workload and maximum workload of jobs. Since the multi objective flexible job shop scheduling problem is strongly NP-Hard, an integrated heuristic approach has been used to solve it. The proposed approach was based on a floating search procedure that has used some heuristic algorithms. Within floating search procedure utilize local heuristic algorithms; it makes the considered problem into two sections including assigning and sequencing sub problem. First of all search is done upon assignment space achieving an acceptable solution and then search would continue on sequencing space based on a heuristic algorithm. This paper has used a multi-objective approach for producing Pareto solution. Thus proposed approach was adapted on NSGA II algorithm and evaluated Pareto-archives. The elements and parameters of the proposed algorithms were adjusted upon preliminary experiments. Finally, computational results were used to analyze efficiency of the proposed algorithm and this results showed that the proposed algorithm capable to produce efficient solutions.

Solving Large Scale Crew Scheduling Problems in Practice

NARCIS (Netherlands)

E.J.W. Abbink (Erwin); L. Albino; T.A.B. Dollevoet (Twan); D. Huisman (Dennis); J. Roussado; R.L. Saldanha

2010-01-01

textabstractThis paper deals with large-scale crew scheduling problems arising at the Dutch railway operator, Netherlands Railways (NS). NS operates about 30,000 trains a week. All these trains need a driver and a certain number of guards. Some labor rules restrict the duties of a certain crew base

Heuristic Method for Decision-Making in Common Scheduling Problems

Directory of Open Access Journals (Sweden)

Edyta Kucharska

2017-10-01

Full Text Available The aim of the paper is to present a heuristic method for decision-making regarding an NP-hard scheduling problem with limitations related to tasks and the resources dependent on the current state of the process. The presented approach is based on the algebraic-logical meta-model (ALMM, which enables making collective decisions in successive process stages, not separately for individual objects or executors. Moreover, taking into account the limitations of the problem, it involves constructing only an acceptable solution and significantly reduces the amount of calculations. A general algorithm based on the presented method is composed of the following elements: preliminary analysis of the problem, techniques for the choice of decision at a given state, the pruning non-perspective trajectory, selection technique of the initial state for the trajectory final part, and the trajectory generation parameters modification. The paper includes applications of the presented approach to scheduling problems on unrelated parallel machines with a deadline and machine setup time dependent on the process state, where the relationship between tasks is defined by the graph. The article also presents the results of computational experiments.

A priority-based heuristic algorithm (PBHA for optimizing integrated process planning and scheduling problem

Directory of Open Access Journals (Sweden)

Muhammad Farhan Ausaf

2015-12-01

Full Text Available Process planning and scheduling are two important components of a manufacturing setup. It is important to integrate them to achieve better global optimality and improved system performance. To find optimal solutions for integrated process planning and scheduling (IPPS problem, numerous algorithm-based approaches exist. Most of these approaches try to use existing meta-heuristic algorithms for solving the IPPS problem. Although these approaches have been shown to be effective in optimizing the IPPS problem, there is still room for improvement in terms of quality of solution and algorithm efficiency, especially for more complicated problems. Dispatching rules have been successfully utilized for solving complicated scheduling problems, but haven’t been considered extensively for the IPPS problem. This approach incorporates dispatching rules with the concept of prioritizing jobs, in an algorithm called priority-based heuristic algorithm (PBHA. PBHA tries to establish job and machine priority for selecting operations. Priority assignment and a set of dispatching rules are simultaneously used to generate both the process plans and schedules for all jobs and machines. The algorithm was tested for a series of benchmark problems. The proposed algorithm was able to achieve superior results for most complex problems presented in recent literature while utilizing lesser computational resources.

Solving multi-objective job shop scheduling problems using a non-dominated sorting genetic algorithm

Science.gov (United States)

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.

A hybrid genetic algorithm for the distributed permutation flowshop scheduling problem

Directory of Open Access Journals (Sweden)

Jian Gao

2011-08-01

Full Text Available Distributed Permutation Flowshop Scheduling Problem (DPFSP is a newly proposed scheduling problem, which is a generalization of classical permutation flow shop scheduling problem. The DPFSP is NP-hard in general. It is in the early stages of studies on algorithms for solving this problem. In this paper, we propose a GA-based algorithm, denoted by GA_LS, for solving this problem with objective to minimize the maximum completion time. In the proposed GA_LS, crossover and mutation operators are designed to make it suitable for the representation of DPFSP solutions, where the set of partial job sequences is employed. Furthermore, GA_LS utilizes an efficient local search method to explore neighboring solutions. The local search method uses three proposed rules that move jobs within a factory or between two factories. Intensive experiments on the benchmark instances, extended from Taillard instances, are carried out. The results indicate that the proposed hybrid genetic algorithm can obtain better solutions than all the existing algorithms for the DPFSP, since it obtains better relative percentage deviation and differences of the results are also statistically significant. It is also seen that best-known solutions for most instances are updated by our algorithm. Moreover, we also show the efficiency of the GA_LS by comparing with similar genetic algorithms with the existing local search methods.

Hybrid IP/CP Methods for Solving Sports Scheduling Problems

DEFF Research Database (Denmark)

Rasmussen, Rasmus Vinther

2006-01-01

The field of sports scheduling comprises a challenging research areawith a great variety of hard combinatorial optimization problems andchallenging practical applications. This dissertation gives acomprehensive survey of the area and a number of new contributionsare presented. First a general sol...

Literature Review on the Hybrid Flow Shop Scheduling Problem with Unrelated Parallel Machines

Directory of Open Access Journals (Sweden)

Eliana Marcela Peña Tibaduiza

2017-01-01

Full Text Available Context: The flow shop hybrid problem with unrelated parallel machines has been less studied in the academia compared to the flow shop hybrid with identical processors. For this reason, there are few reports about the kind of application of this problem in industries. Method: A literature review of the state of the art on flow-shop scheduling problem was conducted by collecting and analyzing academic papers on several scientific databases. For this aim, a search query was constructed using keywords defining the problem and checking the inclusion of unrelated parallel machines in such definition; as a result, 50 papers were finally selected for this study. Results: A classification of the problem according to the characteristics of the production system was performed, also solution methods, constraints and objective functions commonly used are presented. Conclusions: An increasing trend is observed in studies of flow shop with multiple stages, but few are based on industry case-studies.

Heuristics for no-wait flow shop scheduling problem

Directory of Open Access Journals (Sweden)

Kewal Krishan Nailwal

2016-09-01

Full Text Available No-wait flow shop scheduling refers to continuous flow of jobs through different machines. The job once started should have the continuous processing through the machines without wait. This situation occurs when there is a lack of an intermediate storage between the processing of jobs on two consecutive machines. The problem of no-wait with the objective of minimizing makespan in flow shop scheduling is NP-hard; therefore the heuristic algorithms are the key to solve the problem with optimal solution or to approach nearer to optimal solution in simple manner. The paper describes two heuristics, one constructive and an improvement heuristic algorithm obtained by modifying the constructive one for sequencing n-jobs through m-machines in a flow shop under no-wait constraint with the objective of minimizing makespan. The efficiency of the proposed heuristic algorithms is tested on 120 Taillard’s benchmark problems found in the literature against the NEH under no-wait and the MNEH heuristic for no-wait flow shop problem. The improvement heuristic outperforms all heuristics on the Taillard’s instances by improving the results of NEH by 27.85%, MNEH by 22.56% and that of the proposed constructive heuristic algorithm by 24.68%. To explain the computational process of the proposed algorithm, numerical illustrations are also given in the paper. Statistical tests of significance are done in order to draw the conclusions.

Heuristic algorithm for single resource constrained project scheduling problem based on the dynamic programming

Directory of Open Access Journals (Sweden)

Stanimirović Ivan

2009-01-01

Full Text Available We introduce a heuristic method for the single resource constrained project scheduling problem, based on the dynamic programming solution of the knapsack problem. This method schedules projects with one type of resources, in the non-preemptive case: once started an activity is not interrupted and runs to completion. We compare the implementation of this method with well-known heuristic scheduling method, called Minimum Slack First (known also as Gray-Kidd algorithm, as well as with Microsoft Project.

A Multiagent Evolutionary Algorithm for the Resource-Constrained Project Portfolio Selection and Scheduling Problem

Directory of Open Access Journals (Sweden)

Yongyi Shou

2014-01-01

Full Text Available A multiagent evolutionary algorithm is proposed to solve the resource-constrained project portfolio selection and scheduling problem. The proposed algorithm has a dual level structure. In the upper level a set of agents make decisions to select appropriate project portfolios. Each agent selects its project portfolio independently. The neighborhood competition operator and self-learning operator are designed to improve the agent’s energy, that is, the portfolio profit. In the lower level the selected projects are scheduled simultaneously and completion times are computed to estimate the expected portfolio profit. A priority rule-based heuristic is used by each agent to solve the multiproject scheduling problem. A set of instances were generated systematically from the widely used Patterson set. Computational experiments confirmed that the proposed evolutionary algorithm is effective for the resource-constrained project portfolio selection and scheduling problem.

Artificial immune algorithm for multi-depot vehicle scheduling problems

Science.gov (United States)

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.

A Genetic Algorithm-based Heuristic for Part-Feeding Mobile Robot Scheduling Problem

DEFF Research Database (Denmark)

Dang, Vinh Quang; Nielsen, Izabela Ewa; Bocewicz, Grzegorz

2012-01-01

This present study deals with the problem of sequencing feeding tasks of a single mobile robot with manipulation arm which is able to provide parts or components for feeders of machines in a manufacturing cell. The mobile robot has to be scheduled in order to keep machines within the cell producing...... products without any shortage of parts. A method based on the characteristics of feeders and inspired by the (s, Q) inventory system, is thus applied to define time windows for feeding tasks of the robot. The performance criterion is to minimize total traveling time of the robot in a given planning horizon...

A hybrid electromagnetism-like algorithm for a multi-mode resource-constrained project scheduling problem

Directory of Open Access Journals (Sweden)

Mohammad Hossein Sadeghi

2013-08-01

Full Text Available In this paper, two different sub-problems are considered to solve a resource constrained project scheduling problem (RCPSP, namely i assignment of modes to tasks and ii scheduling of these tasks in order to minimize the makespan of the project. The modified electromagnetism-like algorithm deals with the first problem to create an assignment of modes to activities. This list is used to generate a project schedule. When a new assignment is made, it is necessary to fix all mode dependent requirements of the project activities and to generate a random schedule with the serial SGS method. A local search will optimize the sequence of the activities. Also in this paper, a new penalty function has been proposed for solutions which are infeasible with respect to non-renewable resources. Performance of the proposed algorithm has been compared with the best algorithms published so far on the basis of CPU time and number of generated schedules stopping criteria. Reported results indicate excellent performance of the algorithm.

Freezing the Master Production Schedule Under Rolling Planning Horizons

OpenAIRE

V. Sridharan; William L. Berry; V. Udayabhanu

1987-01-01

The stability of the Master Production Schedule (MPS) is a critical issue in managing production operations with a Material Requirements Planning System. One method of achieving stability is to freeze some portion or all of the MPS. While freezing the MPS can limit the number of schedule changes, it can also produce an increase in production and inventory costs. This paper examines three decision variables in freezing the MPS: the freezing method, the freeze interval length, and the planning ...

Optimization of the solution of the problem of scheduling theory ...

African Journals Online (AJOL)

This article describes the genetic algorithm used to solve the problem related to the scheduling theory. A large number of different methods is described in the scientific literature. The main issue that faced the problem in question is that it is necessary to search the optimal solution in a large search space for the set of ...

Cooperated Bayesian algorithm for distributed scheduling problem

Institute of Scientific and Technical Information of China (English)

QIANG Lei; XIAO Tian-yuan

2006-01-01

This paper presents a new distributed Bayesian optimization algorithm (BOA) to overcome the efficiency problem when solving NP scheduling problems.The proposed approach integrates BOA into the co-evolutionary schema,which builds up a concurrent computing environment.A new search strategy is also introduced for local optimization process.It integrates the reinforcement learning(RL) mechanism into the BOA search processes,and then uses the mixed probability information from BOA (post-probability) and RL (pre-probability) to enhance the cooperation between different local controllers,which improves the optimization ability of the algorithm.The experiment shows that the new algorithm does better in both optimization (2.2%) and convergence (11.7%),compared with classic BOA.

A Generalized Ant Colony Algorithm for Job一shop Scheduling Problem

Directory of Open Access Journals (Sweden)

ZHANG Hong-Guo

2017-02-01

Full Text Available Aiming at the problem of ant colony algorithm for solving Job一shop scheduling problem. Considering the complexity of the algorithm that uses disjunctive graph to describe the relationship between workpiece processing. To solve the problem of optimal solution，a generalized ant colony algorithm is proposed. Under the premise of considering constrained relationship between equipment and process，the pheromone update mechanism is applied to solve Job-shop scheduling problem，so as to improve the quality of the solution. In order to improve the search efficiency，according to the state transition rules of ant colony algorithm，this paper makes a detailed study on the selection and improvement of the parameters in the algorithm，and designs the pheromone update strategy. Experimental results show that a generalized ant colony algorithm is more feasible and more effective. Compared with other algorithms in the literature，the results prove that the algorithm improves in computing the optimal solution and convergence speed.

On non-permutation solutions to some two machine flow shop scheduling problems

NARCIS (Netherlands)

V. Strusevich (Vitaly); P.J. Zwaneveld (Peter)

1994-01-01

textabstractIn this paper, we study two versions of the two machine flow shop scheduling problem, where schedule length is to be minimized. First, we consider the two machine flow shop with setup, processing, and removal times separated. It is shown that an optimal solution need not be a permutation

Solving a manpower scheduling problem for airline catering using tabu search

DEFF Research Database (Denmark)

Ho, Sin C.; Leung, Janny M. Y.

We study a manpower scheduling problem with job time-windows and job-skills compatibility constraints. This problem is motivated by airline catering operations, whereby airline meals and other supplies are delivered to aircrafts on the tarmac just before the flights take off. Jobs (flights) must...

A duty-period-based formulation of the airline crew scheduling problem

Energy Technology Data Exchange (ETDEWEB)

Hoffman, K.

1994-12-31

We present a new formulation of the airline crew scheduling problem that explicitly considers the duty periods. We suggest an algorithm for solving the formulation by a column generation approach with branch-and-bound. Computational results are reported for a number of test problems.

A branch-and-price algorithm for the long-term home care scheduling problem

DEFF Research Database (Denmark)

Gamst, Mette; Jensen, Thomas Sejr

2012-01-01

In several countries, home care is provided for certain citizens living at home. The long-term home care scheduling problem is to generate work plans such that a high quality of service is maintained, the work hours of the employees are respected, and the overall cost is kept as low as possible. We...... propose a branchand-price algorithm for the long-term home care scheduling problem. The pricing problem generates a one-day plan for an employee, and the master problem merges the plans with respect to regularity constraints. The method is capable of generating plans with up to 44 visits during one week....

A canned food scheduling problem with batch due date

Science.gov (United States)

Chung, Tsui-Ping; Liao, Ching-Jong; Smith, Milton

2014-09-01

This article considers a canned food scheduling problem where jobs are grouped into several batches. Jobs can be sent to the next operation only when all the jobs in the same batch have finished their processing, i.e. jobs in a batch, have a common due date. This batch due date problem is quite common in canned food factories, but there is no efficient heuristic to solve the problem. The problem can be formulated as an identical parallel machine problem with batch due date to minimize the total tardiness. Since the problem is NP hard, two heuristics are proposed to find the near-optimal solution. Computational results comparing the effectiveness and efficiency of the two proposed heuristics with an existing heuristic are reported and discussed.

Algorithm for complete enumeration based on a stroke graph to solve the supply network configuration and operations scheduling problem

Directory of Open Access Journals (Sweden)

Julien Maheut

2013-07-01

Full Text Available Purpose: The purpose of this paper is to present an algorithm that solves the supply network configuration and operations scheduling problem in a mass customization company that faces alternative operations for one specific tool machine order in a multiplant context. Design/methodology/approach: To achieve this objective, the supply chain network configuration and operations scheduling problem is presented. A model based on stroke graphs allows the design of an algorithm that enumerates all the feasible solutions. The algorithm considers the arrival of a new customized order proposal which has to be inserted into a scheduled program. A selection function is then used to choose the solutions to be simulated in a specific simulation tool implemented in a Decision Support System. Findings and Originality/value: The algorithm itself proves efficient to find all feasible solutions when alternative operations must be considered. The stroke structure is successfully used to schedule operations when considering more than one manufacturing and supply option in each step. Research limitations/implications: This paper includes only the algorithm structure for a one-by-one, sequenced introduction of new products into the list of units to be manufactured. Therefore, the lotsizing process is done on a lot-per-lot basis. Moreover, the validation analysis is done through a case study and no generalization can be done without risk. Practical implications: The result of this research would help stakeholders to determine all the feasible and practical solutions for their problem. It would also allow to assessing the total costs and delivery times of each solution. Moreover, the Decision Support System proves useful to assess alternative solutions. Originality/value: This research offers a simple algorithm that helps solve the supply network configuration problem and, simultaneously, the scheduling problem by considering alternative operations. The proposed system

Optimal Research and Numerical Simulation for Scheduling No-Wait Flow Shop in Steel Production

Directory of Open Access Journals (Sweden)

Huawei Yuan

2013-01-01

Full Text Available This paper considers the m-machine flow shop scheduling problem with the no-wait constraint to minimize total completion time which is the typical model in steel production. First, the asymptotic optimality of the Shortest Processing Time (SPT first rule is proven for this problem. To further evaluate the performance of the algorithm, a new lower bound with performance guarantee is designed. At the end of the paper, numerical simulations show the effectiveness of the proposed algorithm and lower bound.

Integrated batch production and maintenance scheduling for multiple items processed on a deteriorating machine to minimize total production and maintenance costs with due date constraint

Directory of Open Access Journals (Sweden)

Zahedi Zahedi

2016-04-01

Full Text Available This paper discusses an integrated model of batch production and maintenance scheduling on a deteriorating machine producing multiple items to be delivered at a common due date. The model describes the trade-off between total inventory cost and maintenance cost as the increase of production run length. The production run length is a time bucket between two consecutive preventive maintenance activities. The objective function of the model is to minimize total cost consisting of in process and completed part inventory costs, setup cost, preventive and corrective maintenance costs and rework cost. The problem is to determine the optimal production run length and to schedule the batches obtained from determining the production run length in order to minimize total cost.

Flexible job-shop scheduling based on genetic algorithm and simulation validation

Directory of Open Access Journals (Sweden)

Zhou Erming

2017-01-01

Full Text Available This paper selects flexible job-shop scheduling problem as the research object, and Constructs mathematical model aimed at minimizing the maximum makespan. Taking the transmission reverse gear production line of a transmission corporation as an example, genetic algorithm is applied for flexible jobshop scheduling problem to get the specific optimal scheduling results with MATLAB. DELMIA/QUEST based on 3D discrete event simulation is applied to construct the physical model of the production workshop. On the basis of the optimal scheduling results, the logical link of the physical model for the production workshop is established, besides, importing the appropriate process parameters to make virtual simulation on the production workshop. Finally, through analyzing the simulated results, it shows that the scheduling results are effective and reasonable.

Constraint-based job shop scheduling with ILOG SCHEDULER

NARCIS (Netherlands)

Nuijten, W.P.M.; Le Pape, C.

1998-01-01

We introduce constraint-based scheduling and discuss its main principles. An approximation algorithm based on tree search is developed for the job shop scheduling problem using ILOG SCHEDULER. A new way of calculating lower bounds on the makespan of the job shop scheduling problem is presented and

Comparative Simulation Study of Production Scheduling in the Hybrid and the Parallel Flow

Directory of Open Access Journals (Sweden)

Varela Maria L.R.

2017-06-01

Full Text Available Scheduling is one of the most important decisions in production control. An approach is proposed for supporting users to solve scheduling problems, by choosing the combination of physical manufacturing system configuration and the material handling system settings. The approach considers two alternative manufacturing scheduling configurations in a two stage product oriented manufacturing system, exploring the hybrid flow shop (HFS and the parallel flow shop (PFS environments. For illustrating the application of the proposed approach an industrial case from the automotive components industry is studied. The main aim of this research to compare results of study of production scheduling in the hybrid and the parallel flow, taking into account the makespan minimization criterion. Thus the HFS and the PFS performance is compared and analyzed, mainly in terms of the makespan, as the transportation times vary. The study shows that the performance HFS is clearly better when the work stations’ processing times are unbalanced, either in nature or as a consequence of the addition of transport times just to one of the work station processing time but loses advantage, becoming worse than the performance of the PFS configuration when the work stations’ processing times are balanced, either in nature or as a consequence of the addition of transport times added on the work stations’ processing times. This means that physical layout configurations along with the way transport time are including the work stations’ processing times should be carefully taken into consideration due to its influence on the performance reached by both HFS and PFS configurations.

Recent Research Trends in Genetic Algorithm Based Flexible Job Shop Scheduling Problems

Directory of Open Access Journals (Sweden)

Muhammad Kamal Amjad

2018-01-01

Full Text Available Flexible Job Shop Scheduling Problem (FJSSP is an extension of the classical Job Shop Scheduling Problem (JSSP. The FJSSP is known to be NP-hard problem with regard to optimization and it is very difficult to find reasonably accurate solutions of the problem instances in a rational time. Extensive research has been carried out in this area especially over the span of the last 20 years in which the hybrid approaches involving Genetic Algorithm (GA have gained the most popularity. Keeping in view this aspect, this article presents a comprehensive literature review of the FJSSPs solved using the GA. The survey is further extended by the inclusion of the hybrid GA (hGA techniques used in the solution of the problem. This review will give readers an insight into use of certain parameters in their future research along with future research directions.

Optimal scheduling for enhanced coal bed methane production through CO2 injection

International Nuclear Information System (INIS)

Huang, Yuping; Zheng, Qipeng P.; Fan, Neng; Aminian, Kashy

2014-01-01

Highlights: • A novel deterministic optimization model for CO 2 -ECBM production scheduling. • Maximize the total profit from both sales of natural gas and CO 2 credits trading in the carbon market. • A stochastic model incorporating uncertainties and dynamics of NG price and CO 2 credit. - Abstract: Enhanced coal bed methane production with CO 2 injection (CO 2 -ECBM) is an effective technology for accessing the natural gas embedded in the traditionally unmineable coal seams. The revenue via this production process is generated not only by the sales of coal bed methane, but also by trading CO 2 credits in the carbon market. As the technology of CO 2 -ECBM becomes mature, its commercialization opportunities are also springing up. This paper proposes applicable mathematical models for CO 2 -ECBM production and compares the impacts of their production schedules on the total profit. A novel basic deterministic model for CO 2 -ECBM production including the technical and chemical details is proposed and then a multistage stochastic programming model is formulated in order to address uncertainties of natural gas price and CO 2 credit. Both models are nonlinear programming problems, which are solved by commercial nonlinear programming software BARON via GAMS. Numerical experiments show the benefits (e.g., expected profit gain) of using stochastic models versus deterministic models

A novel discrete PSO algorithm for solving job shop scheduling problem to minimize makespan

Science.gov (United States)

Rameshkumar, K.; Rajendran, C.

2018-02-01

In this work, a discrete version of PSO algorithm is proposed to minimize the makespan of a job-shop. A novel schedule builder has been utilized to generate active schedules. The discrete PSO is tested using well known benchmark problems available in the literature. The solution produced by the proposed algorithms is compared with best known solution published in the literature and also compared with hybrid particle swarm algorithm and variable neighborhood search PSO algorithm. The solution construction methodology adopted in this study is found to be effective in producing good quality solutions for the various benchmark job-shop scheduling problems.

An Agent-Based Solution Framework for Inter-Block Yard Crane Scheduling Problems

Directory of Open Access Journals (Sweden)

Omor Sharif

2012-06-01

Full Text Available The efficiency of yard operations is critical to the overall productivity of a container terminal because the yard serves as the interface between the landside and waterside operations. Most container terminals use yard cranes to transfer containers between the yard and trucks (both external and internal. To facilitate vessel operations, an efficient work schedule for the yard cranes is necessary given varying work volumes among yard blocks with different planning periods. This paper investigated an agent-based approach to assign and relocate yard cranes among yard blocks based on the forecasted work volumes. The goal of our study is to reduce the work volume that remains incomplete at the end of a planning period. We offered several preference functions for yard cranes and blocks which are modeled as agents. These preference functions are designed to find effective schedules for yard cranes. In addition, we examined various rules for the initial assignment of yard cranes to blocks. Our analysis demonstrated that our model can effectively and efficiently reduce the percentage of incomplete work volume for any real-world sized problem.

A Column Generation Approach for Solving the Patient Admission Scheduling Problem

DEFF Research Database (Denmark)

Range, Troels Martin; Lusby, Richard Martin; Larsen, Jesper

This paper addresses the Patient Admission Scheduling (PAS) problem. The PAS problem deals with assigning elective patients to beds, satisfying a number of soft and hard constraints. The problem can be seen as part of the functions of hospital management at an operational level. There exists a sm...... to produce new best solutions for ve out of six instances from a publicly available repository....

Using the method of ideal point to solve dual-objective problem for production scheduling

Directory of Open Access Journals (Sweden)

Mariia Marko

2016-07-01

Full Text Available In practice, there are often problems, which must simultaneously optimize several criterias. This so-called multi-objective optimization problem. In the article we consider the use of the method ideal point to solve the two-objective optimization problem of production planning. The process of finding solution to the problem consists of a series of steps where using simplex method, we find the ideal point. After that for solving a scalar problems, we use the method of Lagrange multipliers

Neighbourhood generation mechanism applied in simulated annealing to job shop scheduling problems

Science.gov (United States)

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.

Integer programming formulation and variable neighborhood search metaheuristic for the multiproduct pipeline scheduling problem

Energy Technology Data Exchange (ETDEWEB)

Souza Filho, Erito M.; Bahiense, Laura; Ferreira Filho, Virgilio J.M. [Universidade Federal do Rio de Janeiro (UFRJ), RJ (Brazil). Coordenacao dos Programas de Pos-graduacao de Engenharia (COPPE); Lima, Leonardo [Centro Federal de Educacao Tecnologica Celso Sukow da Fonseca (CEFET-RJ), Rio de Janeiro, RJ (Brazil)

2008-07-01

Pipeline are known as the most reliable and economical mode of transportation for petroleum and its derivatives, especially when large amounts of products have to be pumped for large distances. In this work we address the short-term schedule of a pipeline system comprising the distribution of several petroleum derivatives from a single oil refinery to several depots, connected to local consumer markets, through a single multi-product pipeline. We propose an integer linear programming formulation and a variable neighborhood search meta-heuristic in order to compare the performances of the exact and heuristic approaches to the problem. Computational tests in C language and MOSEL/XPRESS-MP language are performed over a real Brazilian pipeline system. (author)

Constraint optimization model of a scheduling problem for a robotic arm in automatic systems

DEFF Research Database (Denmark)

Kristiansen, Ewa; Smith, Stephen F.; Kristiansen, Morten

2014-01-01

are characteristics of the painting process application itself. Unlike spot-welding, painting tasks require movement of the entire robot arm. In addition to minimizing intertask duration, the scheduler must strive to maximize painting quality and the problem is formulated as a multi-objective optimization problem....... The scheduling model is implemented as a stand-alone module using constraint programming, and integrated with a larger automatic system. The results of a number of simulation experiments with simple parts are reported, both to characterize the functionality of the scheduler and to illustrate the operation...... of the entire software system for automatic generation of robot programs for painting....

A hybrid algorithm for flexible job-shop scheduling problem with setup times

Directory of Open Access Journals (Sweden)

Ameni Azzouz

2017-01-01

Full Text Available Job-shop scheduling problem is one of the most important fields in manufacturing optimization where a set of n jobs must be processed on a set of m specified machines. Each job consists of a specific set of operations, which have to be processed according to a given order. The Flexible Job Shop problem (FJSP is a generalization of the above-mentioned problem, where each operation can be processed by a set of resources and has a processing time depending on the resource used. The FJSP problems cover two difficulties, namely, machine assignment problem and operation sequencing problem. This paper addresses the flexible job-shop scheduling problem with sequence-dependent setup times to minimize two kinds of objectives function: makespan and bi-criteria objective function. For that, we propose a hybrid algorithm based on genetic algorithm (GA and variable neighbourhood search (VNS to solve this problem. To evaluate the performance of our algorithm, we compare our results with other methods existing in literature. All the results show the superiority of our algorithm against the available ones in terms of solution quality.

Classification of Ship Routing and Scheduling Problems in Liner Shipping

DEFF Research Database (Denmark)

Kjeldsen, Karina Hjortshøj

2011-01-01

This article provides a classification scheme for ship routing and scheduling problems in liner shipping in line with the current and future operational conditions of the liner shipping industry. Based on the classification, the literature is divided into groups whose main characteristics...

Effective Iterated Greedy Algorithm for Flow-Shop Scheduling Problems with Time lags

Science.gov (United States)

ZHAO, Ning; YE, Song; LI, Kaidian; CHEN, Siyu

2017-05-01

Flow shop scheduling problem with time lags is a practical scheduling problem and attracts many studies. Permutation problem(PFSP with time lags) is concentrated but non-permutation problem(non-PFSP with time lags) seems to be neglected. With the aim to minimize the makespan and satisfy time lag constraints, efficient algorithms corresponding to PFSP and non-PFSP problems are proposed, which consist of iterated greedy algorithm for permutation(IGTLP) and iterated greedy algorithm for non-permutation (IGTLNP). The proposed algorithms are verified using well-known simple and complex instances of permutation and non-permutation problems with various time lag ranges. The permutation results indicate that the proposed IGTLP can reach near optimal solution within nearly 11% computational time of traditional GA approach. The non-permutation results indicate that the proposed IG can reach nearly same solution within less than 1% computational time compared with traditional GA approach. The proposed research combines PFSP and non-PFSP together with minimal and maximal time lag consideration, which provides an interesting viewpoint for industrial implementation.

An FMS Dynamic Production Scheduling Algorithm Considering Cutting Tool Failure and Cutting Tool Life

International Nuclear Information System (INIS)

Setiawan, A; Wangsaputra, R; Halim, A H; Martawirya, Y Y

2016-01-01

This paper deals with Flexible Manufacturing System (FMS) production rescheduling due to unavailability of cutting tools caused either of cutting tool failure or life time limit. The FMS consists of parallel identical machines integrated with an automatic material handling system and it runs fully automatically. Each machine has a same cutting tool configuration that consists of different geometrical cutting tool types on each tool magazine. The job usually takes two stages. Each stage has sequential operations allocated to machines considering the cutting tool life. In the real situation, the cutting tool can fail before the cutting tool life is reached. The objective in this paper is to develop a dynamic scheduling algorithm when a cutting tool is broken during unmanned and a rescheduling needed. The algorithm consists of four steps. The first step is generating initial schedule, the second step is determination the cutting tool failure time, the third step is determination of system status at cutting tool failure time and the fourth step is the rescheduling for unfinished jobs. The approaches to solve the problem are complete-reactive scheduling and robust-proactive scheduling. The new schedules result differences starting time and completion time of each operations from the initial schedule. (paper)

Multi-Objective Flexible Flow Shop Scheduling Problem Considering Variable Processing Time due to Renewable Energy

Directory of Open Access Journals (Sweden)

Xiuli Wu

2018-03-01

Full Text Available Renewable energy is an alternative to non-renewable energy to reduce the carbon footprint of manufacturing systems. Finding out how to make an alternative energy-efficient scheduling solution when renewable and non-renewable energy drives production is of great importance. In this paper, a multi-objective flexible flow shop scheduling problem that considers variable processing time due to renewable energy (MFFSP-VPTRE is studied. First, the optimization model of the MFFSP-VPTRE is formulated considering the periodicity of renewable energy and the limitations of energy storage capacity. Then, a hybrid non-dominated sorting genetic algorithm with variable local search (HNSGA-II is proposed to solve the MFFSP-VPTRE. An operation and machine-based encoding method is employed. A low-carbon scheduling algorithm is presented. Besides the crossover and mutation, a variable local search is used to improve the offspring’s Pareto set. The offspring and the parents are combined and those that dominate more are selected to continue evolving. Finally, two groups of experiments are carried out. The results show that the low-carbon scheduling algorithm can effectively reduce the carbon footprint under the premise of makespan optimization and the HNSGA-II outperforms the traditional NSGA-II and can solve the MFFSP-VPTRE effectively and efficiently.

Combined Noncyclic Scheduling and Advanced Control for Continuous Chemical Processes

Directory of Open Access Journals (Sweden)

Damon Petersen

2017-12-01

Full Text Available A novel formulation for combined scheduling and control of multi-product, continuous chemical processes is introduced in which nonlinear model predictive control (NMPC and noncyclic continuous-time scheduling are efficiently combined. A decomposition into nonlinear programming (NLP dynamic optimization problems and mixed-integer linear programming (MILP problems, without iterative alternation, allows for computationally light solution. An iterative method is introduced to determine the number of production slots for a noncyclic schedule during a prediction horizon. A filter method is introduced to reduce the number of MILP problems required. The formulation’s closed-loop performance with both process disturbances and updated market conditions is demonstrated through multiple scenarios on a benchmark continuously stirred tank reactor (CSTR application with fluctuations in market demand and price for multiple products. Economic performance surpasses cyclic scheduling in all scenarios presented. Computational performance is sufficiently light to enable online operation in a dual-loop feedback structure.

An economic lot and delivery scheduling problem with the fuzzy shelf life in a flexible job shop with unrelated parallel machines

Directory of Open Access Journals (Sweden)

S. Dousthaghi

2012-08-01

Full Text Available This paper considers an economic lot and delivery scheduling problem (ELDSP in a fuzzy environment with the fuzzy shelf life for each product. This problem is formulated in a flexible job shop with unrelated parallel machines, when the planning horizon is finite and it determines lot sizing, scheduling and sequencing, simultaneously. The proposed model of this paper is based on the basic period (BP approach. In this paper, a mixed-integer nonlinear programming (MINLP model is presented and then it is changed into two models in the fuzzy shelf life. The main model is dependent to the multiple basic periods and it is difficult to solve the resulted proposed model for large-scale problems in reasonable amount of time; thus, an efficient heuristic method is proposed to solve the problem. The performance of the proposed model is demonstrated using some numerical examples.

An adaptive large neighborhood search heuristic for the pickup and delivery problem with time Windows and scheduled lines

NARCIS (Netherlands)

Ghilas, V.; Demir, E.; van Woensel, T.

2016-01-01

The Pickup and Delivery Problem with Time Windows and Scheduled Lines (PDPTW-SL) concerns scheduling a set of vehicles to serve freight requests such that a part of the journey can be carried out on a scheduled public transportation line. Due to the complexity of the problem, which is NP-hard, we

The Simultaneous Vehicle Scheduling and Passenger Service Problem with Flexible Dwell Times

DEFF Research Database (Denmark)

Fonseca, Joao Filipe Paiva; Larsen, Allan; van der Hurk, Evelien

In this talk, we deal with a generalization of the well-known Vehicle Scheduling Problem(VSP) that we call Simultaneous Vehicle Scheduling and Passenger Service Problem with Flexible Dwell Times (SVSPSP-FDT). The SVSPSP-FDT generalizes the VSP because the original timetables of the trips can...... be changed (i.e., shifted and stretched) in order to minimize a new objective function that aims at minimizing the operational costs plus the waiting times of the passengers at transfer points. Contrary to most generalizations of the VSP, the SVSPSP-FDT establishes the possibility of changing trips' dwell...... times at important transfer points based on expected passenger ows. We introduce a compact mixed integer linear formulation of the SVSPSP-FDT able to address small instances. We also present a meta-heuristic approach to solve medium/large instances of the problem. The e ectiveness of the proposed...

A Novel Assembly Line Scheduling Algorithm Based on CE-PSO

Directory of Open Access Journals (Sweden)

Xiaomei Hu

2015-01-01

Full Text Available With the widespread application of assembly line in enterprises, assembly line scheduling is an important problem in the production since it directly affects the productivity of the whole manufacturing system. The mathematical model of assembly line scheduling problem is put forward and key data are confirmed. A double objective optimization model based on equipment utilization and delivery time loss is built, and optimization solution strategy is described. Based on the idea of solution strategy, assembly line scheduling algorithm based on CE-PSO is proposed to overcome the shortcomings of the standard PSO. Through the simulation experiments of two examples, the validity of the assembly line scheduling algorithm based on CE-PSO is proved.

A Heuristic Approach for Determining Lot Sizes and Schedules Using Power-of-Two Policy

Directory of Open Access Journals (Sweden)

Esra Ekinci

2007-01-01

Full Text Available We consider the problem of determining realistic and easy-to-schedule lot sizes in a multiproduct, multistage manufacturing environment. We concentrate on a specific type of production, namely, flow shop type production. The model developed consists of two parts, lot sizing problem and scheduling problem. In lot sizing problem, we employ binary integer programming and determine reorder intervals for each product using power-of-two policy. In the second part, using the results obtained of the lot sizing problem, we employ mixed integer programming to determine schedules for a multiproduct, multistage case with multiple machines in each stage. Finally, we provide a numerical example and compare the results with similar methods found in practice.

A Hybrid Differential Evolution and Tree Search Algorithm for the Job Shop Scheduling Problem

Directory of Open Access Journals (Sweden)

Rui Zhang

2011-01-01

Full Text Available The job shop scheduling problem (JSSP is a notoriously difficult problem in combinatorial optimization. In terms of the objective function, most existing research has been focused on the makespan criterion. However, in contemporary manufacturing systems, due-date-related performances are more important because they are essential for maintaining a high service reputation. Therefore, in this study we aim at minimizing the total weighted tardiness in JSSP. Considering the high complexity, a hybrid differential evolution (DE algorithm is proposed for the problem. To enhance the overall search efficiency, a neighborhood property of the problem is discovered, and then a tree search procedure is designed and embedded into the DE framework. According to the extensive computational experiments, the proposed approach is efficient in solving the job shop scheduling problem with total weighted tardiness objective.

A short-term operating room surgery scheduling problem integrating multiple nurses roster constraints.

Science.gov (United States)

Xiang, Wei; Yin, Jiao; Lim, Gino

2015-02-01

Operating room (OR) surgery scheduling determines the individual surgery's operation start time and assigns the required resources to each surgery over a schedule period, considering several constraints related to a complete surgery flow and the multiple resources involved. This task plays a decisive role in providing timely treatments for the patients while balancing hospital resource utilization. The originality of the present study is to integrate the surgery scheduling problem with real-life nurse roster constraints such as their role, specialty, qualification and availability. This article proposes a mathematical model and an ant colony optimization (ACO) approach to efficiently solve such surgery scheduling problems. A modified ACO algorithm with a two-level ant graph model is developed to solve such combinatorial optimization problems because of its computational complexity. The outer ant graph represents surgeries, while the inner graph is a dynamic resource graph. Three types of pheromones, i.e. sequence-related, surgery-related, and resource-related pheromone, fitting for a two-level model are defined. The iteration-best and feasible update strategy and local pheromone update rules are adopted to emphasize the information related to the good solution in makespan, and the balanced utilization of resources as well. The performance of the proposed ACO algorithm is then evaluated using the test cases from (1) the published literature data with complete nurse roster constraints, and 2) the real data collected from a hospital in China. The scheduling results using the proposed ACO approach are compared with the test case from both the literature and the real life hospital scheduling. Comparison results with the literature shows that the proposed ACO approach has (1) an 1.5-h reduction in end time; (2) a reduction in variation of resources' working time, i.e. 25% for ORs, 50% for nurses in shift 1 and 86% for nurses in shift 2; (3) an 0.25h reduction in

On the Integrated Job Scheduling and Constrained Network Routing Problem

DEFF Research Database (Denmark)

Gamst, Mette

This paper examines the NP-hard problem of scheduling a number of jobs on a finite set of machines such that the overall profit of executed jobs is maximized. Each job demands a number of resources, which must be sent to the executing machine via constrained paths. Furthermore, two resource demand...

Optimal Results and Numerical Simulations for Flow Shop Scheduling Problems

Directory of Open Access Journals (Sweden)

Tao Ren

2012-01-01

Full Text Available This paper considers the m-machine flow shop problem with two objectives: makespan with release dates and total quadratic completion time, respectively. For Fm|rj|Cmax, we prove the asymptotic optimality for any dense scheduling when the problem scale is large enough. For Fm‖ΣCj2, improvement strategy with local search is presented to promote the performance of the classical SPT heuristic. At the end of the paper, simulations show the effectiveness of the improvement strategy.

Optimization of multi-objective integrated process planning and scheduling problem using a priority based optimization algorithm

Science.gov (United States)

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.

A non-permutation flowshop scheduling problem with lot streaming: A Mathematical model

Directory of Open Access Journals (Sweden)

Daniel Rossit

2016-06-01

Full Text Available In this paper we investigate the use of lot streaming in non-permutation flowshop scheduling problems. The objective is to minimize the makespan subject to the standard flowshop constraints, but where it is now permitted to reorder jobs between machines. In addition, the jobs can be divided into manageable sublots, a strategy known as lot streaming. Computational experiments show that lot streaming reduces the makespan up to 43% for a wide range of instances when compared to the case in which no job splitting is applied. The benefits grow as the number of stages in the production process increases but reach a limit. Beyond a certain point, the division of jobs into additional sublots does not improve the solution.

Crane Scheduling for a Plate Storage

DEFF Research Database (Denmark)

Hansen, Jesper; Clausen, Jens

2002-01-01

Odense Steel Shipyard produces the worlds largest container ships. The first process of producing the steel ships is handling arrival and storage of steel plates until they are needed in production. This paper considers the problem of scheduling two cranes that carry out the movements of plates...... into, around and out of the storage. The system is required to create a daily schedule for the cranes, but also handle possible disruptions during the execution of the plan. The problem is solved with a Simulated Annealing algorithm....

Development of the Contiguous-cells Transportation Problem

Directory of Open Access Journals (Sweden)

O. E. Charles-Owaba

2015-08-01

Full Text Available The issue of scheduling a long string of multi-period activities which have to be completed without interruption has always been an industrial challenge. The existing production/maintenance scheduling algorithms can only handle situations where activities can be split into two or more sets of activities carried out in non-contiguous sets of work periods. This study proposes a contiguous-periods production/maintenance scheduling approach using the Transportation Model. Relevant variables and parameters of contiguous-cells scheduling problem were taken from the literature. A scheduling optimization problem was defined and solved using a contiguous-cells transportation algorithm (CCTA which was applied in order to determine the optimal maintenance schedule of a fleet of ships at a dockyard in South-Western Nigeria. Fifteen different problems were solved. It is concluded that the contiguous-cells transportation approach to production/ maintenance scheduling is feasible. The model will be a useful decision support tool for scheduling maintenance operations.

A genetic algorithm approach for open-pit mine production scheduling

Directory of Open Access Journals (Sweden)

Aref Alipour

2017-06-01

Full Text Available In an Open-Pit Production Scheduling (OPPS problem, the goal is to determine the mining sequence of an orebody as a block model. In this article, linear programing formulation is used to aim this goal. OPPS problem is known as an NP-hard problem, so an exact mathematical model cannot be applied to solve in the real state. Genetic Algorithm (GA is a well-known member of evolutionary algorithms that widely are utilized to solve NP-hard problems. Herein, GA is implemented in a hypothetical Two-Dimensional (2D copper orebody model. The orebody is featured as two-dimensional (2D array of blocks. Likewise, counterpart 2D GA array was used to represent the OPPS problem’s solution space. Thereupon, the fitness function is defined according to the OPPS problem’s objective function to assess the solution domain. Also, new normalization method was used for the handling of block sequencing constraint. A numerical study is performed to compare the solutions of the exact and GA-based methods. It is shown that the gap between GA and the optimal solution by the exact method is less than % 5; hereupon GA is found to be efficiently in solving OPPS problem.

Hydrothermal self-scheduling problem in a day-ahead electricity market

International Nuclear Information System (INIS)

Bisanovic, Smajo; Dlakic, Muris; Hajro, Mensur

2008-01-01

This paper addresses the self-scheduling problem of determining the unit commitment status for power generation companies before submitting the hourly bids in a day-ahead market. The hydrothermal model is formulated as a deterministic optimization problem where expected profit is maximized using the 0/1 mixed-integer linear programming technique. This approach allows precise modelling of non-convex variable cost functions and non-linear start-up cost functions of thermal units, non-concave power-discharge characteristics of hydro units, ramp rate limits of thermal units and minimum up and down time constraints for both hydro and thermal units. Model incorporates long-term bilateral contracts with contracted power and price patterns, as well as forecasted market hourly prices for day-ahead auction. Solution is achieved using the homogeneous interior point method for linear programming as state of the art technique, with a branch and bound optimizer for integer programming. The effectiveness of the proposed model in optimizing the generation schedule is demonstrated through the case studies and their analysis. (author)

REORGANIZATION OF THE TECHNOLOGICAL FLOW AT CLOTHING COMPANY THROUGH THE PRODUCTION SCHEDULE

Directory of Open Access Journals (Sweden)

GHELBET Angela

2017-05-01

Full Text Available One of the main difficulties that light industry, namely clothing manufacturing sector faces today is inadequate organization of production processes. This is one of the most common and most serious obstacles in companies in the country, leading to low productivity. In order to reveal the causes of the problem and to develop solutions for change, it is proposed to conduct a study of a company facing difficulties in organizing the production process. It is important that the method/tool applied for the study is able to solve the problems occurring in the production process with minimum effort and maximum efficiency. The study was conducted within the process of manufacturing of a model of special clothing, namely clothing for doctors. The study was conducted within February-March 2016 at a clothing company of the Republic of Moldova. The study conducted shows that the transport issue in the technological flow can be solved by applying the production schedule, which eventually increases labor productivity by eliminating the time necessary to transport the labor object from one place of work to another, leading to economic growth considerable for the company. Following the assessments referring to the proposed improvements to organize the technological flow, there should be a 20% reduction in manufacturing time of a product, which will directly increase the revenue of the company by at least 10%.

A Gas Scheduling Optimization Model for Steel Enterprises

Directory of Open Access Journals (Sweden)

Niu Honghai

2017-01-01

Full Text Available Regarding the scheduling problems of steel enterprises, this research designs the gas scheduling optimization model according to the rules and priorities. Considering different features and the process changes of the gas unit in the process of actual production, the calculation model of process state and gas consumption soft measurement together with the rules of scheduling optimization is proposed to provide the dispatchers with real-time gas using status of each process, then help them to timely schedule and reduce the gas volume fluctuations. In the meantime, operation forewarning and alarm functions are provided to avoid the abnormal situation in the scheduling, which has brought about very good application effect in the actual scheduling and ensures the safety of the gas pipe network system and the production stability.

Scheduling the scheduling task : a time management perspective on scheduling

NARCIS (Netherlands)

Larco Martinelli, J.A.; Wiers, V.C.S.; Fransoo, J.C.

2013-01-01

Time is the most critical resource at the disposal of schedulers. Hence, an adequate management of time from the schedulers may impact positively on the scheduler’s productivity and responsiveness to uncertain scheduling environments. This paper presents a field study of how schedulers make use of

Car painting process scheduling with harmony search algorithm

Science.gov (United States)

Syahputra, M. F.; Maiyasya, A.; Purnamawati, S.; Abdullah, D.; Albra, W.; Heikal, M.; Abdurrahman, A.; Khaddafi, M.

2018-02-01

Automotive painting program in the process of painting the car body by using robot power, making efficiency in the production system. Production system will be more efficient if pay attention to scheduling of car order which will be done by considering painting body shape of car. Flow shop scheduling is a scheduling model in which the job-job to be processed entirely flows in the same product direction / path. Scheduling problems often arise if there are n jobs to be processed on the machine, which must be specified which must be done first and how to allocate jobs on the machine to obtain a scheduled production process. Harmony Search Algorithm is a metaheuristic optimization algorithm based on music. The algorithm is inspired by observations that lead to music in search of perfect harmony. This musical harmony is in line to find optimal in the optimization process. Based on the tests that have been done, obtained the optimal car sequence with minimum makespan value.

Comparative study of heuristics algorithms in solving flexible job shop scheduling problem with condition based maintenance

Directory of Open Access Journals (Sweden)

Yahong Zheng

2014-05-01

Full Text Available Purpose: This paper focuses on a classic optimization problem in operations research, the flexible job shop scheduling problem (FJSP, to discuss the method to deal with uncertainty in a manufacturing system.Design/methodology/approach: In this paper, condition based maintenance (CBM, a kind of preventive maintenance, is suggested to reduce unavailability of machines. Different to the simultaneous scheduling algorithm (SSA used in the previous article (Neale & Cameron,1979, an inserting algorithm (IA is applied, in which firstly a pre-schedule is obtained through heuristic algorithm and then maintenance tasks are inserted into the pre-schedule scheme.Findings: It is encouraging that a new better solution for an instance in benchmark of FJSP is obtained in this research. Moreover, factually SSA used in literature for solving normal FJSPPM (FJSP with PM is not suitable for the dynamic FJSPPM. Through application in the benchmark of normal FJSPPM, it is found that although IA obtains inferior results compared to SSA used in literature, it performs much better in executing speed.Originality/value: Different to traditional scheduling of FJSP, uncertainty of machines is taken into account, which increases the complexity of the problem. An inserting algorithm (IA is proposed to solve the dynamic scheduling problem. It is stated that the quality of the final result depends much on the quality of the pre-schedule obtained during the procedure of solving a normal FJSP. In order to find the best solution of FJSP, a comparative study of three heuristics is carried out, the integrated GA, ACO and ABC. In the comparative study, we find that GA performs best in the three heuristic algorithms. Meanwhile, a new better solution for an instance in benchmark of FJSP is obtained in this research.

JOINT OPTIMIZATION OF PRODUCTION PLANNING AND VEHICLE ROUTING PROBLEMS: A REVIEW OF EXISTING STRATEGIES

Directory of Open Access Journals (Sweden)

Marc Reimann

2014-05-01

Full Text Available Keen competition and increasingly demanding customers have forced companies to use their resources more efficiently and to integrate production and transportation planning. In the last few years more and more researchers have also focused on this challenging problem by trying to determine the complexity of the individual problems and then developing fast and robust algorithms to solve them. This paper reviews existing literature on integrated production and distribution decisions at the tactical and operational level, where the distribution part is modelled as some variation of the well-known Vehicle Routing Problem (VRP. The focus is thereby on problems that explicitly consider deliveries to multiple clients in a less-than-truckload fashion. In terms of the production decisions we distinguish in our review between tactical and operational production problems by considering lot-sizing/capacity allocation and scheduling models, respectively.

Information Flow Scheduling in Concurrent Multi-Product Development Based on DSM

Science.gov (United States)

Sun, Qing-Chao; Huang, Wei-Qiang; Jiang, Ying-Jie; Sun, Wei

2017-09-01

Multi-product collaborative development is adopted widely in manufacturing enterprise, while the present multi-project planning models don't take technical/data interactions of multiple products into account. To decrease the influence of technical/data interactions on project progresses, the information flow scheduling models based on the extended DSM is presented. Firstly, information dependencies are divided into four types: series, parallel, coupling and similar. Secondly, different types of dependencies are expressed as DSM units, and the extended DSM model is brought forward, described as a block matrix. Furthermore, the information flow scheduling methods is proposed, which involves four types of operations, where partitioning and clustering algorithm are modified from DSM for ensuring progress of high-priority project, merging and converting is the specific computation of the extended DSM. Finally, the information flow scheduling of two machine tools development is analyzed with example, and different project priorities correspond to different task sequences and total coordination cost. The proposed methodology provides a detailed instruction for information flow scheduling in multi-product development, with specially concerning technical/data interactions.

An Algorithm for the Weighted Earliness-Tardiness Unconstrained Project Scheduling Problem

Science.gov (United States)

Afshar Nadjafi, Behrouz; Shadrokh, Shahram

This research considers a project scheduling problem with the object of minimizing weighted earliness-tardiness penalty costs, taking into account a deadline for the project and precedence relations among the activities. An exact recursive method has been proposed for solving the basic form of this problem. We present a new depth-first branch and bound algorithm for extended form of the problem, which time value of money is taken into account by discounting the cash flows. The algorithm is extended with two bounding rules in order to reduce the size of the branch and bound tree. Finally, some test problems are solved and computational results are reported.

Performance evaluation of different types of particle representation procedures of Particle Swarm Optimization in Job-shop Scheduling Problems

Science.gov (United States)

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.

A Variable Interval Rescheduling Strategy for Dynamic Flexible Job Shop Scheduling Problem by Improved Genetic Algorithm

Directory of Open Access Journals (Sweden)

Lei Wang

2017-01-01

Full Text Available In real-world manufacturing systems, production scheduling systems are often implemented under random or dynamic events like machine failure, unexpected processing times, stochastic arrival of the urgent orders, cancellation of the orders, and so on. These dynamic events will lead the initial scheduling scheme to be nonoptimal and/or infeasible. Hence, appropriate dynamic rescheduling approaches are needed to overcome the dynamic events. In this paper, we propose a dynamic rescheduling method based on variable interval rescheduling strategy (VIRS to deal with the dynamic flexible job shop scheduling problem considering machine failure, urgent job arrival, and job damage as disruptions. On the other hand, an improved genetic algorithm (GA is proposed for minimizing makespan. In our improved GA, a mix of random initialization population by combining initialization machine and initialization operation with random initialization is designed for generating high-quality initial population. In addition, the elitist strategy (ES and improved population diversity strategy (IPDS are used to avoid falling into the local optimal solution. Experimental results for static and several dynamic events in the FJSP show that our method is feasible and effective.

The applicability of knowledge-based scheduling to the utilities industry

International Nuclear Information System (INIS)

Yoshimoto, G.; Gargan, R. Jr.; Duggan, P.

1992-01-01

The Electric Power Research Institute (EPRI), Nuclear Power Division, has identified the three major goals of high technology applications for nuclear power plants. These goals are to enhance power production through increasing power generation efficiency, to increase productivity of the operations, and to reduce the threats to the safety of the plant. Our project responds to the second goal by demonstrating that significant productivity increases can be achieved for outage maintenance operations based on existing knowledge-based scheduling technology. Its use can also mitigate threats to potential safety problems by means of the integration of risk assessment features into the scheduler. The scheduling approach uses advanced techniques enabling the automation of the routine scheduling decision process that previously was handled by people. The process of removing conflicts in scheduling is automated. This is achieved by providing activity representations that allow schedulers to express a variety of different scheduling constraints and by implementing scheduling mechanisms that simulate kinds of processes that humans use to find better solutions from a large number of possible solutions. This approach allows schedulers to express detailed constraints between activities and other activities, resources (material and personnel), and requirements that certain states exist for their execution. Our scheduler has already demonstrated its benefit to improving the shuttle processing flow management at Kennedy Space Center. Knowledge-based scheduling techniques should be examined by utilities industry researchers, developers, operators and management for application to utilities planning problems because of its great cost benefit potential. 4 refs., 4 figs

A Method of Flow-Shop Re-Scheduling Dealing with Variation of Productive Capacity

Directory of Open Access Journals (Sweden)

Kenzo KURIHARA

2005-02-01

Full Text Available We can make optimum scheduling results using various methods that are proposed by many researchers. However, it is very difficult to process the works on time without delaying the schedule. There are two major causes that disturb the planned optimum schedules; they are (1the variation of productive capacity, and (2the variation of products' quantities themselves. In this paper, we deal with the former variation, or productive capacities, at flow-shop works. When production machines in a shop go out of order at flow-shops, we cannot continue to operate the productions and we have to stop the production line. To the contrary, we can continue to operate the shops even if some workers absent themselves. Of course, in this case, the production capacities become lower, because workers need to move from a machine to another to overcome the shortage of workers and some shops cannot be operated because of the worker shortage. We developed a new re-scheduling method based on Branch-and Bound method. We proposed an equation for calculating the lower bound for our Branch-and Bound method in a practical time. Some evaluation experiments are done using practical data of real flow-shop works. We compared our results with those of another simple scheduling method, and we confirmed the total production time of our result is shorter than that of another method by 4%.

Heuristics methods for the flow shop scheduling problem with separated setup times

Directory of Open Access Journals (Sweden)

Marcelo Seido Nagano

2012-06-01

Full Text Available This paper deals with the permutation flow shop scheduling problem with separated machine setup times. As a result of an investigation on the problem characteristics, four heuristics methods are proposed with procedures of the construction sequencing solution by an analogy with the asymmetric traveling salesman problem with the objective of minimizing makespan. Experimental results show that one of the new heuristics methods proposed provide high quality solutions in comparisons with the evaluated methods considered in the literature.

Concept of Indoor 3D-Route UAV Scheduling System

DEFF Research Database (Denmark)

Khosiawan, Yohanes; Nielsen, Izabela Ewa; Do, Ngoc Ang Dung

2016-01-01

environment. On top of that, the multi-source productive best-first-search concept also supports efficient real-time scheduling in response to uncertain events. Without human intervention, the proposed work provides an automatic scheduling system for UAV routing problem in 3D indoor environment....

Exact and heuristic solution approaches for the Integrated Job Scheduling and Constrained Network Routing Problem

DEFF Research Database (Denmark)

Gamst, M.

2014-01-01

problem. The methods are computationally evaluated on test instances arising from telecommunications with up to 500 jobs and 500 machines. Results show that solving the integrated job scheduling and constrained network routing problem to optimality is very difficult. The exact solution approach performs......This paper examines the problem of scheduling a number of jobs on a finite set of machines such that the overall profit of executed jobs is maximized. Each job has a certain demand, which must be sent to the executing machine via constrained paths. A job cannot start before all its demands have...... arrived at the machine. Furthermore, two resource demand transmissions cannot use the same edge in the same time period. The problem has application in grid computing, where a number of geographically distributed machines work together for solving large problems. The machines are connected through...

Planning and scheduling for petroleum refineries using mathematical programming

Directory of Open Access Journals (Sweden)

Joly M.

2002-01-01

Full Text Available The objective of this paper is the development and solution of nonlinear and mixed-integer (MIP optimization models for real-world planning and scheduling problems in petroleum refineries. Firstly, we present a nonlinear planning model that represents a general refinery topology and allows implementation of nonlinear process models as well as blending relations. The optimization model is able to define new operating points, thus increasing the production of the more valuable products and simultaneously satisfying all specification constraints. The second part addresses scheduling problems in oil refineries, which are formulated as MIP optimization models and rely on both continuous and discrete time representations. Three practical applications closely related to the current refinery scenario are presented. The first one addresses the problem of crude oil inventory management of a refinery that receives several types of crude oil delivered exclusively by a single oil pipeline. Subsequently, two optimization models intended to define the optimal production policy, inventory control and distribution are proposed and solved for the fuel oil and asphalt plant. Finally, the planning model of Moro et al. (1998 is extended in order to sequence decisions at the scheduling level in the liquefied petroleum gas (LPG area for maximization of the production of petrochemical-grade propane and product delivery.

optimal scheduling of petroleum products distribution in nigeria

African Journals Online (AJOL)

MECHANICAL ENGINEERING

The study reveals that any variation in supply, demand and ... and storage depots for easy shipment of the products from ... The system should be robust yet simple to support routine ..... (10)Klabjan, D. Topics in airline crew scheduling and ...

Planning Risk-Based SQC Schedules for Bracketed Operation of Continuous Production Analyzers.

Science.gov (United States)

Westgard, James O; Bayat, Hassan; Westgard, Sten A

2018-02-01

To minimize patient risk, "bracketed" statistical quality control (SQC) is recommended in the new CLSI guidelines for SQC (C24-Ed4). Bracketed SQC requires that a QC event both precedes and follows (brackets) a group of patient samples. In optimizing a QC schedule, the frequency of QC or run size becomes an important planning consideration to maintain quality and also facilitate responsive reporting of results from continuous operation of high production analytic systems. Different plans for optimizing a bracketed SQC schedule were investigated on the basis of Parvin's model for patient risk and CLSI C24-Ed4's recommendations for establishing QC schedules. A Sigma-metric run size nomogram was used to evaluate different QC schedules for processes of different sigma performance. For high Sigma performance, an effective SQC approach is to employ a multistage QC procedure utilizing a "startup" design at the beginning of production and a "monitor" design periodically throughout production. Example QC schedules are illustrated for applications with measurement procedures having 6-σ, 5-σ, and 4-σ performance. Continuous production analyzers that demonstrate high σ performance can be effectively controlled with multistage SQC designs that employ a startup QC event followed by periodic monitoring or bracketing QC events. Such designs can be optimized to minimize the risk of harm to patients. © 2017 American Association for Clinical Chemistry.

A tabu-search heuristic for solving the multi-depot vehicle scheduling problem

Directory of Open Access Journals (Sweden)

Gilmar D'Agostini Oliveira Casalinho

2014-08-01

Full Text Available Currently the logistical problems are relying quite significantly on Operational Research in order to achieve greater efficiency in their operations. Among the problems related to the vehicles scheduling in a logistics system, the Multiple Depot Vehicle Scheduling Problem (MDVSP has been addressed in several studies. The MDVSP presupposes the existence of depots that affect the planning of sequences to which travel must be performed. Often, exact methods cannot solve large instances encountered in practice and in order to take them into account, several heuristic approaches are being developed. The aim of this study was thus to solve the MDVSP using a meta-heuristic based on tabu-search method. The main motivation for this work came from the indication that only recently the use of meta-heuristics is being applied to MDVSP context (Pepin et al. 2008 and, also, the limitations listed by Rohde (2008 in his study, which used the branch-and-bound in one of the steps of the heuristic presented to solve the problem, which has increased the time resolution. The research method for solving this problem was based on adaptations of traditional techniques of Operational Research, and provided resolutions presenting very competitive results for the MDVSP such as the cost of the objective function, number of vehicles used and computational time.

A stochastic simulation approach for production scheduling and ...

African Journals Online (AJOL)

International Journal of Engineering, Science and Technology ... management decisions related to production scheduling and investment planning. ... and indicate the value of promoting an information culture in the entire work forces. ... to support decision making in a BPR (Business Processes Re-engineering) scenario.

Task-specific shell for scheduling problems, ARES[sub TM]/SCH. Scheduling mondai muke task tokka shell ARES[sub TM]/SCH

Energy Technology Data Exchange (ETDEWEB)

Kojima, S; Narimatsu, K [Toshiba Corp., Tokyo (Japan)

1994-08-01

An Expert System (ES) Shell (developed by Toshiba Corp.) which applies to the scheduling of production plan and operation plan is introduced. It describes that this tool is equipped with flowchart editor and constraint condition editor which mention the knowledge related to scheduling method, and that the former expresses scheduling procedure knowledge in the form of flowchart by combining basic tasks prepared beforehand, and the latter expresses constraint conditions which should be satisfied by the schedule, and knowledge related to the priority order which should be considered in-between in the form of IF-THEN Rule which is very close to Japanese. In addition, the knowledge is equipped with knowledge debugging system which conducts debugging while executing the knowledge. It adds that by using this tool, the manhour required for the development and maintenance of ES can be reduced considerably. 2 refs., 3 figs.

Using Coevolution Genetic Algorithm with Pareto Principles to Solve Project Scheduling Problem under Duration and Cost Constraints

Directory of Open Access Journals (Sweden)

Alexandr Victorovich Budylskiy

2014-06-01

Full Text Available This article considers the multicriteria optimization approach using the modified genetic algorithm to solve the project-scheduling problem under duration and cost constraints. The work contains the list of choices for solving this problem. The multicriteria optimization approach is justified here. The study describes the Pareto principles, which are used in the modified genetic algorithm. We identify the mathematical model of the project-scheduling problem. We introduced the modified genetic algorithm, the ranking strategies, the elitism approaches. The article includes the example.

The Combinatorial Multi-Mode Resource Constrained Multi-Project Scheduling Problem

Directory of Open Access Journals (Sweden)

Denis Pinha

2016-11-01

Full Text Available This paper presents the formulation and solution of the Combinatorial Multi-Mode Resource Constrained Multi-Project Scheduling Problem. The focus of the proposed method is not on finding a single optimal solution, instead on presenting multiple feasible solutions, with cost and duration information to the project manager. The motivation for developing such an approach is due in part to practical situations where the definition of optimal changes on a regular basis. The proposed approach empowers the project manager to determine what is optimal, on a given day, under the current constraints, such as, change of priorities, lack of skilled worker. The proposed method utilizes a simulation approach to determine feasible solutions, under the current constraints. Resources can be non-consumable, consumable, or doubly constrained. The paper also presents a real-life case study dealing with scheduling of ship repair activities.

Evolutionary Hybrid Particle Swarm Optimization Algorithm for Solving NP-Hard No-Wait Flow Shop Scheduling Problems

Directory of Open Access Journals (Sweden)

Laxmi A. Bewoor

2017-10-01

Full Text Available The no-wait flow shop is a flowshop in which the scheduling of jobs is continuous and simultaneous through all machines without waiting for any consecutive machines. The scheduling of a no-wait flow shop requires finding an appropriate sequence of jobs for scheduling, which in turn reduces total processing time. The classical brute force method for finding the probabilities of scheduling for improving the utilization of resources may become trapped in local optima, and this problem can hence be observed as a typical NP-hard combinatorial optimization problem that requires finding a near optimal solution with heuristic and metaheuristic techniques. This paper proposes an effective hybrid Particle Swarm Optimization (PSO metaheuristic algorithm for solving no-wait flow shop scheduling problems with the objective of minimizing the total flow time of jobs. This Proposed Hybrid Particle Swarm Optimization (PHPSO algorithm presents a solution by the random key representation rule for converting the continuous position information values of particles to a discrete job permutation. The proposed algorithm initializes population efficiently with the Nawaz-Enscore-Ham (NEH heuristic technique and uses an evolutionary search guided by the mechanism of PSO, as well as simulated annealing based on a local neighborhood search to avoid getting stuck in local optima and to provide the appropriate balance of global exploration and local exploitation. Extensive computational experiments are carried out based on Taillard’s benchmark suite. Computational results and comparisons with existing metaheuristics show that the PHPSO algorithm outperforms the existing methods in terms of quality search and robustness for the problem considered. The improvement in solution quality is confirmed by statistical tests of significance.

Efficient bounding schemes for the two-center hybrid flow shop scheduling problem with removal times.

Science.gov (United States)

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.

A Recovery Model for Production Scheduling: Combination of Disruption Management and Internet of Things

Directory of Open Access Journals (Sweden)

Yang Jiang

2016-01-01

Full Text Available It is difficult to generate the new schedule effectively for minimizing the negative impact when an unanticipated disruption occurs after a subset of tasks has been finished in production scheduling. In such cases, continuing with the original schedule may not be optimal or feasible. Based on disruption management and Internet of things (IoT, this study designs a real-time status analyzer to identify the disruption and propose a recovery model to deal with the disruption. The computational result proves that our algorithm is competitive with the existing heuristics. Furthermore, due to the tradeoff between all participators (mainly including customers, managers of production enterprise, and workers involved in production scheduling, our model is more effective than the total rescheduling and right-shift rescheduling.

Proposing New Heuristic Approaches for Preventive Maintenance Scheduling

Directory of Open Access Journals (Sweden)

majid Esmailian

2013-08-01

Full Text Available The purpose of preventive maintenance management is to perform a series of tasks that prevent or minimize production breakdowns and improve reliability of production facilities. An important objective of preventive maintenance management is to minimize downtime of production facilities. In order to accomplish this objective, personnel should efficiently allocate resources and determine an effective maintenance schedule. Gopalakrishnan (1997 developed a mathematical model and four heuristic approaches to solve the preventive maintenance scheduling problem of assigning skilled personnel to work with tasks that require a set of corresponding skills. However, there are several limitations in the prior work in this area of research. The craft combination problem has not been solved because the craft combination is assumed as given. The craft combination problem concerns the computation of all combinations of assigning multi skilled workers to accomplishment of a particular task. In fact, determining craft combinations is difficult because of the exponential number of craft combinations that are possible. This research provides a heuristic approach for determining the craft combination and four new heuristic approach solution for the preventive maintenance scheduling problem with multi skilled workforce constraints. In order to examine the new heuristic approach and to compare the new heuristic approach with heuristic approach of Gopalakrishnan (1997, 81 standard problems have been generated based on the criterion suggested by from Gopalakrishnan (1997. The average solution quality (SQ of the new heuristic approaches is 1.86% and in old heuristic approaches is 8.32%. The solution time of new heuristic approaches are shorter than old heuristic approaches. The solution time of new heuristic approaches is 0.78 second and old heuristic approaches is 6.43 second, but the solution time of mathematical model provided by Gopalakrishnan (1997 is 152 second. �

Meta-heuristic algorithms for parallel identical machines scheduling problem with weighted late work criterion and common due date.

Science.gov (United States)

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.

Capacity optimization and scheduling of a multiproduct manufacturing facility for biotech products.

Science.gov (United States)

Shaik, Munawar A; Dhakre, Ankita; Rathore, Anurag S; Patil, Nitin

2014-01-01

A general mathematical framework has been proposed in this work for scheduling of a multiproduct and multipurpose facility involving manufacturing of biotech products. The specific problem involves several batch operations occurring in multiple units involving fixed processing time, unlimited storage policy, transition times, shared units, and deterministic and fixed data in the given time horizon. The different batch operations are modeled using state-task network representation. Two different mathematical formulations are proposed based on discrete- and continuous-time representations leading to a mixed-integer linear programming model which is solved using General Algebraic Modeling System software. A case study based on a real facility is presented to illustrate the potential and applicability of the proposed models. The continuous-time model required less number of events and has a smaller problem size compared to the discrete-time model. © 2014 American Institute of Chemical Engineers.

Analysis of Issues for Project Scheduling by Multiple, Dispersed Schedulers (distributed Scheduling) and Requirements for Manual Protocols and Computer-based Support

Science.gov (United States)

Richards, Stephen F.

1991-01-01

Although computerized operations have significant gains realized in many areas, one area, scheduling, has enjoyed few benefits from automation. The traditional methods of industrial engineering and operations research have not proven robust enough to handle the complexities associated with the scheduling of realistic problems. To address this need, NASA has developed the computer-aided scheduling system (COMPASS), a sophisticated, interactive scheduling tool that is in wide-spread use within NASA and the contractor community. Therefore, COMPASS provides no explicit support for the large class of problems in which several people, perhaps at various locations, build separate schedules that share a common pool of resources. This research examines the issue of distributing scheduling, as applied to application domains characterized by the partial ordering of tasks, limited resources, and time restrictions. The focus of this research is on identifying issues related to distributed scheduling, locating applicable problem domains within NASA, and suggesting areas for ongoing research. The issues that this research identifies are goals, rescheduling requirements, database support, the need for communication and coordination among individual schedulers, the potential for expert system support for scheduling, and the possibility of integrating artificially intelligent schedulers into a network of human schedulers.

A Local Search Algorithm for the Flow Shop Scheduling Problem with Release Dates

Directory of Open Access Journals (Sweden)

Tao Ren

2015-01-01

Full Text Available This paper discusses the flow shop scheduling problem to minimize the makespan with release dates. By resequencing the jobs, a modified heuristic algorithm is obtained for handling large-sized problems. Moreover, based on some properties, a local search scheme is provided to improve the heuristic to gain high-quality solution for moderate-sized problems. A sequence-independent lower bound is presented to evaluate the performance of the algorithms. A series of simulation results demonstrate the effectiveness of the proposed algorithms.

Scheduling with Time Lags

NARCIS (Netherlands)

X. Zhang (Xiandong)

2010-01-01

textabstractScheduling is essential when activities need to be allocated to scarce resources over time. Motivated by the problem of scheduling barges along container terminals in the Port of Rotterdam, this thesis designs and analyzes algorithms for various on-line and off-line scheduling problems

78 FR 55099 - Established Aggregate Production Quotas for Schedule I and II Controlled Substances and...

Science.gov (United States)

2013-09-09

... aggregate production quotas, an additional 25% of the estimated medical, scientific, and research needs as... Production Quotas for Schedule I and II Controlled Substances and Established Assessment of Annual Needs for... initial 2014 aggregate production quotas for controlled substances in Schedules I and II of the Controlled...

Variable Neighbourhood Search and Mathematical Programming for Just-in-Time Job-Shop Scheduling Problem

Directory of Open Access Journals (Sweden)

Sunxin Wang

2014-01-01

Full Text Available This paper presents a combination of variable neighbourhood search and mathematical programming to minimize the sum of earliness and tardiness penalty costs of all operations for just-in-time job-shop scheduling problem (JITJSSP. Unlike classical E/T scheduling problem with each job having its earliness or tardiness penalty cost, each operation in this paper has its earliness and tardiness penalties, which are paid if the operation is completed before or after its due date. Our hybrid algorithm combines (i a variable neighbourhood search procedure to explore the huge feasible solution spaces efficiently by alternating the swap and insertion neighbourhood structures and (ii a mathematical programming model to optimize the completion times of the operations for a given solution in each iteration procedure. Additionally, a threshold accepting mechanism is proposed to diversify the local search of variable neighbourhood search. Computational results on the 72 benchmark instances show that our algorithm can obtain the best known solution for 40 problems, and the best known solutions for 33 problems are updated.

A Priority Rule-Based Heuristic for Resource Investment Project Scheduling Problem with Discounted Cash Flows and Tardiness Penalties

Directory of Open Access Journals (Sweden)

Amir Abbas Najafi

2009-01-01

Full Text Available Resource investment problem with discounted cash flows (RIPDCFs is a class of project scheduling problem. In RIPDCF, the availability levels of the resources are considered decision variables, and the goal is to find a schedule such that the net present value of the project cash flows optimizes. In this paper, we consider a new RIPDCF in which tardiness of project is permitted with defined penalty. We mathematically formulated the problem and developed a heuristic method to solve it. The results of the performance analysis of the proposed method show an effective solution approach to the problem.

Solving a mixed-integer linear programming model for a multi-skilled project scheduling problem by simulated annealing

Directory of Open Access Journals (Sweden)

H Kazemipoor

2012-04-01

Full Text Available A multi-skilled project scheduling problem (MSPSP has been generally presented to schedule a project with staff members as resources. Each activity in project network requires different skills and also staff members have different skills, too. This causes the MSPSP becomes a special type of a multi-mode resource-constrained project scheduling problem (MM-RCPSP with a huge number of modes. Given the importance of this issue, in this paper, a mixed integer linear programming for the MSPSP is presented. Due to the complexity of the problem, a meta-heuristic algorithm is proposed in order to find near optimal solutions. To validate performance of the algorithm, results are compared against exact solutions solved by the LINGO solver. The results are promising and show that optimal or near-optimal solutions are derived for small instances and good solutions for larger instances in reasonable time.

Developing optimal nurses work schedule using integer programming

Science.gov (United States)

Shahidin, Ainon Mardhiyah; Said, Mohd Syazwan Md; Said, Noor Hizwan Mohamad; Sazali, Noor Izatie Amaliena

2017-08-01

Time management is the art of arranging, organizing and scheduling one's time for the purpose of generating more effective work and productivity. Scheduling is the process of deciding how to commit resources between varieties of possible tasks. Thus, it is crucial for every organization to have a good work schedule for their staffs. The job of Ward nurses at hospitals runs for 24 hours every day. Therefore, nurses will be working using shift scheduling. This study is aimed to solve the nurse scheduling problem at an emergency ward of a private hospital. A 7-day work schedule for 7 consecutive weeks satisfying all the constraints set by the hospital will be developed using Integer Programming. The work schedule for the nurses obtained gives an optimal solution where all the constraints are being satisfied successfully.

Modeling Nurse Scheduling Problem Using 0-1 Goal Programming A Case Study Of Tafo Government Hospital Kumasi-Ghana

Directory of Open Access Journals (Sweden)

Wallace Agyei

2015-03-01

Full Text Available Abstract The problem of scheduling nurses at the Out-Patient Department OPD at Tafo Government Hospital Kumasi Ghana is presented. Currently the schedules are prepared by head nurse who performs this difficult and time consuming task by hand. Due to the existence of many constraints the resulting schedule usually does not guarantee the fairness of distribution of work. The problem was formulated as 0-1goal programming model with the of objective of evenly balancing the workload among nurses and satisfying their preferences as much as possible while complying with the legal and working regulations.. The developed model was then solved using LINGO14.0 software. The resulting schedules based on 0-1goal programming model balanced the workload in terms of the distribution of shift duties fairness in terms of the number of consecutive night duties and satisfied the preferences of the nurses. This is an improvement over the schedules done manually.

Improved teaching-learning-based and JAYA optimization algorithms for solving flexible flow shop scheduling problems

Science.gov (United States)

Buddala, Raviteja; Mahapatra, Siba Sankar

2017-11-01

Flexible flow shop (or a hybrid flow shop) scheduling problem is an extension of classical flow shop scheduling problem. In a simple flow shop configuration, a job having `g' operations is performed on `g' operation centres (stages) with each stage having only one machine. If any stage contains more than one machine for providing alternate processing facility, then the problem becomes a flexible flow shop problem (FFSP). FFSP which contains all the complexities involved in a simple flow shop and parallel machine scheduling problems is a well-known NP-hard (Non-deterministic polynomial time) problem. Owing to high computational complexity involved in solving these problems, it is not always possible to obtain an optimal solution in a reasonable computation time. To obtain near-optimal solutions in a reasonable computation time, a large variety of meta-heuristics have been proposed in the past. However, tuning algorithm-specific parameters for solving FFSP is rather tricky and time consuming. To address this limitation, teaching-learning-based optimization (TLBO) and JAYA algorithm are chosen for the study because these are not only recent meta-heuristics but they do not require tuning of algorithm-specific parameters. Although these algorithms seem to be elegant, they lose solution diversity after few iterations and get trapped at the local optima. To alleviate such drawback, a new local search procedure is proposed in this paper to improve the solution quality. Further, mutation strategy (inspired from genetic algorithm) is incorporated in the basic algorithm to maintain solution diversity in the population. Computational experiments have been conducted on standard benchmark problems to calculate makespan and computational time. It is found that the rate of convergence of TLBO is superior to JAYA. From the results, it is found that TLBO and JAYA outperform many algorithms reported in the literature and can be treated as efficient methods for solving the FFSP.

A Bee Colony Optimization Approach for Mixed Blocking Constraints Flow Shop Scheduling Problems

Directory of Open Access Journals (Sweden)

Mostafa Khorramizadeh

2015-01-01

Full Text Available The flow shop scheduling problems with mixed blocking constraints with minimization of makespan are investigated. The Taguchi orthogonal arrays and path relinking along with some efficient local search methods are used to develop a metaheuristic algorithm based on bee colony optimization. In order to compare the performance of the proposed algorithm, two well-known test problems are considered. Computational results show that the presented algorithm has comparative performance with well-known algorithms of the literature, especially for the large sized problems.

The Green Ship Routing and Scheduling Problem (GSRSP): A conceptual approach

DEFF Research Database (Denmark)

Kontovas, Christos A.

2014-01-01

Recent reviews of the literature on ship routing and scheduling note the increased attention to environmental issues. This is an area of paramount importance for international shipping and will be even more so in the future. This short communication is motivated by the increasing attention......) based on existing formulations and highlights all the important parameters of the problem. (C) 2014 Elsevier Ltd. All rights reserved....

Comparing Mixed & Integer Programming vs. Constraint Programming by solving Job-Shop Scheduling Problems

Directory of Open Access Journals (Sweden)

Renata Melo e Silva de Oliveira

2015-03-01

Full Text Available Scheduling is a key factor for operations management as well as for business success. From industrial Job-shop Scheduling problems (JSSP, many optimization challenges have emerged since de 1960s when improvements have been continuously required such as bottlenecks allocation, lead-time reductions and reducing response time to requests.  With this in perspective, this work aims to discuss 3 different optimization models for minimizing Makespan. Those 3 models were applied on 17 classical problems of examples JSSP and produced different outputs.  The first model resorts on Mixed and Integer Programming (MIP and it resulted on optimizing 60% of the studied problems. The other models were based on Constraint Programming (CP and approached the problem in two different ways: a model CP1 is a standard IBM algorithm whereof restrictions have an interval structure that fail to solve 53% of the proposed instances, b Model CP-2 approaches the problem with disjunctive constraints and optimized 88% of the instances. In this work, each model is individually analyzed and then compared considering: i Optimization success performance, ii Computational processing time, iii Greatest Resource Utilization and, iv Minimum Work-in-process Inventory. Results demonstrated that CP-2 presented best results on criteria i and ii, but MIP was superior on criteria iii and iv and those findings are discussed at the final section of this work.

New scheduling rules for a dynamic flexible flow line problem with sequence-dependent setup times

Science.gov (United States)

Kia, Hamidreza; Ghodsypour, Seyed Hassan; Davoudpour, Hamid

2017-09-01

In the literature, the application of multi-objective dynamic scheduling problem and simple priority rules are widely studied. Although these rules are not efficient enough due to simplicity and lack of general insight, composite dispatching rules have a very suitable performance because they result from experiments. In this paper, a dynamic flexible flow line problem with sequence-dependent setup times is studied. The objective of the problem is minimization of mean flow time and mean tardiness. A 0-1 mixed integer model of the problem is formulated. Since the problem is NP-hard, four new composite dispatching rules are proposed to solve it by applying genetic programming framework and choosing proper operators. Furthermore, a discrete-event simulation model is made to examine the performances of scheduling rules considering four new heuristic rules and the six adapted heuristic rules from the literature. It is clear from the experimental results that composite dispatching rules that are formed from genetic programming have a better performance in minimization of mean flow time and mean tardiness than others.

SIMULTANEOUS SCHEDULING AND OPERATIONAL OPTIMIZATION OF MULTIPRODUCT, CYCLIC CONTINUOUS PLANTS

Directory of Open Access Journals (Sweden)

A. Alle

2002-03-01

Full Text Available The problems of scheduling and optimization of operational conditions in multistage, multiproduct continuous plants with intermediate storage are simultaneously addressed. An MINLP model, called TSPFLOW, which is based on the TSP formulation for product sequencing, is proposed to schedule the operation of such plants. TSPFLOW yields a one-order-of-magnitude CPU time reduction as well as the solution of instances larger than those formerly reported (Pinto and Grossmann, 1994. Secondly, processing rates and yields are introduced as additional optimization variables in order to state the simultaneous problem of scheduling with operational optimization. Results show that trade-offs are very complex and that the development of a straightforward (rule of thumb method to optimally schedule the operation is less effective than the proposed approach.

SIMULTANEOUS SCHEDULING AND OPERATIONAL OPTIMIZATION OF MULTIPRODUCT, CYCLIC CONTINUOUS PLANTS

Directory of Open Access Journals (Sweden)

Alle A.

2002-01-01

Full Text Available The problems of scheduling and optimization of operational conditions in multistage, multiproduct continuous plants with intermediate storage are simultaneously addressed. An MINLP model, called TSPFLOW, which is based on the TSP formulation for product sequencing, is proposed to schedule the operation of such plants. TSPFLOW yields a one-order-of-magnitude CPU time reduction as well as the solution of instances larger than those formerly reported (Pinto and Grossmann, 1994. Secondly, processing rates and yields are introduced as additional optimization variables in order to state the simultaneous problem of scheduling with operational optimization. Results show that trade-offs are very complex and that the development of a straightforward (rule of thumb method to optimally schedule the operation is less effective than the proposed approach.

Hybrid Metaheuristics for Solving a Fuzzy Single Batch-Processing Machine Scheduling Problem

Directory of Open Access Journals (Sweden)

S. Molla-Alizadeh-Zavardehi

2014-01-01

Full Text Available 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.

A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan

International Nuclear Information System (INIS)

Lian Zhigang; Gu Xingsheng; Jiao Bin

2008-01-01

It is well known that the flow-shop scheduling problem (FSSP) is a branch of production scheduling and is NP-hard. Now, many different approaches have been applied for permutation flow-shop scheduling to minimize makespan, but current algorithms even for moderate size problems cannot be solved to guarantee optimality. Some literatures searching PSO for continuous optimization problems are reported, but papers searching PSO for discrete scheduling problems are few. In this paper, according to the discrete characteristic of FSSP, a novel particle swarm optimization (NPSO) algorithm is presented and successfully applied to permutation flow-shop scheduling to minimize makespan. Computation experiments of seven representative instances (Taillard) based on practical data were made, and comparing the NPSO with standard GA, we obtain that the NPSO is clearly more efficacious than standard GA for FSSP to minimize makespan

Constraint-based scheduling

Science.gov (United States)

Zweben, Monte

1993-01-01

The GERRY scheduling system developed by NASA Ames with assistance from the Lockheed Space Operations Company, and the Lockheed Artificial Intelligence Center, uses a method called constraint-based iterative repair. Using this technique, one encodes both hard rules and preference criteria into data structures called constraints. GERRY repeatedly attempts to improve schedules by seeking repairs for violated constraints. The system provides a general scheduling framework which is being tested on two NASA applications. The larger of the two is the Space Shuttle Ground Processing problem which entails the scheduling of all the inspection, repair, and maintenance tasks required to prepare the orbiter for flight. The other application involves power allocation for the NASA Ames wind tunnels. Here the system will be used to schedule wind tunnel tests with the goal of minimizing power costs. In this paper, we describe the GERRY system and its application to the Space Shuttle problem. We also speculate as to how the system would be used for manufacturing, transportation, and military problems.

Operational Excellence through Schedule Optimization and Production Simulation of Application Specific Integrated Circuits.

Energy Technology Data Exchange (ETDEWEB)

Flory, John Andrew [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Padilla, Denise D. [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Gauthier, John H. [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Zwerneman, April Marie [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Miller, Steven P [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States)

2016-05-01

Upcoming weapon programs require an aggressive increase in Application Specific Integrated Circuit (ASIC) production at Sandia National Laboratories (SNL). SNL has developed unique modeling and optimization tools that have been instrumental in improving ASIC production productivity and efficiency, identifying optimal operational and tactical execution plans under resource constraints, and providing confidence in successful mission execution. With ten products and unprecedented levels of demand, a single set of shared resources, highly variable processes, and the need for external supplier task synchronization, scheduling is an integral part of successful manufacturing. The scheduler uses an iterative multi-objective genetic algorithm and a multi-dimensional performance evaluator. Schedule feasibility is assessed using a discrete event simulation (DES) that incorporates operational uncertainty, variability, and resource availability. The tools provide rapid scenario assessments and responses to variances in the operational environment, and have been used to inform major equipment investments and workforce planning decisions in multiple SNL facilities.

Scheduling by positional completion times: analysis of a two-stage flow shop problem with a batching machine

NARCIS (Netherlands)

Hoogeveen, J.A.; Velde, van de S.L.

1998-01-01

We consider a scheduling problem introduced by Ahmadi et al., Batching and scheduling jobs on batch and discrete processors, Operation Research 40 (1992) 750–763, in which each job has to be prepared before it can be processed. The preparation is performed by a batching machine; it can prepare at

A Two-Stage Stochastic Mixed-Integer Programming Approach to the Smart House Scheduling Problem

Science.gov (United States)

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.

Nuclear Power Plant Preventive Maintenance Scheduling Problem with Fuzziness

International Nuclear Information System (INIS)

Abass, S.A.; Abdallah, A.S.

2013-01-01

Maintenance activity is regarded as the most important key factor for the safety, reliability and economy of a nuclear power plant. Preventive maintenance refers to set of planned activities which include nondestructive testing and periodic inspection as well as maintenance. In this paper, we address the problem of nuclear power plant preventive maintenance scheduling with uncertainty. The uncertainty will be represented by fuzzy parameters. The problem is how to determine the period for which generating units of an electric system should be taken off line for planned preventive maintenance over specific time horizon. Preventive maintenance activity of a nuclear power plant is an important issue as it designed to extend the plant life . It is more required to review the maintenance not only from the view point of safety and reliability but also economy. Preventive maintenance program exists to ensure that nuclear safety significant equipment will function when it is supposed to. Also this problem is extremely important because a failure in a power plant may cause a general breakdown in an electric network. In this paper a mixed integer programming model is used to express this problem. In proposed model power demand is taken as fuzzy parameters. A case study is provided to demonstrate the efficiency of the proposed model.

On Several Fundamental Problems of Optimization, Estimation, and Scheduling in Wireless Communications

Science.gov (United States)

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

10 CFR 170.21 - Schedule of fees for production and utilization facilities, review of standard referenced design...

Science.gov (United States)

2010-01-01

... 10 Energy 2 2010-01-01 2010-01-01 false Schedule of fees for production and utilization facilities, review of standard referenced design approvals, special projects, inspections and import and export... AMENDED Schedule of Fees § 170.21 Schedule of fees for production and utilization facilities, review of...

Greedy and metaheuristics for the offline scheduling problem in grid computing

DEFF Research Database (Denmark)

Gamst, Mette

In grid computing a number of geographically distributed resources connected through a wide area network, are utilized as one computations unit. The NP-hard offline scheduling problem in grid computing consists of assigning jobs to resources in advance. In this paper, five greedy heuristics and two....... All heuristics solve instances with up to 2000 jobs and 1000 resources, thus the results are useful both with respect to running times and to solution values....

Analyzing Integrated Cost-Schedule Risk for Complex Product Systems R&D Projects

Directory of Open Access Journals (Sweden)

Zhe Xu

2014-01-01

Full Text Available The vast majority of the research efforts in project risk management tend to assess cost risk and schedule risk independently. However, project cost and time are related in reality and the relationship between them should be analyzed directly. We propose an integrated cost and schedule risk assessment model for complex product systems R&D projects. Graphical evaluation review technique (GERT, Monte Carlo simulation, and probability distribution theory are utilized to establish the model. In addition, statistical analysis and regression analysis techniques are employed to analyze simulation outputs. Finally, a complex product systems R&D project as an example is modeled by the proposed approach and the simulation outputs are analyzed to illustrate the effectiveness of the risk assessment model. It seems that integrating cost and schedule risk assessment can provide more reliable risk estimation results.

Proposed algorithm to improve job shop production scheduling using ant colony optimization method

Science.gov (United States)

Pakpahan, Eka KA; Kristina, Sonna; Setiawan, Ari

2017-12-01

This paper deals with the determination of job shop production schedule on an automatic environment. On this particular environment, machines and material handling system are integrated and controlled by a computer center where schedule were created and then used to dictate the movement of parts and the operations at each machine. This setting is usually designed to have an unmanned production process for a specified interval time. We consider here parts with various operations requirement. Each operation requires specific cutting tools. These parts are to be scheduled on machines each having identical capability, meaning that each machine is equipped with a similar set of cutting tools therefore is capable of processing any operation. The availability of a particular machine to process a particular operation is determined by the remaining life time of its cutting tools. We proposed an algorithm based on the ant colony optimization method and embedded them on matlab software to generate production schedule which minimize the total processing time of the parts (makespan). We test the algorithm on data provided by real industry and the process shows a very short computation time. This contributes a lot to the flexibility and timelines targeted on an automatic environment.

Distributed continuous energy scheduling for dynamic virtual power plants

International Nuclear Information System (INIS)

Niesse, Astrid

2015-01-01

This thesis presents DynaSCOPE as distributed control method for continuous energy scheduling for dynamic virtual power plants (DVPP). DVPPs aggregate the flexibility of distributed energy units to address current energy markets. As an extension of the Virtual Power Plant concept they show high dynamics in aggregation and operation of energy units. Whereas operation schedules are set up for all energy units in a day-ahead planning procedure, incidents may render these schedules infeasible during execution, like deviation from prognoses or outages. Thus, a continuous scheduling process is needed to ensure product fulfillment. With DynaSCOPE, software agents representing single energy units solve this problem in a completely distributed heuristic approach. Using a stepped concept, several damping mechanisms are applied to allow minimum disturbance while continuously trying to fulfill the product as contracted at the market.

Research and Applications of Shop Scheduling Based on Genetic Algorithms

Directory of Open Access Journals (Sweden)

Hang ZHAO

Full Text Available ABSTRACT Shop Scheduling is an important factor affecting the efficiency of production, efficient scheduling method and a research and application for optimization technology play an important role for manufacturing enterprises to improve production efficiency, reduce production costs and many other aspects. Existing studies have shown that improved genetic algorithm has solved the limitations that existed in the genetic algorithm, the objective function is able to meet customers' needs for shop scheduling, and the future research should focus on the combination of genetic algorithm with other optimized algorithms. In this paper, in order to overcome the shortcomings of early convergence of genetic algorithm and resolve local minimization problem in search process,aiming at mixed flow shop scheduling problem, an improved cyclic search genetic algorithm is put forward, and chromosome coding method and corresponding operation are given.The operation has the nature of inheriting the optimal individual ofthe previous generation and is able to avoid the emergence of local minimum, and cyclic and crossover operation and mutation operation can enhance the diversity of the population and then quickly get the optimal individual, and the effectiveness of the algorithm is validated. Experimental results show that the improved algorithm can well avoid the emergency of local minimum and is rapid in convergence.

Automated Planning and Scheduling for Space Mission Operations

Science.gov (United States)

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.

A matheuristic approach for solving the Integrated Timetabling and Vehicle Scheduling Problem

DEFF Research Database (Denmark)

Fonseca, Joao Filipe Paiva; Larsen, Allan; van der Hurk, Evelien

between different trips. We consider transfers between bus trips scheduled by the model, but also transfers to other fixed lines that intersect the lines considered in the IT-VSP. We present a MIP formulation of the IT-VSP able to solve small instances of the problem, and a matheuristic approach that uses...... the compact MIP to solve larger instances of the problem. The idea is to iteratively solve restricted versions of the MIP selecting at each step a subset of trips where modifications are allowed, while all other trips remain fixed. The performance of the proposed matheuristic is shown on a case study...

Solving scheduling problems by untimed model checking. The clinical chemical analyser case study

NARCIS (Netherlands)

Margaria, T.; Wijs, Anton J.; Massink, M.; van de Pol, Jan Cornelis; Bortnik, Elena M.

2009-01-01

In this article, we show how scheduling problems can be modelled in untimed process algebra, by using special tick actions. A minimal-cost trace leading to a particular action, is one that minimises the number of tick steps. As a result, we can use any (timed or untimed) model checking tool to find

A Formal Product-Line Engineering Approach for Schedulers

NARCIS (Netherlands)

Orhan, Güner; Aksit, Mehmet; Rensink, Arend; Jololian, Leon; Robbins, David E.; Fernandes, Steven L.

2017-01-01

Scheduling techniques have been applied to a large category of software systems, such as, processor scheduling in operating systems, car scheduling in elevator systems, facility scheduling at airports, antenna scheduling in radar systems, scheduling of events, control signals and data in

Robust and Flexible Scheduling with Evolutionary Computation

DEFF Research Database (Denmark)

Jensen, Mikkel T.

Over the last ten years, there have been numerous applications of evolutionary algorithms to a variety of scheduling problems. Like most other research on heuristic scheduling, the primary aim of the research has been on deterministic formulations of the problems. This is in contrast to real world...... scheduling problems which are usually not deterministic. Usually at the time the schedule is made some information about the problem and processing environment is available, but this information is uncertain and likely to change during schedule execution. Changes frequently encountered in scheduling...... environments include machine breakdowns, uncertain processing times, workers getting sick, materials being delayed and the appearance of new jobs. These possible environmental changes mean that a schedule which was optimal for the information available at the time of scheduling can end up being highly...

Athabasca--special report No. 1, we are progressing on schedule

Energy Technology Data Exchange (ETDEWEB)

Moss, A E

1966-09-01

Since April of 1964 when the government of Alberta gave permission for the production of crude oil from the Athabasca Tar Sands, construction of a $240 million oil sands venture has been progressing according to schedule. This plant will be capable of processing 45,000 bbl of crude oil per day and will require the mining of approximately 135,000 tons of material per day. The scheduled completion date for this project is Sept. 1967. This huge project consists of the construction of various plant units and service facilities, preparation of the mine for production, construction of a highway and a multi- million dollar bridge, and the design and construction of a 16-in. pipeline 266 miles in length. A shortage of experienced engineers, supervisors, and skilled tradesmen has been the largest problem. In spite of the many problems encountered, approximately 50% of the construction has now been completed and the plant will be completed on schedule.

Solving a large-scale precedence constrained scheduling problem with elastic jobs using tabu search

DEFF Research Database (Denmark)

Pedersen, C.R.; Rasmussen, R.V.; Andersen, Kim Allan

2007-01-01

This paper presents a solution method for minimizing makespan of a practical large-scale scheduling problem with elastic jobs. The jobs are processed on three servers and restricted by precedence constraints, time windows and capacity limitations. We derive a new method for approximating the server...... exploitation of the elastic jobs and solve the problem using a tabu search procedure. Finding an initial feasible solution is in general -complete, but the tabu search procedure includes a specialized heuristic for solving this problem. The solution method has proven to be very efficient and leads...

Scheduling theory, algorithms, and systems

CERN Document Server

Pinedo, Michael L

2016-01-01

This new edition of the well-established text Scheduling: Theory, Algorithms, and Systems provides an up-to-date coverage of important theoretical models in the scheduling literature as well as important scheduling problems that appear in the real world. The accompanying website includes supplementary material in the form of slide-shows from industry as well as movies that show actual implementations of scheduling systems. The main structure of the book, as per previous editions, consists of three parts. The first part focuses on deterministic scheduling and the related combinatorial problems. The second part covers probabilistic scheduling models; in this part it is assumed that processing times and other problem data are random and not known in advance. The third part deals with scheduling in practice; it covers heuristics that are popular with practitioners and discusses system design and implementation issues. All three parts of this new edition have been revamped, streamlined, and extended. The reference...

The Home Care Crew Scheduling Problem: Preference-based visit clustering and temporal dependencies

DEFF Research Database (Denmark)

Rasmussen, Matias Sevel; Justesen, Tor Fog; Dohn, Anders Høeg

2012-01-01

In the Home Care Crew Scheduling Problem a staff of home carers has to be assigned a number of visits to patients’ homes, such that the overall service level is maximised. The problem is a generalisation of the vehicle routing problem with time windows. Required travel time between visits and time...... preference constraints. The algorithm is tested both on real-life problem instances and on generated test instances inspired by realistic settings. The use of the specialised branching scheme on real-life problems is novel. The visit clustering decreases run times significantly, and only gives a loss...... windows of the visits must be respected. The challenge when assigning visits to home carers lies in the existence of soft preference constraints and in temporal dependencies between the start times of visits.We model the problem as a set partitioning problem with side constraints and develop an exact...

Quality Improvement, Inventory Management, Lead Time Reduction and Production Scheduling in High-Mix Manufacturing Environments

Science.gov (United States)

2017-01-13

Quality Improvement , Inventory Management, Lead Time Reduction and Production Scheduling in High-mix Manufacturing Environments by Sean Daigle B.S...Mechanical Engineering Chairman, Department Committee on Graduate Theses 2 Quality Improvement , Inventory Management, Lead Time Reduction and... Production Scheduling in High-mix Manufacturing Environments by Sean Daigle Submitted to the Department of Mechanical Engineering on January 13, 2017, in

Implementation Learning and Forgetting Curve to Scheduling in Garment Industry

Science.gov (United States)

Muhamad Badri, Huda; Deros, Baba Md; Syahri, M.; Saleh, Chairul; Fitria, Aninda

2016-02-01

The learning curve shows the relationship between time and the cumulative number of units produced which using the mathematical description on the performance of workers in performing repetitive works. The problems of this study is level differences in the labors performance before and after the break which affects the company's production scheduling. The study was conducted in the garment industry, which the aims is to predict the company production scheduling using the learning curve and forgetting curve. By implementing the learning curve and forgetting curve, this paper contributes in improving the labors performance that is in line with the increase in maximum output 3 hours productive before the break are 15 unit product with learning curve percentage in the company is 93.24%. Meanwhile, the forgetting curve improving maximum output 3 hours productive after the break are 11 unit product with the percentage of forgetting curve in the company is 92.96%. Then, the obtained 26 units product on the productive hours one working day is used as the basic for production scheduling.

Comparison of Multiobjective Evolutionary Algorithms for Operations Scheduling under Machine Availability Constraints

Directory of Open Access Journals (Sweden)

M. Frutos

2013-01-01

Full Text Available 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.

Study on multi-objective flexible job-shop scheduling problem considering energy consumption

Directory of Open Access Journals (Sweden)

Zengqiang Jiang

2014-06-01

Full Text Available Purpose: Build a multi-objective Flexible Job-shop Scheduling Problem(FJSP optimization model, in which the makespan, processing cost, energy consumption and cost-weighted processing quality are considered, then Design a Modified Non-dominated Sorting Genetic Algorithm (NSGA-II based on blood variation for above scheduling model.Design/methodology/approach: A multi-objective optimization theory based on Pareto optimal method is used in carrying out the optimization model. NSGA-II is used to solve the model.Findings: By analyzing the research status and insufficiency of multi-objective FJSP, Find that the difference in scheduling will also have an effect on energy consumption in machining process and environmental emissions. Therefore, job-shop scheduling requires not only guaranteeing the processing quality, time and cost, but also optimizing operation plan of machines and minimizing energy consumption.Originality/value: A multi-objective FJSP optimization model is put forward, in which the makespan, processing cost, energy consumption and cost-weighted processing quality are considered. According to above model, Blood-Variation-based NSGA-II (BVNSGA-II is designed. In which, the chromosome mutation rate is determined after calculating the blood relationship between two cross chromosomes, crossover and mutation strategy of NSGA-II is optimized and the prematurity of population is overcome. Finally, the performance of the proposed model and algorithm is evaluated through a case study, and the results proved the efficiency and feasibility of the proposed model and algorithm.

Formulation for less master production schedule instability under rolling horizon

OpenAIRE

Herrera , Carlos; Thomas , André

2009-01-01

International audience; In Manufacturing Planning and Control Systems, the Master Production Schedule (MPS) makes a link between tactical and operational levels, taking into account information provided by end items, demand forecast as well as Sales and Operations Planning (S&OP) suggestions. Therefore, MPS plays an important role to maintain an adequate customers service level and an efficient production system. In a rolling planning horizon, MPS is periodically computed over whole operation...

Gain and exposure scheduling to compensate for photorefractive neural-network weight decay

Science.gov (United States)

Goldstein, Adam A.; Petrisor, Gregory C.; Jenkins, B. Keith

1995-03-01

A gain and exposure schedule that theoretically eliminates the effect of photorefractive weight decay for the general class of outer-product neural-network learning algorithms (e.g., backpropagation, Widrow-Hoff, perceptron) is presented. This schedule compensates for photorefractive diffraction-efficiency decay by iteratively increasing the spatial-light-modulator transfer function gain and decreasing the weight-update exposure time. Simulation results for the scheduling procedure, as applied to backpropagation learning for the exclusive-OR problem, show improved learning performance compared with results for networks trained without scheduling.

Flow shop scheduling with heterogeneous workers

OpenAIRE

Benavides, Alexander J.; Ritt, Marcus; Miralles Insa, Cristóbal Javier

2014-01-01

We propose an extension to the flow shop scheduling problem named Heterogeneous Flow Shop Scheduling Problem (Het-FSSP), where two simultaneous issues have to be resolved: finding the best worker assignment to the workstations, and solving the corresponding scheduling problem. This problem is motivated by Sheltered Work centers for Disabled, whose main objective is the labor integration of persons with disabilities, an important aim not only for these centers but for any company d...

National contingency plan product schedule data base

International Nuclear Information System (INIS)

Putukian, J.; Hiltabrand, R.R.

1993-01-01

During oil spills there are always proposals by the technical community and industry to use chemical agents to help in oil spill cleanups. Federal Clean Water Act regulations require that any chemical agents that the federal on-scene coordinator (FOSC) wants to use for oil cleanup be listed on the US Environmental Protection Agency (EPA) National Contingency Plan (NCP) Product Schedule. Chemical countermeasures are among the most controversial, complex, and time-critical issues facing decision-making officials choosing response methods to use on coastal oil spills. There are situations in which dispersants are likely to be one of the most appropriate counter-measure strategies. Dispersants are most effective when applied to fresh oil, and their effectiveness dramatically decreases as the oil weathers, which can begin in as little as 24 hours. To logistically implement dispersant use, a decision would need to be made within roughly the first 4 hours after the release. Most of the information that the FOSC needs to make the determination to use a specific chemical agent exists in manuals, EPA bulletins, and the published literature. This information is not in an easy-to-use format under field emergency conditions. Hence the need to collect and disseminate the information in an automated data base. The sources for the information in this data base are the following. Published results of tests performed by Environment Canada; EPA bulletins associated with the NCP Product Schedule; Published results of tests by the chemical industry. The data base resides on a Macintosh computer and contains information about 70 NCP products, including dispersants, surface collecting agents, and biological additives. It contains information on physical properties, toxicity, heavy metal content, safety precautions, use conditions, etc

An Optimizing Space Data-Communications Scheduling Method and Algorithm with Interference Mitigation, Generalized for a Broad Class of Optimization Problems

Science.gov (United States)

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

SOFIA's Choice: Automating the Scheduling of Airborne Observations

Science.gov (United States)

Frank, Jeremy; Norvig, Peter (Technical Monitor)

1999-01-01

This paper describes the problem of scheduling observations for an airborne telescope. Given a set of prioritized observations to choose from, and a wide range of complex constraints governing legitimate choices and orderings, how can we efficiently and effectively create a valid flight plan which supports high priority observations? This problem is quite different from scheduling problems which are routinely solved automatically in industry. For instance, the problem requires making choices which lead to other choices later, and contains many interacting complex constraints over both discrete and continuous variables. Furthermore, new types of constraints may be added as the fundamental problem changes. As a result of these features, this problem cannot be solved by traditional scheduling techniques. The problem resembles other problems in NASA and industry, from observation scheduling for rovers and other science instruments to vehicle routing. The remainder of the paper is organized as follows. In 2 we describe the observatory in order to provide some background. In 3 we describe the problem of scheduling a single flight. In 4 we compare flight planning and other scheduling problems and argue that traditional techniques are not sufficient to solve this problem. We also mention similar complex scheduling problems which may benefit from efforts to solve this problem. In 5 we describe an approach for solving this problem based on research into a similar problem, that of scheduling observations for a space-borne probe. In 6 we discuss extensions of the flight planning problem as well as other problems which are similar to flight planning. In 7 we conclude and discuss future work.

Flexible Job-Shop Scheduling with Dual-Resource Constraints to Minimize Tardiness Using Genetic Algorithm

Science.gov (United States)

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.

Multiagent scheduling method with earliness and tardiness objectives in flexible job shops.

Science.gov (United States)

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.

Integrated Harvest and Distribution Scheduling with Time Windows of Perishable Agri-Products in One-Belt and One-Road Context

Directory of Open Access Journals (Sweden)

Yiping Jiang

2018-05-01

Full Text Available The unique characteristics of perishable agri-products are a short lifespan and rapid quality deterioration. This establishes the need to significantly reduce the time from harvest to distribution. These features require reducing the processing time from harvest to distribution to being as short as possible. In this study, we focus on an integrated perishable agri-products scheduling problem that combines harvest and distribution simultaneously, with the purpose of reducing processing time and quality decay. We propose this problem as a mixed integer nonlinear programming model (MINLP to optimize the harvest time and the vehicle routing to consumers, and this MINIP is formulated as a vehicle routing problem with time windows (VRPTW. We introduce a big M method to transform the nonlinear model into a linear model, then apply CPLEX to solve the transformed model. Numerical experiments and sensitive analysis are conducted to verify the efficiency of the proposed model and to provide managerial insights.

Planning and Scheduling of Airline Operations

Directory of Open Access Journals (Sweden)

İlkay ORHAN

2010-02-01

Full Text Available The Turkish Civil Aviation sector has grown at a rate of 53 % between the years 2002-2008 owing to countrywide economical developments and some removed restrictions in the aviation field. Successful international companies in the sector use advanced computer-supported solution methods for their planning and scheduling problems. These methods have been providing significant competitive advantages to those companies. There are four major scheduling and planning problems in the airline sector: flight scheduling, aircraft scheduling, crew scheduling and disruptions management. These aforementioned scheduling and planning problems faced by all airline companies in the airline sector were examined in detail. Studies reveal that companies using the advanced methods might gain significant cost reductions. However, even then, the time required for solving large scale problems may not satisfy the decision quality desired by decision makers. In such cases, using modern decision methods integrated with advanced technologies offer companies an opportunity for significant cost-advantages.

Application of Operational Research Techniques in Operating Room Scheduling Problems: Literature Overview

Directory of Open Access Journals (Sweden)

Şeyda Gür

2018-01-01

Full Text Available Increased healthcare costs are pushing hospitals to reduce costs and increase the quality of care. Operating rooms are the most important source of income and expense for hospitals. Therefore, the hospital management focuses on the effectiveness of schedules and plans. This study includes analyses of recent research on operating room scheduling and planning. Most studies in the literature, from 2000 to the present day, were evaluated according to patient characteristics, performance measures, solution techniques used in the research, the uncertainty of the problem, applicability of the research, and the planning strategy to be dealt within the solution. One hundred seventy studies were examined in detail, after scanning the Emerald, Science Direct, JSTOR, Springer, Taylor and Francis, and Google Scholar databases. To facilitate the identification of these studies, they are grouped according to the different criteria of concern and then, a detailed overview is presented.

Skipping Strategy (SS) for Initial Population of Job-Shop Scheduling Problem

Science.gov (United States)

Abdolrazzagh-Nezhad, M.; Nababan, E. B.; Sarim, H. M.

2018-03-01

Initial population in job-shop scheduling problem (JSSP) is an essential step to obtain near optimal solution. Techniques used to solve JSSP are computationally demanding. Skipping strategy (SS) is employed to acquire initial population after sequence of job on machine and sequence of operations (expressed in Plates-jobs and mPlates-jobs) are determined. The proposed technique is applied to benchmark datasets and the results are compared to that of other initialization techniques. It is shown that the initial population obtained from the SS approach could generate optimal solution.

Maximizing Total Profit in Two-agent Problem of Order Acceptance and Scheduling

Directory of Open Access Journals (Sweden)

Mohammad Reisi-Nafchi

2017-03-01

Full Text Available In competitive markets, attracting potential customers and keeping current customers is a survival condition for each company. So, paying attention to the requests of customers is important and vital. In this paper, the problem of order acceptance and scheduling has been studied, in which two types of customers or agents compete in a single machine environment. The objective is maximizing sum of the total profit of first agent's accepted orders and the total revenue of second agent. Therefore, only the first agent has penalty and its penalty function is lateness and the second agent's orders have a common due date and this agent does not accept any tardy order. To solve the problem, a mathematical programming, a heuristic algorithm and a pseudo-polynomial dynamic programming algorithm are proposed. Computational results confirm the ability of solving all problem instances up to 70 orders size optimally and also 93.12% of problem instances up to 150 orders size by dynamic programming.

An efficient genetic algorithm for a hybrid flow shop scheduling problem with time lags and sequence-dependent setup time

Directory of Open Access Journals (Sweden)

Farahmand-Mehr Mohammad

2014-01-01

Full Text Available In this paper, a hybrid flow shop scheduling problem with a new approach considering time lags and sequence-dependent setup time in realistic situations is presented. Since few works have been implemented in this field, the necessity of finding better solutions is a motivation to extend heuristic or meta-heuristic algorithms. This type of production system is found in industries such as food processing, chemical, textile, metallurgical, printed circuit board, and automobile manufacturing. A mixed integer linear programming (MILP model is proposed to minimize the makespan. Since this problem is known as NP-Hard class, a meta-heuristic algorithm, named Genetic Algorithm (GA, and three heuristic algorithms (Johnson, SPTCH and Palmer are proposed. Numerical experiments of different sizes are implemented to evaluate the performance of presented mathematical programming model and the designed GA in compare to heuristic algorithms and a benchmark algorithm. Computational results indicate that the designed GA can produce near optimal solutions in a short computational time for different size problems.

Using Improved Ant Colony Algorithm to Investigate EMU Circulation Scheduling Problem

Directory of Open Access Journals (Sweden)

Yu Zhou

2014-01-01

Full Text Available High-speed railway is one of the most important ways to solve the long-standing travel difficulty problem in China. However, due to the high acquisition and maintenance cost, it is impossible for decision-making departments to purchase enough EMUs to satisfy the explosive travel demand. Therefore, there is an urgent need to study how to utilize EMU more efficiently and reduce costs in the case of completing a given task in train diagram. In this paper, an EMU circulation scheduling model is built based on train diagram constraints, maintenance constraints, and so forth; in the model solving process, an improved ACA algorithm has been designed. A case study is conducted to verify the feasibility of the model. Moreover, contrast tests have been carried out to compare the efficiency between the improved ACA and the traditional approaches. The results reveal that improved ACA method can solve the model with less time and the quality of each representative index is much better, which means that efficiency of the improved ACA method is higher and better scheduling scheme can be obtained.

Solving and Interpreting Large-scale Harvest Scheduling Problems by Duality and Decomposition

OpenAIRE

Berck, Peter; Bible, Thomas

1982-01-01

This paper presents a solution to the forest planning problem that takes advantage of both the duality of linear programming formulations currently being used for harvest scheduling and the characteristics of decomposition inherent in the forest land class-relationship. The subproblems of decomposition, defined as the dual, can be solved in a simple, recursive fashion. In effect, such a technique reduces the computational burden in terms of time and computer storage as compared to the traditi...

Solving a large-scale precedence constrained scheduling problem with elastic jobs using tabu search

DEFF Research Database (Denmark)

Pedersen, C.R.; Rasmussen, R.V.; Andersen, Kim Allan

2007-01-01

exploitation of the elastic jobs and solve the problem using a tabu search procedure. Finding an initial feasible solution is in general -complete, but the tabu search procedure includes a specialized heuristic for solving this problem. The solution method has proven to be very efficient and leads......This paper presents a solution method for minimizing makespan of a practical large-scale scheduling problem with elastic jobs. The jobs are processed on three servers and restricted by precedence constraints, time windows and capacity limitations. We derive a new method for approximating the server...... to a significant decrease in makespan compared to the strategy currently implemented....

A Hybrid Multiobjective Evolutionary Approach for Flexible Job-Shop Scheduling Problems

Directory of Open Access Journals (Sweden)

Jian Xiong

2012-01-01

Full Text Available This paper addresses multiobjective flexible job-shop scheduling problem (FJSP with three simultaneously considered objectives: minimizing makespan, minimizing total workload, and minimizing maximal workload. A hybrid multiobjective evolutionary approach (H-MOEA is developed to solve the problem. According to the characteristic of FJSP, a modified crowding distance measure is introduced to maintain the diversity of individuals. In the proposed H-MOEA, well-designed chromosome representation and genetic operators are developed for FJSP. Moreover, a local search procedure based on critical path theory is incorporated in H-MOEA to improve the convergence ability of the algorithm. Experiment results on several well-known benchmark instances demonstrate the efficiency and stability of the proposed algorithm. The comparison with other recently published approaches validates that H-MOEA can obtain Pareto-optimal solutions with better quality and/or diversity.

Scheduling stochastic two-machine flow shop problems to minimize expected makespan

Directory of Open Access Journals (Sweden)

Mehdi Heydari

2013-07-01

Full Text Available During the past few years, despite tremendous contribution on deterministic flow shop problem, there are only limited number of works dedicated on stochastic cases. This paper examines stochastic scheduling problems in two-machine flow shop environment for expected makespan minimization where processing times of jobs are normally distributed. Since jobs have stochastic processing times, to minimize the expected makespan, the expected sum of the second machine’s free times is minimized. In other words, by minimization waiting times for the second machine, it is possible to reach the minimum of the objective function. A mathematical method is proposed which utilizes the properties of the normal distributions. Furthermore, this method can be used as a heuristic method for other distributions, as long as the means and variances are available. The performance of the proposed method is explored using some numerical examples.

An Optimization of Manufacturing Systems using a Feedback Control Scheduling Model

Science.gov (United States)

Ikome, John M.; Kanakana, Grace M.

2018-03-01

In complex production system that involves multiple process, unplanned disruption often turn to make the entire production system vulnerable to a number of problems which leads to customer’s dissatisfaction. However, this problem has been an ongoing problem that requires a research and methods to streamline the entire process or develop a model that will address it, in contrast to this, we have developed a feedback scheduling model that can minimize some of this problem and after a number of experiment, it shows that some of this problems can be eliminated if the correct remedial actions are implemented on time.

Two phase genetic algorithm for vehicle routing and scheduling problem with cross-docking and time windows considering customer satisfaction

Science.gov (United States)

Baniamerian, Ali; Bashiri, Mahdi; Zabihi, Fahime

2018-03-01

Cross-docking is a new warehousing policy in logistics which is widely used all over the world and attracts many researchers attention to study about in last decade. In the literature, economic aspects has been often studied, while one of the most significant factors for being successful in the competitive global market is improving quality of customer servicing and focusing on customer satisfaction. In this paper, we introduce a vehicle routing and scheduling problem with cross-docking and time windows in a three-echelon supply chain that considers customer satisfaction. A set of homogeneous vehicles collect products from suppliers and after consolidation process in the cross-dock, immediately deliver them to customers. A mixed integer linear programming model is presented for this problem to minimize transportation cost and early/tardy deliveries with scheduling of inbound and outbound vehicles to increase customer satisfaction. A two phase genetic algorithm (GA) is developed for the problem. For investigating the performance of the algorithm, it was compared with exact and lower bound solutions in small and large-size instances, respectively. Results show that there are at least 86.6% customer satisfaction by the proposed method, whereas customer satisfaction in the classical model is at most 33.3%. Numerical examples results show that the proposed two phase algorithm could achieve optimal solutions in small-size instances. Also in large-size instances, the proposed two phase algorithm could achieve better solutions with less gap from the lower bound in less computational time in comparison with the classic GA.

Preemptive scheduling with rejection

NARCIS (Netherlands)

Hoogeveen, H.; Skutella, M.; Woeginger, Gerhard

2003-01-01

We consider the problem of preemptively scheduling a set of n jobs on m (identical, uniformly related, or unrelated) parallel machines. The scheduler may reject a subset of the jobs and thereby incur job-dependent penalties for each rejected job, and he must construct a schedule for the remaining

Preemptive scheduling with rejection

NARCIS (Netherlands)

Hoogeveen, J.A.; Skutella, M.; Woeginger, G.J.; Paterson, M.

2000-01-01

We consider the problem of preemptively scheduling a set of n jobs on m (identical, uniformly related, or unrelated) parallel machines. The scheduler may reject a subset of the jobs and thereby incur job-dependent penalties for each rejected job, and he must construct a schedule for the remaining

Artificial intelligence approaches to astronomical observation scheduling

Science.gov (United States)

Johnston, Mark D.; Miller, Glenn

1988-01-01

Automated scheduling will play an increasing role in future ground- and space-based observatory operations. Due to the complexity of the problem, artificial intelligence technology currently offers the greatest potential for the development of scheduling tools with sufficient power and flexibility to handle realistic scheduling situations. Summarized here are the main features of the observatory scheduling problem, how artificial intelligence (AI) techniques can be applied, and recent progress in AI scheduling for Hubble Space Telescope.

Multi-objective flexible job shop scheduling problem using variable neighborhood evolutionary algorithm

Science.gov (United States)

Wang, Chun; Ji, Zhicheng; Wang, Yan

2017-07-01

In this paper, multi-objective flexible job shop scheduling problem (MOFJSP) was studied with the objects to minimize makespan, total workload and critical workload. A variable neighborhood evolutionary algorithm (VNEA) was proposed to obtain a set of Pareto optimal solutions. First, two novel crowded operators in terms of the decision space and object space were proposed, and they were respectively used in mating selection and environmental selection. Then, two well-designed neighborhood structures were used in local search, which consider the problem characteristics and can hold fast convergence. Finally, extensive comparison was carried out with the state-of-the-art methods specially presented for solving MOFJSP on well-known benchmark instances. The results show that the proposed VNEA is more effective than other algorithms in solving MOFJSP.

Maximizing the nurses' preferences in nurse scheduling problem: mathematical modeling and a meta-heuristic algorithm

Science.gov (United States)

Jafari, Hamed; Salmasi, Nasser

2015-09-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.

Single-machine scheduling with release dates, due dates and family setup times

NARCIS (Netherlands)

Schutten, Johannes M.J.; van de Velde, S.L.; van de Velde, S.L.; Zijm, Willem H.M.

1996-01-01

We address the NP-hard problem of scheduling n independent jobs with release dates, due dates, and family setup times on a single machine to minimize the maximum lateness. This problem arises from the constant tug-of-war going on in manufacturing between efficient production and delivery

Retail sales of scheduled listed chemical products; self-certification of regulated sellers of scheduled listed chemical products. Interim final rule with request for comment.

Science.gov (United States)

2006-09-26

In March 2006, the President signed the Combat Methamphetamine Epidemic Act of 2005, which establishes new requirements for retail sales of over-the-counter (nonprescription) products containing the List I chemicals ephedrine, pseudoephedrine, and phenylpropanolamine. The three chemicals can be used to manufacture methamphetamine illegally. DEA is promulgating this rule to incorporate the statutory provisions and make its regulations consistent with the new requirements. This action establishes daily and 30-day limits on the sales of scheduled listed chemical products to individuals and requires recordkeeping on most sales.

Simulation of textile manufacturing processes for planning, scheduling, and quality control purposes

Science.gov (United States)

Cropper, A. E.; Wang, Z.

1995-08-01

Simulation, as a management information tool, has been applied to engineering manufacture and assembly operations. The application of the principles to textile manufacturing (fiber to fabric) is discussed. The particular problems and solutions in applying the simulation software package to the yarn production processes are discussed with an indication of how the software achieves the production schedule. The system appears to have application in planning, scheduling, and quality assurance. The latter being a result of the traceability possibilities through a process involving mixing and splitting of material.

Parallel Machine Scheduling with Batch Delivery to Two Customers

Directory of Open Access Journals (Sweden)

Xueling Zhong

2015-01-01

Full Text Available In some make-to-order supply chains, the manufacturer needs to process and deliver products for customers at different locations. To coordinate production and distribution operations at the detailed scheduling level, we study a parallel machine scheduling model with batch delivery to two customers by vehicle routing method. In this model, the supply chain consists of a processing facility with m parallel machines and two customers. A set of jobs containing n1 jobs from customer 1 and n2 jobs from customer 2 are first processed in the processing facility and then delivered to the customers directly without intermediate inventory. The problem is to find a joint schedule of production and distribution such that the tradeoff between maximum arrival time of the jobs and total distribution cost is minimized. The distribution cost of a delivery shipment consists of a fixed charge and a variable cost proportional to the total distance of the route taken by the shipment. We provide polynomial time heuristics with worst-case performance analysis for the problem. If m=2 and (n1-b(n2-b<0, we propose a heuristic with worst-case ratio bound of 3/2, where b is the capacity of the delivery shipment. Otherwise, the worst-case ratio bound of the heuristic we propose is 2-2/(m+1.

15 CFR 714.3 - Advance declaration requirements for additionally planned production of Schedule 3 chemicals.

Science.gov (United States)

2010-01-01

... COMMERCE CHEMICAL WEAPONS CONVENTION REGULATIONS ACTIVITIES INVOLVING SCHEDULE 3 CHEMICALS § 714.3 Advance... 15 Commerce and Foreign Trade 2 2010-01-01 2010-01-01 false Advance declaration requirements for additionally planned production of Schedule 3 chemicals. 714.3 Section 714.3 Commerce and Foreign Trade...

Schedule Analytics

Science.gov (United States)

2016-04-30

Warfare, Naval Sea Systems Command Acquisition Cycle Time : Defining the Problem David Tate, Institute for Defense Analyses Schedule Analytics Jennifer...research was comprised of the following high- level steps :  Identify and review primary data sources 1...research. However, detailed reviews of the OMB IT Dashboard data revealed that schedule data is highly aggregated. Program start date and program end date

Sequencing, lot sizing and scheduling in job shops: the common cycle approach

NARCIS (Netherlands)

Ouenniche, J.; Boctor, F.F.

1998-01-01

This paper deals with the multi-product, finite horizon, static demand, sequencing, lot sizing and scheduling problem in a job shop environment where the objective is to minimize the sum of setup and inventory holding costs while satisfying the demand with no backlogging. To solve this problem, we

Single-machine scheduling with release dates, due dates, and family setup times

NARCIS (Netherlands)

J.M.J. Schutten (Marco); S.L. van de Velde (Steef); W.H.M. Zijm

1996-01-01

textabstractWe address the NP-hard problem of scheduling n independent jobs with release dates, due dates, and family setup times on a single machine to minimize the maximum lateness. This problem arises from the constant tug-of-war going on in manufacturing between efficient production and delivery

A reactive decision-making approach to reduce instability in a Master Production Schedule

OpenAIRE

Herrera , Carlos; Belmokhtar Berraf , Sana; Thomas , André; Parada , Victor

2016-01-01

International audience; One of the primary factors that impact the master production scheduling performance is demand fluctuation, which leads to frequently updated decisions, thereby causing instability. Consequently, global cost deteriorates, and productivity decreases. A reactive approach based on parametric mixed-integer programming is proposed that aims to provide a set of plans such that a compromise between production cost and production stability is ensured. Several stability measures...

Processing time tolerance-based ACO algorithm for solving job-shop scheduling problem

Science.gov (United States)

Luo, Yabo; Waden, Yongo P.

2017-06-01

Ordinarily, Job Shop Scheduling Problem (JSSP) is known as NP-hard problem which has uncertainty and complexity that cannot be handled by a linear method. Thus, currently studies on JSSP are concentrated mainly on applying different methods of improving the heuristics for optimizing the JSSP. However, there still exist many problems for efficient optimization in the JSSP, namely, low efficiency and poor reliability, which can easily trap the optimization process of JSSP into local optima. Therefore, to solve this problem, a study on Ant Colony Optimization (ACO) algorithm combined with constraint handling tactics is carried out in this paper. Further, the problem is subdivided into three parts: (1) Analysis of processing time tolerance-based constraint features in the JSSP which is performed by the constraint satisfying model; (2) Satisfying the constraints by considering the consistency technology and the constraint spreading algorithm in order to improve the performance of ACO algorithm. Hence, the JSSP model based on the improved ACO algorithm is constructed; (3) The effectiveness of the proposed method based on reliability and efficiency is shown through comparative experiments which are performed on benchmark problems. Consequently, the results obtained by the proposed method are better, and the applied technique can be used in optimizing JSSP.

Intelligent discrete particle swarm optimization for multiprocessor task scheduling problem

Directory of Open Access Journals (Sweden)

S Sarathambekai

2017-03-01

Full Text Available Discrete particle swarm optimization is one of the most recently developed population-based meta-heuristic optimization algorithm in swarm intelligence that can be used in any discrete optimization problems. This article presents a discrete particle swarm optimization algorithm to efficiently schedule the tasks in the heterogeneous multiprocessor systems. All the optimization algorithms share a common algorithmic step, namely population initialization. It plays a significant role because it can affect the convergence speed and also the quality of the final solution. The random initialization is the most commonly used method in majority of the evolutionary algorithms to generate solutions in the initial population. The initial good quality solutions can facilitate the algorithm to locate the optimal solution or else it may prevent the algorithm from finding the optimal solution. Intelligence should be incorporated to generate the initial population in order to avoid the premature convergence. This article presents a discrete particle swarm optimization algorithm, which incorporates opposition-based technique to generate initial population and greedy algorithm to balance the load of the processors. Make span, flow time, and reliability cost are three different measures used to evaluate the efficiency of the proposed discrete particle swarm optimization algorithm for scheduling independent tasks in distributed systems. Computational simulations are done based on a set of benchmark instances to assess the performance of the proposed algorithm.

Hybrid Particle Swarm Optimization for Hybrid Flowshop Scheduling Problem with Maintenance Activities

Science.gov (United States)

Li, Jun-qing; Pan, Quan-ke; Mao, Kun

2014-01-01

A hybrid algorithm which combines particle swarm optimization (PSO) and iterated local search (ILS) is proposed for solving the hybrid flowshop scheduling (HFS) problem with preventive maintenance (PM) activities. In the proposed algorithm, different crossover operators and mutation operators are investigated. In addition, an efficient multiple insert mutation operator is developed for enhancing the searching ability of the algorithm. Furthermore, an ILS-based local search procedure is embedded in the algorithm to improve the exploitation ability of the proposed algorithm. The detailed experimental parameter for the canonical PSO is tuning. The proposed algorithm is tested on the variation of 77 Carlier and Néron's benchmark problems. Detailed comparisons with the present efficient algorithms, including hGA, ILS, PSO, and IG, verify the efficiency and effectiveness of the proposed algorithm. PMID:24883414

Hybrid Particle Swarm Optimization for Hybrid Flowshop Scheduling Problem with Maintenance Activities

Directory of Open Access Journals (Sweden)

Jun-qing Li

2014-01-01

Full Text Available A hybrid algorithm which combines particle swarm optimization (PSO and iterated local search (ILS is proposed for solving the hybrid flowshop scheduling (HFS problem with preventive maintenance (PM activities. In the proposed algorithm, different crossover operators and mutation operators are investigated. In addition, an efficient multiple insert mutation operator is developed for enhancing the searching ability of the algorithm. Furthermore, an ILS-based local search procedure is embedded in the algorithm to improve the exploitation ability of the proposed algorithm. The detailed experimental parameter for the canonical PSO is tuning. The proposed algorithm is tested on the variation of 77 Carlier and Néron’s benchmark problems. Detailed comparisons with the present efficient algorithms, including hGA, ILS, PSO, and IG, verify the efficiency and effectiveness of the proposed algorithm.

Hybrid particle swarm optimization for hybrid flowshop scheduling problem with maintenance activities.

Science.gov (United States)

Li, Jun-qing; Pan, Quan-ke; Mao, Kun

2014-01-01

A hybrid algorithm which combines particle swarm optimization (PSO) and iterated local search (ILS) is proposed for solving the hybrid flowshop scheduling (HFS) problem with preventive maintenance (PM) activities. In the proposed algorithm, different crossover operators and mutation operators are investigated. In addition, an efficient multiple insert mutation operator is developed for enhancing the searching ability of the algorithm. Furthermore, an ILS-based local search procedure is embedded in the algorithm to improve the exploitation ability of the proposed algorithm. The detailed experimental parameter for the canonical PSO is tuning. The proposed algorithm is tested on the variation of 77 Carlier and Néron's benchmark problems. Detailed comparisons with the present efficient algorithms, including hGA, ILS, PSO, and IG, verify the efficiency and effectiveness of the proposed algorithm.

A hybrid Constraint Programming/Mixed Integer Programming framework for the preventive signaling maintenance crew scheduling problem

DEFF Research Database (Denmark)

Pour, Shahrzad M.; Drake, John H.; Ejlertsen, Lena Secher

2017-01-01

A railway signaling system is a complex and interdependent system which should ensure the safe operation of trains. We introduce and address a mixed integer optimisation model for the preventive signal maintenance crew scheduling problem in the Danish railway system. The problem contains many...... to feed as ‘warm start’ solutions to a Mixed Integer Programming (MIP) solver for further optimisation. We apply the CP/MIP framework to a section of the Danish rail network and benchmark our results against both direct application of a MIP solver and modelling the problem as a Constraint Optimisation...

Asymptotic Analysis of SPTA-Based Algorithms for No-Wait Flow Shop Scheduling Problem with Release Dates

Directory of Open Access Journals (Sweden)

Tao Ren

2014-01-01

Full Text Available We address the scheduling problem for a no-wait flow shop to optimize total completion time with release dates. With the tool of asymptotic analysis, we prove that the objective values of two SPTA-based algorithms converge to the optimal value for sufficiently large-sized problems. To further enhance the performance of the SPTA-based algorithms, an improvement scheme based on local search is provided for moderate scale problems. New lower bound is presented for evaluating the asymptotic optimality of the algorithms. Numerical simulations demonstrate the effectiveness of the proposed algorithms.

Asymptotic analysis of SPTA-based algorithms for no-wait flow shop scheduling problem with release dates.

Science.gov (United States)

Ren, Tao; Zhang, Chuan; Lin, Lin; Guo, Meiting; Xie, Xionghang

2014-01-01

We address the scheduling problem for a no-wait flow shop to optimize total completion time with release dates. With the tool of asymptotic analysis, we prove that the objective values of two SPTA-based algorithms converge to the optimal value for sufficiently large-sized problems. To further enhance the performance of the SPTA-based algorithms, an improvement scheme based on local search is provided for moderate scale problems. New lower bound is presented for evaluating the asymptotic optimality of the algorithms. Numerical simulations demonstrate the effectiveness of the proposed algorithms.

Solving a More Flexible Home Health Care Scheduling and Routing Problem with Joint Patient and Nursing Staff Selection

Directory of Open Access Journals (Sweden)

Jamal Abdul Nasir

2018-01-01

Full Text Available Development of an efficient and effective home health care (HHC service system is a quite recent and challenging task for the HHC firms. This paper aims to develop an HHC service system in the perspective of long-term economic sustainability as well as operational efficiency. A more flexible mixed-integer linear programming (MILP model is formulated by incorporating the dynamic arrival and departure of patients along with the selection of new patients and nursing staff. An integrated model is proposed that jointly addresses: (i patient selection; (ii nurse hiring; (iii nurse to patient assignment; and (iv scheduling and routing decisions in a daily HHC planning problem. The proposed model extends the HHC problem from conventional scheduling and routing issues to demand and capacity management aspects. It enables an HHC firm to solve the daily scheduling and routing problem considering existing patients and nursing staff in combination with the simultaneous selection of new patients and nurses, and optimizing the existing routes by including new patients and nurses. The model considers planning issues related to compatibility, time restrictions, contract durations, idle time and workload balance. Two heuristic methods are proposed to solve the model by exploiting the variable neighborhood search (VNS approach. Results obtained from the heuristic methods are compared with a CPLEX based solution. Numerical experiments performed on different data sets, show the efficiency and effectiveness of the solution methods to handle the considered problem.

Gain scheduling using the Youla parameterization

DEFF Research Database (Denmark)

Niemann, Hans Henrik; Stoustrup, Jakob

1999-01-01

Gain scheduling controllers are considered in this paper. The gain scheduling problem where the scheduling parameter vector cannot be measured directly, but needs to be estimated is considered. An estimation of the scheduling vector has been derived by using the Youla parameterization. The use...... in connection with H_inf gain scheduling controllers....

A Novel Joint Problem of Routing, Scheduling, and Variable-Width Channel Allocation in WMNs

Directory of Open Access Journals (Sweden)

Chun-Cheng Lin

2014-01-01

Full Text Available 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.

2007 Wholesale Power Rate Schedules : 2007 General Rate Schedule Provisions.

Energy Technology Data Exchange (ETDEWEB)

United States. Bonneville Power Administration.

2006-11-01

This schedule is available for the contract purchase of Firm Power to be used within the Pacific Northwest (PNW). Priority Firm (PF) Power may be purchased by public bodies, cooperatives, and Federal agencies for resale to ultimate consumers, for direct consumption, and for Construction, Test and Start-Up, and Station Service. Rates in this schedule are in effect beginning October 1, 2006, and apply to purchases under requirements Firm Power sales contracts for a three-year period. The Slice Product is only available for public bodies and cooperatives who have signed Slice contracts for the FY 2002-2011 period. Utilities participating in the Residential Exchange Program (REP) under Section 5(c) of the Northwest Power Act may purchase Priority Firm Power pursuant to the Residential Exchange Program. Rates under contracts that contain charges that escalate based on BPA's Priority Firm Power rates shall be based on the three-year rates listed in this rate schedule in addition to applicable transmission charges. This rate schedule supersedes the PF-02 rate schedule, which went into effect October 1, 2001. Sales under the PF-07 rate schedule are subject to BPA's 2007 General Rate Schedule Provisions (2007 GRSPs). Products available under this rate schedule are defined in the 2007 GRSPs. For sales under this rate schedule, bills shall be rendered and payments due pursuant to BPA's 2007 GRSPs and billing process.

Simplifying Multiproject Scheduling Problem Based on Design Structure Matrix and Its Solution by an Improved aiNet Algorithm

Directory of Open Access Journals (Sweden)

Chunhua Ju

2012-01-01

Full Text Available Managing multiple project is a complex task involving the unrelenting pressures of time and cost. Many studies have proposed various tools and techniques for single-project scheduling; however, the literature further considering multimode or multiproject issues occurring in the real world is rather scarce. In this paper, design structure matrix (DSM and an improved artificial immune network algorithm (aiNet are developed to solve a multi-mode resource-constrained scheduling problem. Firstly, the DSM is used to simplify the mathematic model of multi-project scheduling problem. Subsequently, aiNet algorithm comprised of clonal selection, negative selection, and network suppression is adopted to realize the local searching and global searching, which will assure that it has a powerful searching ability and also avoids the possible combinatorial explosion. Finally, the approach is tested on a set of randomly cases generated from ProGen. The computational results validate the effectiveness of the proposed algorithm comparing with other famous metaheuristic algorithms such as genetic algorithm (GA, simulated annealing algorithm (SA, and ant colony optimization (ACO.

Bridging the Gap Between Planning and Scheduling

Science.gov (United States)

Smith, David E.; Frank, Jeremy; Jonsson, Ari K.; Norvig, Peter (Technical Monitor)

2000-01-01

Planning research in Artificial Intelligence (AI) has often focused on problems where there are cascading levels of action choice and complex interactions between actions. In contrast. Scheduling research has focused on much larger problems where there is little action choice, but the resulting ordering problem is hard. In this paper, we give an overview of M planning and scheduling techniques, focusing on their similarities, differences, and limitations. We also argue that many difficult practical problems lie somewhere between planning and scheduling, and that neither area has the right set of tools for solving these vexing problems.

Heuristic and Exact Algorithms for the Two-Machine Just in Time Job Shop Scheduling Problem

Directory of Open Access Journals (Sweden)

Mohammed Al-Salem

2016-01-01

Full Text Available The problem addressed in this paper is the two-machine job shop scheduling problem when the objective is to minimize the total earliness and tardiness from a common due date (CDD for a set of jobs when their weights equal 1 (unweighted problem. This objective became very significant after the introduction of the Just in Time manufacturing approach. A procedure to determine whether the CDD is restricted or unrestricted is developed and a semirestricted CDD is defined. Algorithms are introduced to find the optimal solution when the CDD is unrestricted and semirestricted. When the CDD is restricted, which is a much harder problem, a heuristic algorithm is proposed to find approximate solutions. Through computational experiments, the heuristic algorithms’ performance is evaluated with problems up to 500 jobs.

Solving a multi-objective manufacturing cell scheduling problem with the consideration of warehouses using a simulated annealing based procedure

Directory of Open Access Journals (Sweden)

Adrián A. Toncovich

2019-01-01

Full Text Available The competition manufacturing companies face has driven the development of novel and efficient methods that enhance the decision making process. In this work, a specific flow shop scheduling problem of practical interest in the industry is presented and formalized using a mathematical programming model. The problem considers a manufacturing system arranged as a work cell that takes into account the transport operations of raw material and final products between the manufacturing cell and warehouses. For solving this problem, we present a multiobjective metaheuristic strategy based on simulated annealing, the Pareto Archived Simulated Annealing (PASA. We tested this strategy on two kinds of benchmark problem sets proposed by the authors. The first group is composed by small-sized problems. On these tests, PASA was able to obtain optimal or near-optimal solutions in significantly short computing times. In order to complete the analysis, we compared these results to the exact Pareto front of the instances obtained with augmented ε-constraint method. Then, we also tested the algorithm in a set of larger problems to evaluate its performance in more extensive search spaces. We performed this assessment through an analysis of the hypervolume metric. Both sets of tests showed the competitiveness of the Pareto Archived Simulated Annealing to efficiently solve this problem and obtain good quality solutions while using reasonable computational resources.

No-Wait Flexible Flow Shop Scheduling with Due Windows

Directory of Open Access Journals (Sweden)

Rong-Hwa Huang

2015-01-01

Full Text Available To improve capacity and reduce processing time, the flow shop with multiprocessors (FSMP system is commonly used in glass, steel, and semiconductor production. No-wait FSMP is a modern production system that responds to periods when zero work is required in process production. The production process must be continuous and uninterrupted. Setup time must also be considered. Just-in-time (JIT production is very popular in industry, and timely delivery is important to customer satisfaction. Therefore, it is essential to consider the time window constraint, which is also very complex. This study focuses on a no-wait FSMP problem with time window constraint. An improved ant colony optimization (ACO, known as ant colony optimization with flexible update (ACOFU, is developed to solve the problem. The results demonstrate that ACOFU is more effective and robust than ACO when applied to small-scale problems. ACOFU has superior solution capacity and robustness when applied to large-scale problems. Therefore, this study concludes that the proposed algorithm ACOFU performs excellently when applied to the scheduling problem discussed in this study.

Sport Tournament Automated Scheduling System

Directory of Open Access Journals (Sweden)

Raof R. A. A

2018-01-01

Full Text Available The organizer of sport events often facing problems such as wrong calculations of marks and scores, as well as difficult to create a good and reliable schedule. Most of the time, the issues about the level of integrity of committee members and also issues about errors made by human came into the picture. Therefore, the development of sport tournament automated scheduling system is proposed. The system will be able to automatically generate the tournament schedule as well as automatically calculating the scores of each tournament. The problem of scheduling the matches of a round robin and knock-out phase in a sport league are given focus. The problem is defined formally and the computational complexity is being noted. A solution algorithm is presented using a two-step approach. The first step is the creation of a tournament pattern and is based on known graph-theoretic method. The second one is an assignment problem and it is solved using a constraint based depth-first branch and bound procedure that assigns actual teams to numbers in the pattern. As a result, the scheduling process and knock down phase become easy for the tournament organizer and at the same time increasing the level of reliability.

A master surgical scheduling approach for cyclic scheduling in operating room departments

NARCIS (Netherlands)

van Oostrum, Jeroen M.; van Houdenhoven, M.; Hurink, Johann L.; Hans, Elias W.; Wullink, Gerhard; Kazemier, G.

This paper addresses the problem of operating room (OR) scheduling at the tactical level of hospital planning and control. Hospitals repetitively construct operating room schedules, which is a time-consuming, tedious, and complex task. The stochasticity of the durations of surgical procedures

Simultaneous planning of the project scheduling and material procurement problem under the presence of multiple suppliers

Science.gov (United States)

Tabrizi, Babak H.; Ghaderi, Seyed Farid

2016-09-01

Simultaneous planning of project scheduling and material procurement can improve the project execution costs. Hence, the issue has been addressed here by a mixed-integer programming model. The proposed model facilitates the procurement decisions by accounting for a number of suppliers offering a distinctive discount formula from which to purchase the required materials. It is aimed at developing schedules with the best net present value regarding the obtained benefit and costs of the project execution. A genetic algorithm is applied to deal with the problem, in addition to a modified version equipped with a variable neighbourhood search. The underlying factors of the solution methods are calibrated by the Taguchi method to obtain robust solutions. The performance of the aforementioned methods is compared for different problem sizes, in which the utilized local search proved efficient. Finally, a sensitivity analysis is carried out to check the effect of inflation on the objective function value.

A Scheduling Model for the Re-entrant Manufacturing System and Its Optimization by NSGA-II

Directory of Open Access Journals (Sweden)

Masoud Rabbani

2016-11-01

Full Text Available In this study, a two-objective mixed-integer linear programming model (MILP for multi-product re-entrant flow shop scheduling problem has been designed. As a result, two objectives are considered. One of them is maximization of the production rate and the other is the minimization of processing time. The system has m stations and can process several products in a moment. The re-entrant flow shop scheduling problem is well known as NP-hard problem and its complexity has been discussed by several researchers. Given that NSGA-II algorithm is one of the strongest and most applicable algorithm in solving multi-objective optimization problems, it is used to solve this problem. To increase algorithm performance, Taguchi technique is used to design experiments for algorithm’s parameters. Numerical experiments are proposed to show the efficiency and effectiveness of the model. Finally, the results of NSGA-II are compared with SPEA2 algorithm (Strength Pareto Evolutionary Algorithm 2. The experimental results show that the proposed algorithm performs significantly better than the SPEA2.

78 FR 37237 - Proposed Adjustments to the Aggregate Production Quotas for Schedule I and II Controlled...

Science.gov (United States)

2013-06-20

... class of controlled substance listed in schedules I and II and for ephedrine, pseudoephedrine, and... disposal by the registrants holding individual manufacturing quotas for the class; (2) whether any... the Aggregate Production Quotas for Schedule I and II Controlled Substances and Assessment of Annual...

Long-term home care scheduling

DEFF Research Database (Denmark)

Gamst, Mette; Jensen, Thomas Sejr

In several countries, home care is provided for certain citizens living at home. The long-term home care scheduling problem is to generate work plans spanning several days such that a high quality of service is maintained and the overall cost is kept as low as possible. A solution to the problem...... provides detailed information on visits and visit times for each employee on each of the covered days. We propose a branch-and-price algorithm for the long-term home care scheduling problem. The pricing problem generates one-day plans for an employee, and the master problem merges the plans with respect...

Quantitative and qualitative problems of short film production in cinema education in Turkey

Directory of Open Access Journals (Sweden)

Erkanı Mehmet Emrah

2016-01-01

Full Text Available Although Turkish cinema has completed its 100 years, short film could not find the place it deserves in the institutions and in the sector. There are problems in terms of the narrative and technical characteristics of short films beside presentation, marketing and international festival attendance issues. Low budgets, course schedules and structures of the cinema departments and short films and the sector’s ignorance of the importance of short film are the obstacles to the development of short films in Turkey. Increasing the government support, strengthening the cooperation between the sector and the university, improving the festivals’ screening conditions, reforming the arrangements to increase the sponsorship incentives, solving the equipment problems of the institutions will positively affect the productivity of Turkish cinema.

A RELATIONAL DATABASE APPROACH TO THE JOB SHOP SCHEDULING PROBLEM

Directory of Open Access Journals (Sweden)

P. Lindeque

2012-01-01

Full Text Available

ENGLISH ABSTRACT: This paper will attempt to illuminate the advantages of an approach to the job shop scheduling problem using priority based search algorithms and database technology. It will use as basis a system developed for and implemented at a large manufacturing plant. The paper will also attempt to make some predictions as to future developments in these techniques and look at the possibility of including new technologies such as expert systems.

AFRIKAANSE OPSOMMING: Die voordele en toepaslikheid van prioriteits-gebaseerde soek-algoritmes en databasisstelsels op die taakwerkswinkelprobleem sal in hierdie artikel uitgelig word. 'n Stelsel wat by 'n groot vervaardigingsonderneming geimplementeer is, sal as uitgangspunt gebruik word. Toekomstige ontwikkelings in bogenoemde tegnieke en die moontlike insluiting van ekspertstelsels sal ook ondersoek word.

Productive and Re-Productive Thinking in Solving Insight Problems

Science.gov (United States)

Cunningham, J. Barton; MacGregor, James N.

2014-01-01

Many innovations in organizations result when people discover insightful solutions to problems. Insightful problem-solving was considered by Gestalt psychologists to be associated with productive, as opposed to re-productive, thinking. Productive thinking is characterized by shifts in perspective which allow the problem solver to consider new,…

Optimization of Hierarchically Scheduled Heterogeneous Embedded Systems

DEFF Research Database (Denmark)

Pop, Traian; Pop, Paul; Eles, Petru

2005-01-01

We present an approach to the analysis and optimization of heterogeneous distributed embedded systems. The systems are heterogeneous not only in terms of hardware components, but also in terms of communication protocols and scheduling policies. When several scheduling policies share a resource......, they are organized in a hierarchy. In this paper, we address design problems that are characteristic to such hierarchically scheduled systems: assignment of scheduling policies to tasks, mapping of tasks to hardware components, and the scheduling of the activities. We present algorithms for solving these problems....... Our heuristics are able to find schedulable implementations under limited resources, achieving an efficient utilization of the system. The developed algorithms are evaluated using extensive experiments and a real-life example....

A Study on the Optimum Bucket Size for Master Scheduling : For the Case of Hierarchically tured Products

OpenAIRE

木内, 正光

2010-01-01

The function of master scheduling is to plan the flow of order from its arrival to its completion. In this study, the problem of bucket size for master scheduling is taken up. The bucket size for master scheduling has much influence on the lead time of the order. However, to date there is no clear method for how to set the optimum bucket size. The purpose of this study is to propose a method to set the optimum bucket size. In this paper, an equation to estimate the optimum bucket size is prop...

Schedule and staffing of a nuclear power project

International Nuclear Information System (INIS)

Polliart, A.J.; Csik, B.

1977-01-01

Establishment of construction schedule: a) preliminary construction schedule; b) PERT (Program Evaluation Review Techniques) analytical method; c) identify key milestone target dates; d) inter-action by participants and contribution to support revised construction schedule. - Construction schedule control: a) ability to update and modify construction schedule; b) alternate plans to circumvent restraints (problems); c) critical path activity-controls; d) continuous review and report system. - Updating construction site reports to include: 1) progress, 2) accomplishments, 3) potential problems and alternate plans; b) progress reports on related support services; c) total assessment of participating groups on schedule; d) information required by management for decisions. - Typical causes for delays in project schedule. (orig.) [de

A dynamic approach to vehicle scheduling

NARCIS (Netherlands)

D. Huisman (Dennis); R. Freling (Richard); A.P.M. Wagelmans (Albert)

2001-01-01

textabstractThis paper presents a dynamic approach to the vehicle scheduling problem. We discuss the potential benefit of our approach compared to the traditional one, where the vehicle scheduling problem is solved only once for a whole period and the travel times are assumed to be fixed. In our

An MILP approach to shelf life integrated planning and scheduling in scalded sausage production

DEFF Research Database (Denmark)

Günther, H.O.; van Beek, P.; Grunow, Martin

2006-01-01

in which shelf life aspects are integrated into operational production planning and scheduling functions. Specifically we make use of so-called Mixed Integer Linear Programming (MILP) models. Our research is based on an industrial case study of yogurt production. Relying on the principle of block planning...

STATEMENT OF THE OPTIMIZATION PROBLEM OF CARBON PRODUCTS PRODUCTION

Directory of Open Access Journals (Sweden)

O. A. Zhuchenko

2016-08-01

Full Text Available The paper formulated optimization problem formulation production of carbon products. The analysis of technical and economic parameters that can be used to optimize the production of carbonaceous products had been done by the author. To evaluate the efficiency of the energy-intensive production uses several technical and economic indicators. In particular, the specific cost, productivity, income and profitability of production. Based on a detailed analysis had been formulated optimality criterion that takes into account the technological components of profitability. The components in detail the criteria and the proposed method of calculating non-trivial, one of them - the production cost of each product. When solving the optimization problem of technological modes of production into account constraints on the variables are optimized. Thus, restrictions may be expressed on the number of each product produced. Have been formulated the method of calculating the cost per unit of product. Attention is paid to the quality indices of finished products as an additional constraint in the optimization problem. As a result have been formulated the general problem of optimizing the production of carbon products, which includes the optimality criterion and restrictions.

21 CFR 113.83 - Establishing scheduled processes.

Science.gov (United States)

2010-04-01

... commercial production runs should be determined on the basis of recognized scientific methods to be of a size... CONTAINERS Production and Process Controls § 113.83 Establishing scheduled processes. Scheduled processes for... production shall be adequately provided for in establishing the scheduled process. Critical factors, e.g...

Mathematical Model and Algorithm for the Reefer Mechanic Scheduling Problem at Seaports

Directory of Open Access Journals (Sweden)

Jiantong Zhang

2017-01-01

Full Text Available With the development of seaborne logistics, the international trade of goods transported in refrigerated containers is growing fast. Refrigerated containers, also known as reefers, are used in transportation of temperature sensitive cargo, such as perishable fruits. This trend brings new challenges to terminal managers, that is, how to efficiently arrange mechanics to plug and unplug power for the reefers (i.e., tasks at yards. This work investigates the reefer mechanics scheduling problem at container ports. To minimize the sum of the total tardiness of all tasks and the total working distance of all mechanics, we formulate a mathematical model. For the resolution of this problem, we propose a DE algorithm which is combined with efficient heuristics, local search strategies, and parameter adaption scheme. The proposed algorithm is tested and validated through numerical experiments. Computational results demonstrate the effectiveness and efficiency of the proposed algorithm.

Scheduling Network Traffic for Grid Purposes

DEFF Research Database (Denmark)

Gamst, Mette

This thesis concerns scheduling of network traffic in grid context. Grid computing consists of a number of geographically distributed computers, which work together for solving large problems. The computers are connected through a network. When scheduling job execution in grid computing, data...... transmission has so far not been taken into account. This causes stability problems, because data transmission takes time and thus causes delays to the execution plan. This thesis proposes the integration of job scheduling and network routing. The scientific contribution is based on methods from operations...... research and consists of six papers. The first four considers data transmission in grid context. The last two solves the data transmission problem, where the number of paths per data connection is bounded from above. The thesis shows that it is possible to solve the integrated job scheduling and network...

Proposal of Heuristic Algorithm for Scheduling of Print Process in Auto Parts Supplier

Science.gov (United States)

Matsumoto, Shimpei; Okuhara, Koji; Ueno, Nobuyuki; Ishii, Hiroaki

We are interested in the print process on the manufacturing processes of auto parts supplier as an actual problem. The purpose of this research is to apply our scheduling technique developed in university to the actual print process in mass customization environment. Rationalization of the print process is depending on the lot sizing. The manufacturing lead time of the print process is long, and in the present method, production is done depending on worker’s experience and intuition. The construction of an efficient production system is urgent problem. Therefore, in this paper, in order to shorten the entire manufacturing lead time and to reduce the stock, we reexamine the usual method of the lot sizing rule based on heuristic technique, and we propose the improvement method which can plan a more efficient schedule.

12-hour-shift plant schedule improves operator productivity

International Nuclear Information System (INIS)

Gould, S.

1989-01-01

Twelve-hour scheduling has been a mainstay of the petrochemical industry, is common in the papermill industry, and is relatively new to the nuclear utility industry. A review of industry experiences, research, and a federal Nuclear Regulatory Commission (NRC) study of the 12-hour shift (NUREG/CR-4248) demonstrate that the advantages outweigh the disadvantages. The primary advantages are greater job satisfaction, fewer errors, and the better communications inherent in two shift turnovers versus three. Several companies that implemented the 12-hour shift found an increase in employee morale, no adverse effect on worker health, and no decline in safety. They experienced greater productivity, fewer operator errors, and better communication

Decentralized Ground Staff Scheduling

DEFF Research Database (Denmark)

Sørensen, M. D.; Clausen, Jens

2002-01-01

scheduling is investigated. The airport terminal is divided into zones, where each zone consists of a set of stands geographically next to each other. Staff is assigned to work in only one zone and the staff scheduling is planned decentralized for each zone. The advantage of this approach is that the staff...... work in a smaller area of the terminal and thus spends less time walking between stands. When planning decentralized the allocation of stands to flights influences the staff scheduling since the workload in a zone depends on which flights are allocated to stands in the zone. Hence solving the problem...... depends on the actual stand allocation but also on the number of zones and the layout of these. A mathematical model of the problem is proposed, which integrates the stand allocation and the staff scheduling. A heuristic solution method is developed and applied on a real case from British Airways, London...

DAILY SCHEDULING OF SMALL HYDRO POWER PLANTS DISPATCH WITH MODIFIED PARTICLES SWARM OPTIMIZATION

Directory of Open Access Journals (Sweden)

Sinvaldo Rodrigues Moreno

2015-04-01

Full Text Available This paper presents a new approach for short-term hydro power scheduling of reservoirs using an algorithm-based Particle Swarm Optimization (PSO. PSO is a population-based algorithm designed to find good solutions to optimization problems, its characteristics have encouraged its adoption to tackle a variety of problems in different fields. In this paper the authors consider an optimization problem related to a daily scheduling of small hydro power dispatch. The goal is construct a feasible solution that maximize the cascade electricity production, following the environmental constraints and water balance. The paper proposes an improved Particle Swarm Optimization (PSO algorithm, which takes advantage of simplicity and facility of implementation. The algorithm was successfully applied to the optimization of the daily schedule strategies of small hydro power plants, considering maximum water utilization and all constraints related to simultaneous water uses. Extensive computational tests and comparisons with other heuristics methods showed the effectiveness of the proposed approach.

An approximation solution to refinery crude oil scheduling problem with demand uncertainty using joint constrained programming.

Science.gov (United States)

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.

An Approximation Solution to Refinery Crude Oil Scheduling Problem with Demand Uncertainty Using Joint Constrained Programming

Directory of Open Access Journals (Sweden)

Qianqian Duan

2014-01-01

Full Text Available 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.

Automatic Generation of Heuristics for Scheduling

Science.gov (United States)

Morris, Robert A.; Bresina, John L.; Rodgers, Stuart M.

1997-01-01

This paper presents a technique, called GenH, that automatically generates search heuristics for scheduling problems. The impetus for developing this technique is the growing consensus that heuristics encode advice that is, at best, useful in solving most, or typical, problem instances, and, at worst, useful in solving only a narrowly defined set of instances. In either case, heuristic problem solvers, to be broadly applicable, should have a means of automatically adjusting to the idiosyncrasies of each problem instance. GenH generates a search heuristic for a given problem instance by hill-climbing in the space of possible multi-attribute heuristics, where the evaluation of a candidate heuristic is based on the quality of the solution found under its guidance. We present empirical results obtained by applying GenH to the real world problem of telescope observation scheduling. These results demonstrate that GenH is a simple and effective way of improving the performance of an heuristic scheduler.

A multilevel variable neighborhood search heuristic for a practical vehicle routing and driver scheduling problem

DEFF Research Database (Denmark)

Wen, Min; Krapper, Emil; Larsen, Jesper

2011-01-01

in their fresh meat supply logistics system. The problem consists of a 1‐week planning horizon, heterogeneous vehicles, and drivers with predefined work regulations. These regulations include, among other things, predefined workdays, fixed starting time, maximum weekly working duration, and a break rule......The world's second largest producer of pork, Danish Crown, also provides a fresh meat supply logistics system within Denmark. This is used by the majority of supermarkets in Denmark. This article addresses an integrated vehicle routing and driver scheduling problem arising at Danish Crown....... The objective is to minimize the total delivery cost that is a weighted sum of two kinds of delivery costs. A multilevel variable neighborhood search heuristic is proposed for the problem. In a preprocessing step, the problem size is reduced through an aggregation procedure. Thereafter, the aggregated weekly...

A Flexible Job Shop Scheduling Problem with Controllable Processing Times to Optimize Total Cost of Delay and Processing

Directory of Open Access Journals (Sweden)

Hadi Mokhtari

2015-11-01

Full Text Available In this paper, the flexible job shop scheduling problem with machine flexibility and controllable process times is studied. The main idea is that the processing times of operations may be controlled by consumptions of additional resources. The purpose of this paper to find the best trade-off between processing cost and delay cost in order to minimize the total costs. The proposed model, flexible job shop scheduling with controllable processing times (FJCPT, is formulated as an integer non-linear programming (INLP model and then it is converted into an integer linear programming (ILP model. Due to NP-hardness of FJCPT, conventional analytic optimization methods are not efficient. Hence, in order to solve the problem, a Scatter Search (SS, as an efficient metaheuristic method, is developed. To show the effectiveness of the proposed method, numerical experiments are conducted. The efficiency of the proposed algorithm is compared with that of a genetic algorithm (GA available in the literature for solving FJSP problem. The results showed that the proposed SS provide better solutions than the existing GA.

An unit cost adjusting heuristic algorithm for the integrated planning and scheduling of a two-stage supply chain

Directory of Open Access Journals (Sweden)

Jianhua Wang

2014-10-01

Full Text Available Purpose: The stable relationship of one-supplier-one-customer is replaced by a dynamic relationship of multi-supplier-multi-customer in current market gradually, and efficient scheduling techniques are important tools of the dynamic supply chain relationship establishing process. This paper studies the optimization of the integrated planning and scheduling problem of a two-stage supply chain with multiple manufacturers and multiple retailers to obtain a minimum supply chain operating cost, whose manufacturers have different production capacities, holding and producing cost rates, transportation costs to retailers.Design/methodology/approach: As a complex task allocation and scheduling problem, this paper sets up an INLP model for it and designs a Unit Cost Adjusting (UCA heuristic algorithm that adjust the suppliers’ supplying quantity according to their unit costs step by step to solve the model.Findings: Relying on the contrasting analysis between the UCA and the Lingo solvers for optimizing many numerical experiments, results show that the INLP model and the UCA algorithm can obtain its near optimal solution of the two-stage supply chain’s planning and scheduling problem within very short CPU time.Research limitations/implications: The proposed UCA heuristic can easily help managers to optimizing the two-stage supply chain scheduling problems which doesn’t include the delivery time and batch of orders. For two-stage supply chains are the most common form of actual commercial relationships, so to make some modification and study on the UCA heuristic should be able to optimize the integrated planning and scheduling problems of a supply chain with more reality constraints.Originality/value: This research proposes an innovative UCA heuristic for optimizing the integrated planning and scheduling problem of two-stage supply chains with the constraints of suppliers’ production capacity and the orders’ delivering time, and has a great

Optimal methodology for a machining process scheduling in spot electricity markets

International Nuclear Information System (INIS)

Yusta, J.M.; Torres, F.; Khodr, H.M.

2010-01-01

Electricity spot markets have introduced hourly variations in the price of electricity. These variations allow the increase of the energy efficiency by the appropriate scheduling and adaptation of the industrial production to the hourly cost of electricity in order to obtain the maximum profit for the industry. In this article a mathematical optimization model simulates costs and the electricity demand of a machining process. The resultant problem is solved using the generalized reduced gradient approach, to find the optimum production schedule that maximizes the industry profit considering the hourly variations of the price of electricity in the spot market. Different price scenarios are studied to analyze the impact of the spot market prices for electricity on the optimal scheduling of the machining process and on the industry profit. The convenience of the application of the proposed model is shown especially in cases of very high electricity prices.

Solving University Scheduling Problem Using Hybrid Approach

Directory of Open Access Journals (Sweden)

Aftab Ahmed Shaikh

2011-10-01

Full Text Available In universities scheduling curriculum activity is an essential job. Primarily, scheduling is a distribution of limited resources under interrelated constraints. The set of hard constraints demand the highest priority and should not to be violated at any cost, while the maximum soft constraints satisfaction mounts the quality scale of solution. In this research paper, a novel bisected approach is introduced that is comprisesd of GA (Genetic Algorithm as well as Backtracking Recursive Search. The employed technique deals with both hard and soft constraints successively. The first phase decisively is focused over elimination of all the hard constraints bounded violations and eventually produces partial solution for subsequent step. The second phase is supposed to draw the best possible solution on the search space. Promising results are obtained by implementation on the real dataset. The key points of the research approach are to get assurance of hard constraints removal from the dataset and minimizing computational time for GA by initializing pre-processed set of chromosomes.

Field Engineers' Scheduling at Oil Rigs: a Case Study

Directory of Open Access Journals (Sweden)

Y. S. Usmani

2012-02-01

Full Text Available Oil exploration and production operations face a number of challenges. Professional planners have to design solutions for various practical problems or issues. However, the time consumed is often very extensive because of the large number of possible solutions. Further, the matter of choosing the best solution remains. The present paper investigates a problem related to leading companies in the energy and chemical manufacturing sector of the oil and gas industry. Each company’s field engineers are expensive and valuable assets. Therefore, an optimized roster is rather important. In the present paper, the objective is to design a field engineers’ schedule which would be both feasible and satisfying towards the various demands of rigs, with minimum operational cost to the company. An efficient and quick optimization technique is presented to schedule the shifts of field engineers.

Preventive maintenance optimization for a multi-component system under changing job shop schedule

International Nuclear Information System (INIS)

Zhou Xiaojun; Lu Zhiqiang; Xi Lifeng

2012-01-01

Variability and small lot size is a common feature for many discrete manufacturing processes designed to meet a wide array of customer needs. Because of this, job shop schedule often has to be continuously updated in reaction to changes in production plan. Generally, the aim of preventive maintenance is to ensure production effectiveness and therefore the preventive maintenance models must have the ability to be adaptive to changes in job shop schedule. In this paper, a dynamic opportunistic preventive maintenance model is developed for a multi-component system with considering changes in job shop schedule. Whenever a job is completed, preventive maintenance opportunities arise for all the components in the system. An optimal maintenance practice is dynamically determined by maximizing the short-term cumulative opportunistic maintenance cost savings for the system. The numerical example shows that the scheme obtained by the proposed model can effectively address the preventive maintenance scheduling problem caused by the changes in job shop schedule and is more efficient than the ones based on two other commonly used preventive maintenance models.

The nurse scheduling problem: a goal programming and nonlinear optimization approaches

Science.gov (United States)

Hakim, L.; Bakhtiar, T.; Jaharuddin

2017-01-01

Nurses scheduling is an activity of allocating nurses to conduct a set of tasks at certain room at a hospital or health centre within a certain period. One of obstacles in the nurse scheduling is the lack of resources in order to fulfil the needs of the hospital. Nurse scheduling which is undertaken manually will be at risk of not fulfilling some nursing rules set by the hospital. Therefore, this study aimed to perform scheduling models that satisfy all the specific rules set by the management of Bogor State Hospital. We have developed three models to overcome the scheduling needs. Model 1 is designed to schedule nurses who are solely assigned to a certain inpatient unit and Model 2 is constructed to manage nurses who are assigned to an inpatient room as well as at Polyclinic room as conjunct nurses. As the assignment of nurses on each shift is uneven, then we propose Model 3 to minimize the variance of the workload in order to achieve equitable assignment on every shift. The first two models are formulated in goal programming framework, while the last model is in nonlinear optimization form.

A new approach for solving capacitated lot sizing and scheduling problem with sequence and period-dependent setup costs

Directory of Open Access Journals (Sweden)

Imen Chaieb Memmi

2013-09-01

Full Text Available Purpose: We aim to examine the capacitated multi-item lot sizing problem which is a typical example of a large bucket model, where many different items can be produced on the same machine in one time period. We propose a new approach to determine the production sequence and lot sizes that minimize the sum of start up and setup costs, inventory and production costs over all periods.Design/methodology/approach: The approach is composed of three steps. First, we compute a lower bound on total cost. Then we propose a three sub-steps iteration procedure. We solve optimally the lot sizing problem without considering products sequencing and their cost. Then, we determine products quantities to produce each period while minimizing the storage and variable production costs. Given the products to manufacture each period, we determine its correspondent optimal products sequencing, by using a Branch and Bound algorithm. Given the sequences of products within each period, we evaluate the total start up and setup cost. We compare then the total cost obtained to the lower bound of the total cost. If this value riches a prefixed value, we stop. Otherwise, we modify the results of lot sizing problem.Findings and Originality/value: We show using an illustrative example, that the difference between the total cost and its lower bound is only 10%. This gap depends on the significance of the inventory and production costs and the machine’s capacity. Comparing the approach we develop with a traditional one, we show that we manage to reduce the total cost by 30%.Research limitations/implications: Our model fits better to real-world situations where production systems run continuously. This model is applied for limited number of part types and periods.Practical implications: Our approach determines the products to manufacture each time period, their economic amounts, and their scheduling within each period. This outcome should help decision makers bearing expensive

Minimizing total weighted tardiness for the single machine scheduling problem with dependent setup time and precedence constraints

Directory of Open Access Journals (Sweden)

Hamidreza Haddad

2012-04-01

Full Text Available This paper tackles the single machine scheduling problem with dependent setup time and precedence constraints. The primary objective of this paper is minimization of total weighted tardiness. Since the complexity of the resulted problem is NP-hard we use metaheuristics method to solve the resulted model. The proposed model of this paper uses genetic algorithm to solve the problem in reasonable amount of time. Because of high sensitivity of GA to its initial values of parameters, a Taguchi approach is presented to calibrate its parameters. Computational experiments validate the effectiveness and capability of proposed method.

Chaotic Multiobjective Evolutionary Algorithm Based on Decomposition for Test Task Scheduling Problem

Directory of Open Access Journals (Sweden)

Hui Lu

2014-01-01

Full Text Available Test task scheduling problem (TTSP is a complex optimization problem and has many local optima. In this paper, a hybrid chaotic multiobjective evolutionary algorithm based on decomposition (CMOEA/D is presented to avoid becoming trapped in local optima and to obtain high quality solutions. First, we propose an improving integrated encoding scheme (IES to increase the efficiency. Then ten chaotic maps are applied into the multiobjective evolutionary algorithm based on decomposition (MOEA/D in three phases, that is, initial population and crossover and mutation operators. To identify a good approach for hybrid MOEA/D and chaos and indicate the effectiveness of the improving IES several experiments are performed. The Pareto front and the statistical results demonstrate that different chaotic maps in different phases have different effects for solving the TTSP especially the circle map and ICMIC map. The similarity degree of distribution between chaotic maps and the problem is a very essential factor for the application of chaotic maps. In addition, the experiments of comparisons of CMOEA/D and variable neighborhood MOEA/D (VNM indicate that our algorithm has the best performance in solving the TTSP.

Relative performance of priority rules for hybrid flow shop scheduling with setup times

Directory of Open Access Journals (Sweden)

Helio Yochihiro Fuchigami

2015-12-01

Full Text Available This paper focuses the hybrid flow shop scheduling problem with explicit and sequence-independent setup times. This production environment is a multistage system with unidirectional flow of jobs, wherein each stage may contain multiple machines available for processing. The optimized measure was the total time to complete the schedule (makespan. The aim was to propose new priority rules to support the schedule and to evaluate their relative performance at the production system considered by the percentage of success, relative deviation, standard deviation of relative deviation, and average CPU time. Computational experiments have indicated that the rules using ascending order of the sum of processing and setup times of the first stage (SPT1 and SPT1_ERD performed better, reaching together more than 56% of success.

Schedules of Controlled Substances: Placement of FDA-Approved Products of Oral Solutions Containing Dronabinol [(-)-delta-9-transtetrahydrocannabinol (delta-9-THC)] in Schedule II. Interim final rule, with request for comments.

Science.gov (United States)

2017-03-23

On July 1, 2016, the U.S. Food and Drug Administration (FDA) approved a new drug application for Syndros, a drug product consisting of dronabinol [(-)-delta-9-trans-tetrahydrocannabinol (delta-9-THC)] oral solution. Thereafter, the Department of Health and Human Services (HHS) provided the Drug Enforcement Administration (DEA) with a scheduling recommendation that would result in Syndros (and other oral solutions containing dronabinol) being placed in schedule II of the Controlled Substances Act (CSA). In accordance with the CSA, as revised by the Improving Regulatory Transparency for New Medical Therapies Act, DEA is hereby issuing an interim final rule placing FDA-approved products of oral solutions containing dronabinol in schedule II of the CSA.

Practical job shop scheduling

NARCIS (Netherlands)

Schutten, Johannes M.J.

1998-01-01

The Shifting Bottleneck procedure is an intuitive and reasonably good approximation algorithm for the notoriously difficult classical job shop scheduling problem. The principle of decomposing a classical job shop problem into a series of single-machine problems can also easily be applied to job shop

Hybrid glowworm swarm optimization for task scheduling in the cloud environment

Science.gov (United States)

Zhou, Jing; Dong, Shoubin

2018-06-01

In recent years many heuristic algorithms have been proposed to solve task scheduling problems in the cloud environment owing to their optimization capability. This article proposes a hybrid glowworm swarm optimization (HGSO) based on glowworm swarm optimization (GSO), which uses a technique of evolutionary computation, a strategy of quantum behaviour based on the principle of neighbourhood, offspring production and random walk, to achieve more efficient scheduling with reasonable scheduling costs. The proposed HGSO reduces the redundant computation and the dependence on the initialization of GSO, accelerates the convergence and more easily escapes from local optima. The conducted experiments and statistical analysis showed that in most cases the proposed HGSO algorithm outperformed previous heuristic algorithms to deal with independent tasks.

Shuffled Frog Leaping Algorithm for Preemptive Project Scheduling Problems with Resource Vacations Based on Patterson Set

Directory of Open Access Journals (Sweden)

Yi Han

2013-01-01

Full Text Available This paper presents a shuffled frog leaping algorithm (SFLA for the single-mode resource-constrained project scheduling problem where activities can be divided into equant units and interrupted during processing. Each activity consumes 0–3 types of resources which are renewable and temporarily not available due to resource vacations in each period. The presence of scarce resources and precedence relations between activities makes project scheduling a difficult and important task in project management. A recent popular metaheuristic shuffled frog leaping algorithm, which is enlightened by the predatory habit of frog group in a small pond, is adopted to investigate the project makespan improvement on Patterson benchmark sets which is composed of different small and medium size projects. Computational results demonstrate the effectiveness and efficiency of SFLA in reducing project makespan and minimizing activity splitting number within an average CPU runtime, 0.521 second. This paper exposes all the scheduling sequences for each project and shows that of the 23 best known solutions have been improved.

A HYBRID HEURISTIC ALGORITHM FOR SOLVING THE RESOURCE CONSTRAINED PROJECT SCHEDULING PROBLEM (RCPSP

Directory of Open Access Journals (Sweden)

Juan Carlos Rivera

Full Text Available The Resource Constrained Project Scheduling Problem (RCPSP is a problem of great interest for the scientific community because it belongs to the class of NP-Hard problems and no methods are known that can solve it accurately in polynomial processing times. For this reason heuristic methods are used to solve it in an efficient way though there is no guarantee that an optimal solution can be obtained. This research presents a hybrid heuristic search algorithm to solve the RCPSP efficiently, combining elements of the heuristic Greedy Randomized Adaptive Search Procedure (GRASP, Scatter Search and Justification. The efficiency obtained is measured taking into account the presence of the new elements added to the GRASP algorithm taken as base: Justification and Scatter Search. The algorithms are evaluated using three data bases of instances of the problem: 480 instances of 30 activities, 480 of 60, and 600 of 120 activities respectively, taken from the library PSPLIB available online. The solutions obtained by the developed algorithm for the instances of 30, 60 and 120 are compared with results obtained by other researchers at international level, where a prominent place is obtained, according to Chen (2011.

Spike: Artificial intelligence scheduling for Hubble space telescope

Science.gov (United States)

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.

Radiopharmaceutical production at Lucas Heights

International Nuclear Information System (INIS)

Druce, M.

1987-01-01

The difficult problems of operating and maintaining complex equipment, meeting despatch deadlines, ensuring product quality, production scheduling and controlling staff are discussed in relation to Australia's national radioisotope production plant

Optimization of municipal waste collection scheduling and routing using vehicle assignment problem (case study of Surabaya city waste collection)

Science.gov (United States)

Ramdhani, M. N.; Baihaqi, I.; Siswanto, N.

2018-04-01

Waste collection and disposal become a major problem for many metropolitan cities. Growing population, limited vehicles, and increased road traffic make the waste transportation become more complex. Waste collection involves some key considerations, such as vehicle assignment, vehicle routes, and vehicle scheduling. In the scheduling process, each vehicle has a scheduled departure that serve each route. Therefore, vehicle’s assignments should consider the time required to finish one assigment on that route. The objective of this study is to minimize the number of vehicles needed to serve all routes by developing a mathematical model which uses assignment problem approach. The first step is to generated possible routes from the existing routes, followed by vehicle assignments for those certain routes. The result of the model shows fewer vehicles required to perform waste collection asa well as the the number of journeys that the vehicle to collect the waste to the landfill. The comparison of existing conditions with the model result indicates that the latter’s has better condition than the existing condition because each vehicle with certain route has an equal workload, all the result’s model has the maximum of two journeys for each route.

Planning and Scheduling for Fleets of Earth Observing Satellites

Science.gov (United States)

Frank, Jeremy; Jonsson, Ari; Morris, Robert; Smith, David E.; Norvig, Peter (Technical Monitor)

2001-01-01

We address the problem of scheduling observations for a collection of earth observing satellites. This scheduling task is a difficult optimization problem, potentially involving many satellites, hundreds of requests, constraints on when and how to service each request, and resources such as instruments, recording devices, transmitters, and ground stations. High-fidelity models are required to ensure the validity of schedules; at the same time, the size and complexity of the problem makes it unlikely that systematic optimization search methods will be able to solve them in a reasonable time. This paper presents a constraint-based approach to solving the Earth Observing Satellites (EOS) scheduling problem, and proposes a stochastic heuristic search method for solving it.

The robust schedule - A link to improved workflow

DEFF Research Database (Denmark)

Lindhard, Søren; Wandahl, Søren

2012-01-01

-down the contractors, and force them to rigorously adhere to the initial schedule. If delayed the work-pace or manpower has to be increased to observe the schedule. In attempt to improve productivity three independent site-mangers have been interviewed about time-scheduling. Their experiences and opinions have been...... analyzed and weaknesses in existing time scheduling have been found. The findings showed a negative side effect of keeping the schedule to tight. A too tight schedule is inflexible and cannot absorb variability in production. Flexibility is necessary because of the contractors interacting and dependable....... The result is a chaotic, complex and uncontrolled construction site. Furthermore, strict time limits entail the workflow to be optimized under non-optimal conditions. Even though productivity seems to be increasing, productivity per man-hour is decreasing resulting in increased cost. To increase productivity...

VNS (Variable Neighbourhood Search) applied to batch sequencing in operational scheduling of pipeline network; VNS (Variable Neighbourhood Search) aplicado ao sequenciamento de bateladas do 'scheduling' de operacoes de uma malha dutoviaria

Energy Technology Data Exchange (ETDEWEB)

Yamamoto, Lia; Arruda, Lucia Valeria Ramos de; Libert, Nikolas [Universidade Tecnologica Federal do Parana (UTFPR), Curitiba, PR (Brazil)

2008-07-01

This work presents the VNS heuristic technique applied on batches ordering in a real network of petroleum derivatives distribution. These ordering have great influence in operational scheduling of a pipeline network. The operational scheduling purposes the efficient utilization of the resources, resulting on a better performance. Due to the great complexity of the real network problem and the necessity of its resolution in little computational time, it was adopted a problem subdivision in assignment of resources, sequencing and timing. In the resources assignment stage, it is considered the production/consumption functions and the products tankages to determine the total batches, including its volume, flow rate and the time-windows to satisfy the demand. These data are used in the sequencing stage, where a VNS based model determines the batches ordering. In a final step, the last block, realize the temporisation considering the network operational constraints. This work shows the results from the optimization of the sequencing stage which aims the improvement of the solution quality of scheduling. (author)

Analysis and Optimisation of Hierarchically Scheduled Multiprocessor Embedded Systems

DEFF Research Database (Denmark)

Pop, Traian; Pop, Paul; Eles, Petru

2008-01-01

We present an approach to the analysis and optimisation of heterogeneous multiprocessor embedded systems. The systems are heterogeneous not only in terms of hardware components, but also in terms of communication protocols and scheduling policies. When several scheduling policies share a resource......, they are organised in a hierarchy. In this paper, we first develop a holistic scheduling and schedulability analysis that determines the timing properties of a hierarchically scheduled system. Second, we address design problems that are characteristic to such hierarchically scheduled systems: assignment...... of scheduling policies to tasks, mapping of tasks to hardware components, and the scheduling of the activities. We also present several algorithms for solving these problems. Our heuristics are able to find schedulable implementations under limited resources, achieving an efficient utilisation of the system...

75 FR 15642 - Schedules of Controlled Substances: Exempted Prescription Product; River Edge Pharmaceutical...

Science.gov (United States)

2010-03-30

... 1117-AB28 Schedules of Controlled Substances: Exempted Prescription Product; River Edge Pharmaceutical... new applications for exemption. DEA has received one new application for exemption for River Edge... application for exemption pursuant to the provisions of 21 CFR 1308.32 for: River Edge Pharmaceutical's...

Project Scheduling Heuristics-Based Standard PSO for Task-Resource Assignment in Heterogeneous Grid

Directory of Open Access Journals (Sweden)

Ruey-Maw Chen

2011-01-01

Full Text Available The task scheduling problem has been widely studied for assigning resources to tasks in heterogeneous grid environment. Effective task scheduling is an important issue for the performance of grid computing. Meanwhile, the task scheduling problem is an NP-complete problem. Hence, this investigation introduces a named “standard“ particle swarm optimization (PSO metaheuristic approach to efficiently solve the task scheduling problems in grid. Meanwhile, two promising heuristics based on multimode project scheduling are proposed to help in solving interesting scheduling problems. They are the best performance resource heuristic and the latest finish time heuristic. These two heuristics applied to the PSO scheme are for speeding up the search of the particle and improving the capability of finding a sound schedule. Moreover, both global communication topology and local ring communication topology are also investigated for efficient study of proposed scheme. Simulation results demonstrate that the proposed approach in this investigation can successfully solve the task-resource assignment problems in grid computing and similar scheduling problems.

An Adaptive Large Neighborhood Search Algorithm for the Resource-constrained Project Scheduling Problem

DEFF Research Database (Denmark)

Muller, Laurent Flindt

2009-01-01

We present an application of an Adaptive Large Neighborhood Search (ALNS) algorithm to the Resource-constrained Project Scheduling Problem (RCPSP). The ALNS framework was first proposed by Pisinger and Røpke [19] and can be described as a large neighborhood search algorithm with an adaptive layer......, where a set of destroy/repair neighborhoods compete to modify the current solution in each iteration of the algorithm. Experiments are performed on the wellknown J30, J60 and J120 benchmark instances, which show that the proposed algorithm is competitive and confirms the strength of the ALNS framework...

Polling, production & priorities

NARCIS (Netherlands)

Winands, E.M.M.

2007-01-01

Polling, Production & Priorities The present monograph focuses on the so-called stochastic economic lot scheduling problem (SELSP), which deals with the make-to-stock production of multiple standardized products on a single machine with limited capacity under random demands, possibly random setup

Capacitated vehicle-routing problem model for scheduled solid waste collection and route optimization using PSO algorithm.

Science.gov (United States)

Hannan, M A; Akhtar, Mahmuda; Begum, R A; Basri, H; Hussain, A; Scavino, Edgar

2018-01-01

Waste collection widely depends on the route optimization problem that involves a large amount of expenditure in terms of capital, labor, and variable operational costs. Thus, the more waste collection route is optimized, the more reduction in different costs and environmental effect will be. This study proposes a modified particle swarm optimization (PSO) algorithm in a capacitated vehicle-routing problem (CVRP) model to determine the best waste collection and route optimization solutions. In this study, threshold waste level (TWL) and scheduling concepts are applied in the PSO-based CVRP model under different datasets. The obtained results from different datasets show that the proposed algorithmic CVRP model provides the best waste collection and route optimization in terms of travel distance, total waste, waste collection efficiency, and tightness at 70-75% of TWL. The obtained results for 1 week scheduling show that 70% of TWL performs better than all node consideration in terms of collected waste, distance, tightness, efficiency, fuel consumption, and cost. The proposed optimized model can serve as a valuable tool for waste collection and route optimization toward reducing socioeconomic and environmental impacts. Copyright © 2017 Elsevier Ltd. All rights reserved.

A model for generating master surgical schedules to allow cyclic scheduling in operating room departments

NARCIS (Netherlands)

van Oostrum, J.M.; van Houdenhoven, M.; Hurink, Johann L.; Hans, Elias W.; Wullink, Gerhard; Kazemier, G.

2005-01-01

This paper addresses the problem of operating room scheduling at the tactical level of hospital planning and control. Hospitals repetitively construct operating room schedules, which is a time consuming tedious and complex task. The stochasticity of the durations of surgical procedures complicates

Vehicle and driver scheduling for public transit.

Science.gov (United States)

2009-08-01

The problem of driver scheduling involves the construction of a legal set of shifts, including allowance : of overtime, which cover the blocks in a particular vehicle schedule. A shift is the work scheduled to be performed by : a driver in one day, w...

Schedule Matters: Understanding the Relationship between Schedule Delays and Costs on Overruns

Science.gov (United States)

Majerowicz, Walt; Shinn, Stephen A.

2016-01-01

This paper examines the relationship between schedule delays and cost overruns on complex projects. It is generally accepted by many project practitioners that cost overruns are directly related to schedule delays. But what does "directly related to" actually mean? Some reasons or root causes for schedule delays and associated cost overruns are obvious, if only in hindsight. For example, unrealistic estimates, supply chain difficulties, insufficient schedule margin, technical problems, scope changes, or the occurrence of risk events can negatively impact schedule performance. Other factors driving schedule delays and cost overruns may be less obvious and more difficult to quantify. Examples of these less obvious factors include project complexity, flawed estimating assumptions, over-optimism, political factors, "black swan" events, or even poor leadership and communication. Indeed, is it even possible the schedule itself could be a source of delay and subsequent cost overrun? Through literature review, surveys of project practitioners, and the authors' own experience on NASA programs and projects, the authors will categorize and examine the various factors affecting the relationship between project schedule delays and cost growth. The authors will also propose some ideas for organizations to consider to help create an awareness of the factors which could cause or influence schedule delays and associated cost growth on complex projects.

Locomotive Schedule Optimization for Da-qin Heavy Haul Railway

Directory of Open Access Journals (Sweden)

Ruiye Su

2015-01-01

Full Text Available The main difference between locomotive schedule of heavy haul railways and that of regular rail transportation is the number of locomotives utilized for one train. One heavy-loaded train usually has more than one locomotive, but a regular train only has one. This paper develops an optimization model for the multilocomotive scheduling problem (MLSP through analyzing the current locomotive schedule of Da-qin Railway. The objective function of our paper is to minimize the total number of utilized locomotives. The MLSP is nondeterministic polynomial (NP hard. Therefore, we convert the multilocomotive traction problem into a single-locomotive traction problem. Then, the single-locomotive traction problem (SLTP can be converted into an assignment problem. The Hungarian algorithm is applied to solve the model and obtain the optimal locomotive schedule. We use the variance of detention time of locomotives at stations to evaluate the stability of locomotive schedule. In order to evaluate the effectiveness of the proposed optimization model, case studies for 20 kt and 30 kt heavy-loaded combined trains on Da-qin Railway are both conducted. Compared to the current schedules, the optimal schedules from the proposed models can save 62 and 47 locomotives for 20 kt and 30 kt heavy-loaded combined trains, respectively. Therefore, the effectiveness of the proposed model and its solution algorithm are both valid.

Designing a fuzzy scheduler for hard real-time systems

Science.gov (United States)

Yen, John; Lee, Jonathan; Pfluger, Nathan; Natarajan, Swami

1992-01-01

In hard real-time systems, tasks have to be performed not only correctly, but also in a timely fashion. If timing constraints are not met, there might be severe consequences. Task scheduling is the most important problem in designing a hard real-time system, because the scheduling algorithm ensures that tasks meet their deadlines. However, the inherent nature of uncertainty in dynamic hard real-time systems increases the problems inherent in scheduling. In an effort to alleviate these problems, we have developed a fuzzy scheduler to facilitate searching for a feasible schedule. A set of fuzzy rules are proposed to guide the search. The situation we are trying to address is the performance of the system when no feasible solution can be found, and therefore, certain tasks will not be executed. We wish to limit the number of important tasks that are not scheduled.

Online Scheduling in Manufacturing A Cumulative Delay Approach

CERN Document Server

Suwa, Haruhiko

2013-01-01

Online scheduling is recognized as the crucial decision-making process of production control at a phase of “being in production" according to the released shop floor schedule. Online scheduling can be also considered as one of key enablers to realize prompt capable-to-promise as well as available-to-promise to customers along with reducing production lead times under recent globalized competitive markets. Online Scheduling in Manufacturing introduces new approaches to online scheduling based on a concept of cumulative delay. The cumulative delay is regarded as consolidated information of uncertainties under a dynamic environment in manufacturing and can be collected constantly without much effort at any points in time during a schedule execution. In this approach, the cumulative delay of the schedule has the important role of a criterion for making a decision whether or not a schedule revision is carried out. The cumulative delay approach to trigger schedule revisions has the following capabilities for the ...

Future aircraft networks and schedules

Science.gov (United States)

Shu, Yan

2011-07-01

Because of the importance of air transportation scheduling, the emergence of small aircraft and the vision of future fuel-efficient aircraft, this thesis has focused on the study of aircraft scheduling and network design involving multiple types of aircraft and flight services. It develops models and solution algorithms for the schedule design problem and analyzes the computational results. First, based on the current development of small aircraft and on-demand flight services, this thesis expands a business model for integrating on-demand flight services with the traditional scheduled flight services. This thesis proposes a three-step approach to the design of aircraft schedules and networks from scratch under the model. In the first step, both a frequency assignment model for scheduled flights that incorporates a passenger path choice model and a frequency assignment model for on-demand flights that incorporates a passenger mode choice model are created. In the second step, a rough fleet assignment model that determines a set of flight legs, each of which is assigned an aircraft type and a rough departure time is constructed. In the third step, a timetable model that determines an exact departure time for each flight leg is developed. Based on the models proposed in the three steps, this thesis creates schedule design instances that involve almost all the major airports and markets in the United States. The instances of the frequency assignment model created in this thesis are large-scale non-convex mixed-integer programming problems, and this dissertation develops an overall network structure and proposes iterative algorithms for solving these instances. The instances of both the rough fleet assignment model and the timetable model created in this thesis are large-scale mixed-integer programming problems, and this dissertation develops subproblem schemes for solving these instances. Based on these solution algorithms, this dissertation also presents

Combined scheduling of electricity and heat in a microgrid with volatile wind power

DEFF Research Database (Denmark)

Xu, Lizhong; Yang, Guang Ya; Xu, Zhao

2011-01-01

An optimization model is developed for scheduling electricity and heat production in a microgrid under a day-ahead market environment considering the operation constraints and the volatility of wind power generation. The model optimizes the total operation costs from energy and heating consumption...... into a mixed-integer programming (MIP) problem. Numerical simulations present the efficacy of the proposed model for day-ahead scheduling of a microgrid with wind penetration under the deregulated environment. © 2011 State Grid Electrtic Resarch Institute Press....

A Heuristic Scheduling Algorithm for Minimizing Makespan and Idle Time in a Nagare Cell

Directory of Open Access Journals (Sweden)

M. Muthukumaran

2012-01-01

Full Text Available Adopting a focused factory is a powerful approach for today manufacturing enterprise. This paper introduces the basic manufacturing concept for a struggling manufacturer with limited conventional resources, providing an alternative solution to cell scheduling by implementing the technique of Nagare cell. Nagare cell is a Japanese concept with more objectives than cellular manufacturing system. It is a combination of manual and semiautomatic machine layout as cells, which gives maximum output flexibility for all kind of low-to-medium- and medium-to-high- volume productions. The solution adopted is to create a dedicated group of conventional machines, all but one of which are already available on the shop floor. This paper focuses on the development of heuristic scheduling algorithm in step-by-step method. The algorithm states that the summation of processing time of all products on each machine is calculated first and then the sum of processing time is sorted by the shortest processing time rule to get the assignment schedule. Based on the assignment schedule Nagare cell layout is arranged for processing the product. In addition, this algorithm provides steps to determine the product ready time, machine idle time, and product idle time. And also the Gantt chart, the experimental analysis, and the comparative results are illustrated with five (1×8 to 5×8 scheduling problems. Finally, the objective of minimizing makespan and idle time with greater customer satisfaction is studied through.

Cost-efficient scheduling of FAST observations

Science.gov (United States)

Luo, Qi; Zhao, Laiping; Yu, Ce; Xiao, Jian; Sun, Jizhou; Zhu, Ming; Zhong, Yi

2018-03-01

A cost-efficient schedule for the Five-hundred-meter Aperture Spherical radio Telescope (FAST) requires to maximize the number of observable proposals and the overall scientific priority, and minimize the overall slew-cost generated by telescope shifting, while taking into account the constraints including the astronomical objects visibility, user-defined observable times, avoiding Radio Frequency Interference (RFI). In this contribution, first we solve the problem of maximizing the number of observable proposals and scientific priority by modeling it as a Minimum Cost Maximum Flow (MCMF) problem. The optimal schedule can be found by any MCMF solution algorithm. Then, for minimizing the slew-cost of the generated schedule, we devise a maximally-matchable edges detection-based method to reduce the problem size, and propose a backtracking algorithm to find the perfect matching with minimum slew-cost. Experiments on a real dataset from NASA/IPAC Extragalactic Database (NED) show that, the proposed scheduler can increase the usage of available times with high scientific priority and reduce the slew-cost significantly in a very short time.

Optimal Scheduling of Domestic Appliances via MILP

Directory of Open Access Journals (Sweden)

Zdenek Bradac

2014-12-01

Full Text Available This paper analyzes a consumption scheduling mechanism for domestic appliances within a home area network. The aim of the proposed scheduling is to minimize the total energy price paid by the consumer and to reduce power peaks in order to achieve a balanced daily load schedule. An exact and computationally efficient mixed-integer linear programming (MILP formulation of the problem is presented. This model is verified by several problem instances. Realistic scenarios based on the real price tariffs commercially available in the Czech Republic are calculated. The results obtained by solving the optimization problem are compared with a simulation of the ripple control service currently used by many domestic consumers in the Czech Republic.

Optimal investment and scheduling of distributed energy resources with uncertainty in electric vehicles driving schedules

Energy Technology Data Exchange (ETDEWEB)

Cardoso, Goncalo [Technical Univ. of Lisbon (Portugal); Stadler, Michael [Lawrence Berkeley National Lab. (LBNL), Berkeley, CA (United States); Center for Energy and Innovation Technologies (Austria); Bozchalui, Mohammed C. [NEC Laboratories American Inc., Irving, TX (United States); Sharma, Ratnesh [NEC Laboratories American Inc., Irving, TX (United States); Marnay, Chris [Lawrence Berkeley National Lab. (LBNL), Berkeley, CA (United States); Barbosa-Povoa, Ana [Technical Univ. of Lisbon (Portugal); Ferrao, Paulo [Technical Univ. of Lisbon (Portugal)

2013-12-06

The large scale penetration of electric vehicles (EVs) will introduce technical challenges to the distribution grid, but also carries the potential for vehicle-to-grid services. Namely, if available in large enough numbers, EVs can be used as a distributed energy resource (DER) and their presence can influence optimal DER investment and scheduling decisions in microgrids. In this work, a novel EV fleet aggregator model is introduced in a stochastic formulation of DER-CAM [1], an optimization tool used to address DER investment and scheduling problems. This is used to assess the impact of EV interconnections on optimal DER solutions considering uncertainty in EV driving schedules. Optimization results indicate that EVs can have a significant impact on DER investments, particularly if considering short payback periods. Furthermore, results suggest that uncertainty in driving schedules carries little significance to total energy costs, which is corroborated by results obtained using the stochastic formulation of the problem.

Multiple-Machine Scheduling with Learning Effects and Cooperative Games

Directory of Open Access Journals (Sweden)

Yiyuan Zhou

2015-01-01

Full Text Available Multiple-machine scheduling problems with position-based learning effects are studied in this paper. There is an initial schedule in this scheduling problem. The optimal schedule minimizes the sum of the weighted completion times; the difference between the initial total weighted completion time and the minimal total weighted completion time is the cost savings. A multiple-machine sequencing game is introduced to allocate the cost savings. The game is balanced if the normal processing times of jobs that are on the same machine are equal and an equal number of jobs are scheduled on each machine initially.

Evaluating the performance of constructive heuristics for the blocking flow shop scheduling problem with setup times

Directory of Open Access Journals (Sweden)

Mauricio Iwama Takano

2019-01-01

Full Text Available This paper addresses the minimization of makespan for the permutation flow shop scheduling problem with blocking and sequence and machine dependent setup times, a problem not yet studied in previous studies. The 14 best known heuristics for the permutation flow shop problem with blocking and no setup times are pre-sented and then adapted to the problem in two different ways; resulting in 28 different heuristics. The heuristics are then compared using the Taillard database. As there is no other work that addresses the problem with blocking and sequence and ma-chine dependent setup times, a database for the setup times was created. The setup time value was uniformly distributed between 1% and 10%, 50%, 100% and 125% of the processing time value. Computational tests are then presented for each of the 28 heuristics, comparing the mean relative deviation of the makespan, the computational time and the percentage of successes of each method. Results show that the heuristics were capable of providing interesting results.

A Hybrid Quantum Evolutionary Algorithm with Improved Decoding Scheme for a Robotic Flow Shop Scheduling Problem

Directory of Open Access Journals (Sweden)

Weidong Lei

2017-01-01

Full Text Available We aim at solving the cyclic scheduling problem with a single robot and flexible processing times in a robotic flow shop, which is a well-known optimization problem in advanced manufacturing systems. The objective of the problem is to find an optimal robot move sequence such that the throughput rate is maximized. We propose a hybrid algorithm based on the Quantum-Inspired Evolutionary Algorithm (QEA and genetic operators for solving the problem. The algorithm integrates three different decoding strategies to convert quantum individuals into robot move sequences. The Q-gate is applied to update the states of Q-bits in each individual. Besides, crossover and mutation operators with adaptive probabilities are used to increase the population diversity. A repairing procedure is proposed to deal with infeasible individuals. Comparison results on both benchmark and randomly generated instances demonstrate that the proposed algorithm is more effective in solving the studied problem in terms of solution quality and computational time.

Common Sleep, Psychiatric, and Somatic Problems According to Work Schedule: an Internet Survey in an Eastern European Country.

Science.gov (United States)

Voinescu, Bogdan I

2018-03-19

A wide range of health problems was investigated, aiming to identify the presence and severity of a set of self-reported and common sleep, psychiatric, and somatic health problems among working professionals in four different shift schedules (morning, evening, rotating, and day) in several cities in Romania. A heterogeneous sample of 488 workers of different professions completed online a battery of tests, namely the Basic Nordic Sleep Questionnaire, the Parasomnia Questionnaire, the Epworth Sleepiness Scale, and the Patient Health Questionnaire, designed to identity symptoms of insomnia, sleepiness, snoring, parasomnia, as well as of depression, anxiety, eating, somatoform, and alcohol use disorders, respectively. The timing and the duration of the sleep, along with the presence of high blood pressure and type 2 diabetes mellitus were also inquired. The prevalence of the different health problems in relation to the type of shift schedule was evaluated with the Pearson Chi-square test. ANOVA was used to calculate the significance of the difference between the means, while associations with different health problems were estimated by binary logistic regression. The most common mental health problems were depression (26%), insomnia (20%), alcohol misuse (18%), and anxiety (17%). No significant differences based on the type of shift in terms of health problems were found, except for high blood pressure and symptoms of panic disorder that were more frequently reported by the workers in early morning shifts. Together with the workers in rotating shifts, they also reported increased sleepiness, poorer sleep quality, and shorter sleep duration. In contrast, the workers in evening shifts reported less severe health problems and longer sleep duration. Working in early morning shifts was found to be associated with poorer health outcomes, while working in rotating and early morning shifts with more severe sleep-related problems.

48 CFR 53.301-1427 - Standard Form 1427, Inventory Schedule A-Construction Sheet (Metals in Mill Product Form).

Science.gov (United States)

2010-10-01

... 48 Federal Acquisition Regulations System 2 2010-10-01 2010-10-01 false Standard Form 1427, Inventory Schedule A-Construction Sheet (Metals in Mill Product Form). 53.301-1427 Section 53.301-1427... Illustrations of Forms 53.301-1427 Standard Form 1427, Inventory Schedule A—Construction Sheet (Metals in Mill...

Cyclic delivery scheduling to customers with different priorities

Directory of Open Access Journals (Sweden)

Katarzyna Zofia Gdowska

2013-12-01

Full Text Available Background: In this paper a cyclic delivery scheduling problem for customers with different priorities is presented. Shops, which are provided with deliveries, are occasionally located in places which are crucial for the proper flow of traffic. In such places coordination of deliveries is crucial; therefore it allows to completely eliminate the phenomenon of the simultaneous arrivals of suppliers. Methods: In this paper the cyclic delivery scheduling problem for customers with different priorities was presented. To this theoretical problem a mix integer programming model was developed. Specific approach to the cyclic delivery scheduling problem is inspired by timetabling problem for urban public transport. Results: Mixed integer programming model was employed for solving four cases of cyclic delivery scheduling problem for customers with different priorities. When the value of the synchronization priority assigned to a single customer raised then the total number of synchronizations in the whole network decreased. In order to compare solutions a synchronization rate was utilized. A simple factor was utilized - the proportion of number of synchronizations of deliveries to a given customer to the total number of synchronizations obtained for the whole network. When the value of synchronization priority raised then the value of synchronization rate of this customer improved significantly. Conclusions: The mixed integer programming model for the cyclic delivery scheduling problem for customers with different priorities presented in this paper can be utilized for generating schedules of serving customers located in places where only one delivery can be received and unloaded at one go and where there is no space for other suppliers to wait in a queue. Such a schedule can be very useful for organizing deliveries to small shops united in a franchising network, since they operate in a way that is very similar to the network presented in this paper

An innovative artificial bee colony algorithm and its application to a practical intercell scheduling problem

Science.gov (United States)

Li, Dongni; Guo, Rongtao; Zhan, Rongxin; Yin, Yong

2018-06-01

In this article, an innovative artificial bee colony (IABC) algorithm is proposed, which incorporates two mechanisms. On the one hand, to provide the evolutionary process with a higher starting level, genetic programming (GP) is used to generate heuristic rules by exploiting the elements that constitute the problem. On the other hand, to achieve a better balance between exploration and exploitation, a leading mechanism is proposed to attract individuals towards a promising region. To evaluate the performance of IABC in solving practical and complex problems, it is applied to the intercell scheduling problem with limited transportation capacity. It is observed that the GP-generated rules incorporate the elements of the most competing human-designed rules, and they are more effective than the human-designed ones. Regarding the leading mechanism, the strategies of the ageing leader and multiple challengers make the algorithm less likely to be trapped in local optima.

Job scheduling in a heterogenous grid environment

Energy Technology Data Exchange (ETDEWEB)

Oliker, Leonid; Biswas, Rupak; Shan, Hongzhang; Smith, Warren

2004-02-11

Computational grids have the potential for solving large-scale scientific problems using heterogeneous and geographically distributed resources. However, a number of major technical hurdles must be overcome before this potential can be realized. One problem that is critical to effective utilization of computational grids is the efficient scheduling of jobs. This work addresses this problem by describing and evaluating a grid scheduling architecture and three job migration algorithms. The architecture is scalable and does not assume control of local site resources. The job migration policies use the availability and performance of computer systems, the network bandwidth available between systems, and the volume of input and output data associated with each job. An extensive performance comparison is presented using real workloads from leading computational centers. The results, based on several key metrics, demonstrate that the performance of our distributed migration algorithms is significantly greater than that of a local scheduling framework and comparable to a non-scalable global scheduling approach.

A comparison of mixed-integer linear programming models for workforce scheduling with position-dependent processing times

Science.gov (United States)

Moreno-Camacho, Carlos A.; Montoya-Torres, Jairo R.; Vélez-Gallego, Mario C.

2018-06-01

Only a few studies in the available scientific literature address the problem of having a group of workers that do not share identical levels of productivity during the planning horizon. This study considers a workforce scheduling problem in which the actual processing time is a function of the scheduling sequence to represent the decline in workers' performance, evaluating two classical performance measures separately: makespan and maximum tardiness. Several mathematical models are compared with each other to highlight the advantages of each approach. The mathematical models are tested with randomly generated instances available from a public e-library.

Project Scheduling Heuristics-Based Standard PSO for Task-Resource Assignment in Heterogeneous Grid

OpenAIRE

Chen, Ruey-Maw; Wang, Chuin-Mu