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

Overlap Algorithms in Flexible Job-shop Scheduling

Directory of Open Access Journals (Sweden)

Celia Gutierrez

2014-06-01

Full Text Available The flexible Job-shop Scheduling Problem (fJSP considers the execution of jobs by a set of candidate resources while satisfying time and technological constraints. This work, that follows the hierarchical architecture, is based on an algorithm where each objective (resource allocation, start-time assignment is solved by a genetic algorithm (GA that optimizes a particular fitness function, and enhances the results by the execution of a set of heuristics that evaluate and repair each scheduling constraint on each operation. The aim of this work is to analyze the impact of some algorithmic features of the overlap constraint heuristics, in order to achieve the objectives at a highest degree. To demonstrate the efficiency of this approach, experimentation has been performed and compared with similar cases, tuning the GA parameters correctly.

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.

A neural network approach to job-shop scheduling.

Science.gov (United States)

Zhou, D N; Cherkassky, V; Baldwin, T R; Olson, D E

1991-01-01

A novel analog computational network is presented for solving NP-complete constraint satisfaction problems, i.e. job-shop scheduling. In contrast to most neural approaches to combinatorial optimization based on quadratic energy cost function, the authors propose to use linear cost functions. As a result, the network complexity (number of neurons and the number of resistive interconnections) grows only linearly with problem size, and large-scale implementations become possible. The proposed approach is related to the linear programming network described by D.W. Tank and J.J. Hopfield (1985), which also uses a linear cost function for a simple optimization problem. It is shown how to map a difficult constraint-satisfaction problem onto a simple neural net in which the number of neural processors equals the number of subjobs (operations) and the number of interconnections grows linearly with the total number of operations. Simulations show that the authors' approach produces better solutions than existing neural approaches to job-shop scheduling, i.e. the traveling salesman problem-type Hopfield approach and integer linear programming approach of J.P.S. Foo and Y. Takefuji (1988), in terms of the quality of the solution and the network complexity.

Proposta de classificação hierarquizada dos modelos de solução para o problema de job shop scheduling A proposition of hierarchical classification for solution models in the job shop scheduling problem

Directory of Open Access Journals (Sweden)

Ricardo Ferrari Pacheco

1999-04-01

Full Text Available Este artigo propõe uma classificação hierarquizada dos modelos utilizados na solução do problema de programação da produção intermitente do tipo job shop, incluindo tanto os que fornecem solução ótima, quanto os modelos heurísticos mais recentes baseados em métodos de busca estendida. Por meio dessa classificação obteve-se um painel amplo dos modelos existentes, evidenciando as diferentes abordagens do problema e suas soluções, com o objetivo de proporcionar uma orientação preliminar na escolha do modelo de job shop scheduling mais adequado.This paper proposes a hierarchical model classification used in the job shop scheduling problem, including those that provide an optimal solution and the more recent ones based on heuristics, called extended search methods. A panel with the existing models is obtained by this classification, and solutions and approach differences are highlighted with the aim of a preliminary orientation on the choice of a more adequate job shop scheduling model.

No-Wait Job Shop Scheduling, a Constraint Propagation Approach

NARCIS (Netherlands)

Lennartz, P.M.

2006-01-01

Multi-machine scheduling problems have earned themselves a reputation of intractability. In this thesis we try to solve a special kind of these problems, the so-called no-wait job shop problems. In an instance of this problem-class we are given a number of operations that are to be executed on a

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.

The Effects of Machine Load Sitnations on Performance of Job Shop and Group Scheduling

OpenAIRE

Torkul, O.

2018-01-01

Perfonnance of job shop and group scheduling ndermulti­natch work input environment was exarnined against two nachine load (light and high load) situations. n order to conduct the analysis, a deterministic computer ;im ulation program was written and used. A job shop {JS) model is applied to the shop floor area and :ompared with a simulation of a similar proposal except hat group technology (GT) model was used in the shop loor area instead. )etailed analysis of the results from applying diffe...

The Effects of Machine Load Sitnations on Performance of Job Shop and Group Scheduling

OpenAIRE

O.TORKUL TORKUL

1998-01-01

Perfonnance of job shop and group scheduling ndermulti­natch work input environment was exarnined against two nachine load (light and high load) situations. n order to conduct the analysis, a deterministic computer ;im ulation program was written and used. A job shop {JS) model is applied to the shop floor area and :ompared with a simulation of a similar proposal except hat group technology (GT) model was used in the shop loor area instead. )etailed analysis of the results from applying diffe...

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 tabu search algorithm for scheduling a single robot in a job-shop environment

NARCIS (Netherlands)

Hurink, Johann L.; Knust, S.

1999-01-01

We consider a single-machine scheduling problem which arises as a subproblem in a job-shop environment where the jobs have to be transported between the machines by a single transport robot. The robot scheduling problem may be regarded as a generalization of the travelling-salesman problem with time

A tabu search algorithm for scheduling a single robot in a job-shop environment

NARCIS (Netherlands)

Hurink, Johann L.; Knust, Sigrid

2002-01-01

We consider a single-machine scheduling problem which arises as a subproblem in a job-shop environment where the jobs have to be transported between the machines by a single transport robot. The robot scheduling problem may be regarded as a generalization of the travelling-salesman problem with time

On-line scheduling of two-machine open shops where jobs arrive over time

NARCIS (Netherlands)

Chen, B.; Vestjens, A.P.A.; Woeginger, G.J.

1998-01-01

We investigate the problem of on-line scheduling two-machine open shops with the objective of minimizing the makespan.Jobs arrive independently over time, and the existence of a job is not known until its arrival. In the clairvoyant on-line model, the processing requirement of every job becomes

EFFICIENT MULTI-OBJECTIVE EVOLUTIONARY ALGORITHM FOR JOB SHOP SCHEDULING

Institute of Scientific and Technical Information of China (English)

Lei Deming; Wu Zhiming

2005-01-01

A new representation method is first presented based on priority rules. According to this method, each entry in the chromosome indicates that in the procedure of the Giffler and Thompson (GT) algorithm, the conflict occurring in the corresponding machine is resolved by the corresponding priority rule. Then crowding-measure multi-objective evolutionary algorithm (CMOEA) is designed,in which both archive maintenance and fitness assignment use crowding measure. Finally the comparisons between CMOEA and SPEA in solving 15 scheduling problems demonstrate that CMOEA is suitable to job shop scheduling.

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.

Generation of Look-Up Tables for Dynamic Job Shop Scheduling Decision Support Tool

Science.gov (United States)

Oktaviandri, Muchamad; Hassan, Adnan; Mohd Shaharoun, Awaluddin

2016-02-01

Majority of existing scheduling techniques are based on static demand and deterministic processing time, while most job shop scheduling problem are concerned with dynamic demand and stochastic processing time. As a consequence, the solutions obtained from the traditional scheduling technique are ineffective wherever changes occur to the system. Therefore, this research intends to develop a decision support tool (DST) based on promising artificial intelligent that is able to accommodate the dynamics that regularly occur in job shop scheduling problem. The DST was designed through three phases, i.e. (i) the look-up table generation, (ii) inverse model development and (iii) integration of DST components. This paper reports the generation of look-up tables for various scenarios as a part in development of the DST. A discrete event simulation model was used to compare the performance among SPT, EDD, FCFS, S/OPN and Slack rules; the best performances measures (mean flow time, mean tardiness and mean lateness) and the job order requirement (inter-arrival time, due dates tightness and setup time ratio) which were compiled into look-up tables. The well-known 6/6/J/Cmax Problem from Muth and Thompson (1963) was used as a case study. In the future, the performance measure of various scheduling scenarios and the job order requirement will be mapped using ANN inverse model.

A Simulated Annealing-Based Heuristic Algorithm for Job Shop Scheduling to Minimize Lateness

Directory of Open Access Journals (Sweden)

Rui Zhang

2013-04-01

Full Text Available A decomposition-based optimization algorithm is proposed for solving large job shop scheduling problems with the objective of minimizing the maximum lateness. First, we use the constraint propagation theory to derive the orientation of a portion of disjunctive arcs. Then we use a simulated annealing algorithm to find a decomposition policy which satisfies the maximum number of oriented disjunctive arcs. Subsequently, each subproblem (corresponding to a subset of operations as determined by the decomposition policy is successively solved with a simulated annealing algorithm, which leads to a feasible solution to the original job shop scheduling problem. Computational experiments are carried out for adapted benchmark problems, and the results show the proposed algorithm is effective and efficient in terms of solution quality and time performance.

Iterated greedy algorithms to minimize the total family flow time for job-shop scheduling with job families and sequence-dependent set-ups

Science.gov (United States)

Kim, Ji-Su; Park, Jung-Hyeon; Lee, Dong-Ho

2017-10-01

This study addresses a variant of job-shop scheduling in which jobs are grouped into job families, but they are processed individually. The problem can be found in various industrial systems, especially in reprocessing shops of remanufacturing systems. If the reprocessing shop is a job-shop type and has the component-matching requirements, it can be regarded as a job shop with job families since the components of a product constitute a job family. In particular, sequence-dependent set-ups in which set-up time depends on the job just completed and the next job to be processed are also considered. The objective is to minimize the total family flow time, i.e. the maximum among the completion times of the jobs within a job family. A mixed-integer programming model is developed and two iterated greedy algorithms with different local search methods are proposed. Computational experiments were conducted on modified benchmark instances and the results are reported.

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.

JOB SHOP SCHEDULING BIOBJETIVO MEDIANTE ENFRIAMIENTO SIMULADO Y ENFOQUE DE PARETO JOB-SHOP SCHEDULING: BIO-OBJECTIVE THROUGH SIMULATED COOLING AND PARETO PRINCIPLE

Directory of Open Access Journals (Sweden)

Juan Carlos Osorio

2012-12-01

Full Text Available El problema del scheduling es uno de los problemas más ampliamente tratados en la literatura; sin embargo, es un problema complejo NP hard. Cuando, además, se involucra más de un objetivo, este problema se convierte en uno de los más complejos en el campo de la investigación de operaciones. Se presenta entonces un modelo biobjetivo para el job shop scheduling que incluye el makespan y el tiempo de flujo medio. Para resolver el modelo se ha utilizado una propuesta que incluye el uso del meta-heurístico Recocido Simulado (SA y el enfoque de Pareto. Este modelo es evaluado en tres problemas presentados en la literatura de tamaños 6x6, 10x5 y 10x10. Los resultados del modelo se comparan con otros meta-heurísticos y se encuentra que este modelo presenta buenos resultados en los tres problemas evaluados.The scheduling problem is one of the most widely treated problems in literature; however, it is an NP hard complex problem. Also, when more than one objective is involved, this problem becomes one of the most complex ones in the field of operations research. A bio-objective model is then emerged for the Job-Shop Scheduling, including makespan and mean flow time. For solving the model a proposal which includes the use of Simulated Annealing (SA metaheuristic and Pareto Principle. This model is evaluated in three problems described in literature with the following sizes: 6x6, 10x5 and 10x10. Results of the model are compared to other metaheuristics and it has been found that this model shows good results in the three problems evaluated.

Review of job shop scheduling research and its new perspectives under Industry 4.0

OpenAIRE

Zhang, Jian; Ding, Guofu; Zou, Yisheng; Qin, Sheng-feng; Fu, Jianlin

2017-01-01

Traditional job shop scheduling is concentrated on centralized scheduling or semi-distributed scheduling. Under the Industry 4.0, the scheduling should deal with a smart and distributed manufacturing system supported by novel and emerging manufacturing technologies such as mass customization, Cyber-Physics Systems, Digital Twin, and SMAC (Social, Mobile, Analytics, Cloud). The scheduling research needs to shift its focus to smart distributed scheduling modeling and optimization. In order to t...

Parallel Branch-and-Bound Methods for the Job Shop Scheduling

DEFF Research Database (Denmark)

Clausen, Jens; Perregaard, Michael

1998-01-01

Job-shop scheduling (JSS) problems are among the more difficult to solve in the class of NP-complete problems. The only successful approach has been branch-and-bound based algorithms, but such algorithms depend heavily on good bound functions. Much work has been done to identify such functions...... for the JSS problem, but with limited success. Even with recent methods, it is still not possible to solve problems substantially larger than 10 machines and 10 jobs. In the current study, we focus on parallel methods for solving JSS problems. We implement two different parallel branch-and-bound algorithms...

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

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.

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

Constraint satisfaction adaptive neural network and heuristics combined approaches for generalized job-shop scheduling.

Science.gov (United States)

Yang, S; Wang, D

2000-01-01

This paper presents a constraint satisfaction adaptive neural network, together with several heuristics, to solve the generalized job-shop scheduling problem, one of NP-complete constraint satisfaction problems. The proposed neural network can be easily constructed and can adaptively adjust its weights of connections and biases of units based on the sequence and resource constraints of the job-shop scheduling problem during its processing. Several heuristics that can be combined with the neural network are also presented. In the combined approaches, the neural network is used to obtain feasible solutions, the heuristic algorithms are used to improve the performance of the neural network and the quality of the obtained solutions. Simulations have shown that the proposed neural network and its combined approaches are efficient with respect to the quality of solutions and the solving speed.

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.

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.

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.

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.

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.

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.

Evaluation and Selection of Best Priority Sequencing Rule in Job Shop Scheduling using Hybrid MCDM Technique

Science.gov (United States)

Kiran Kumar, Kalla; Nagaraju, Dega; Gayathri, S.; Narayanan, S.

2017-05-01

Priority Sequencing Rules provide the guidance for the order in which the jobs are to be processed at a workstation. The application of different priority rules in job shop scheduling gives different order of scheduling. More experimentation needs to be conducted before a final choice is made to know the best priority sequencing rule. Hence, a comprehensive method of selecting the right choice is essential in managerial decision making perspective. This paper considers seven different priority sequencing rules in job shop scheduling. For evaluation and selection of the best priority sequencing rule, a set of eight criteria are considered. The aim of this work is to demonstrate the methodology of evaluating and selecting the best priority sequencing rule by using hybrid multi criteria decision making technique (MCDM), i.e., analytical hierarchy process (AHP) with technique for order preference by similarity to ideal solution (TOPSIS). The criteria weights are calculated by using AHP whereas the relative closeness values of all priority sequencing rules are computed based on TOPSIS with the help of data acquired from the shop floor of a manufacturing firm. Finally, from the findings of this work, the priority sequencing rules are ranked from most important to least important. The comprehensive methodology presented in this paper is very much essential for the management of a workstation to choose the best priority sequencing rule among the available alternatives for processing the jobs with maximum benefit.

A controlled genetic algorithm by fuzzy logic and belief functions for job-shop scheduling.

Science.gov (United States)

Hajri, S; Liouane, N; Hammadi, S; Borne, P

2000-01-01

Most scheduling problems are highly complex combinatorial problems. However, stochastic methods such as genetic algorithm yield good solutions. In this paper, we present a controlled genetic algorithm (CGA) based on fuzzy logic and belief functions to solve job-shop scheduling problems. For better performance, we propose an efficient representational scheme, heuristic rules for creating the initial population, and a new methodology for mixing and computing genetic operator probabilities.

Production Scheduling in Complex Job Shops from an Industrie 4.0 Perspective: A Review and Challenges in the Semiconductor Industry

OpenAIRE

Waschneck, Bernd; Bauernhansl, Thomas; Altenmüller, Thomas; Kyek, Andreas

2017-01-01

On the one hand, Industrie 4.0 has recently emerged as the keyword for increasing productivity in the 21st century. On the other hand, production scheduling in a Complex Job Shop (CJS) environment, such as wafer fabrication facilities, has drawn interest of researchers dating back to the 1950s [65, 18]. Although both research areas overlap, there seems to be very little interchange of ideas. This review presents and assesses production scheduling techniques in complex job shops from an Indust...

Job shop scheduling by simulated annealing

NARCIS (Netherlands)

Laarhoven, van P.J.M.; Aarts, E.H.L.; Lenstra, J.K.

1992-01-01

We describe an approximation algorithm for the problem of finding the minimum makespan in a job shop. The algorithm is based on simulated annealing, a generalization of the well known iterative improvement approach to combinatorial optimization problems. The generalization involves the acceptance of

Near-Optimal Heuristics for Just-In-Time Jobs Maximization in Flow Shop Scheduling

Directory of Open Access Journals (Sweden)

Helio Yochihiro Fuchigami

2018-04-01

Full Text Available The number of just-in-time jobs maximization in a permutation flow shop scheduling problem is considered. A mixed integer linear programming model to represent the problem as well as solution approaches based on enumeration and constructive heuristics were proposed and computationally implemented. Instances with up to 10 jobs and five machines are solved by the mathematical model in an acceptable running time (3.3 min on average while the enumeration method consumes, on average, 1.5 s. The 10 constructive heuristics proposed show they are practical especially for large-scale instances (up to 100 jobs and 20 machines, with very good-quality results and efficient running times. The best two heuristics obtain near-optimal solutions, with only 0.6% and 0.8% average relative deviations. They prove to be better than adaptations of the NEH heuristic (well-known for providing very good solutions for makespan minimization in flow shop for the considered problem.

A Review On Job Shop Scheduling Using Non-Conventional Optimization Algorithm

OpenAIRE

K.Mallikarjuna; Venkatesh.G

2014-01-01

A great deal of research has been focused on solving job shop scheduling problem (∫J), over the last four decades, resulting in a wide variety of approaches. Recently much effort has been concentrated on hybrid methods to solve ∫J, as a single technique cannot solve this stubborn problem. As a result much effort has recently been concentrated on techniques that lead to combinatorial optimization methods and a meta-strategy which guides the search out of local optima. In this p...

FLOW-SHOP SCHEDULING WITH MULTIPLE OPERATIONS AND TIME LAGS

NARCIS (Netherlands)

RIEZEBOS, J; GAALMAN, GJC; GUPTA, JND

A scheduling system is proposed and developed for a special type of flow shop. Ln this flow shop there is one machine at each stage. A job may require multiple operations at each stage. The first operation of a job on stage j cannot start until the last operation of the job on stage j - 1 has

A PMBGA to Optimize the Selection of Rules for Job Shop Scheduling Based on the Giffler-Thompson Algorithm

Directory of Open Access Journals (Sweden)

Rui Zhang

2012-01-01

Full Text Available Most existing research on the job shop scheduling problem has been focused on the minimization of makespan (i.e., the completion time of the last job. However, in the fiercely competitive market nowadays, delivery punctuality is more important for maintaining a high service reputation. So in this paper, we aim at solving job shop scheduling problems with the total weighted tardiness objective. Several dispatching rules are adopted in the Giffler-Thompson algorithm for constructing active schedules. It is noticeable that the rule selections for scheduling consecutive operations are not mutually independent but actually interrelated. Under such circumstances, a probabilistic model-building genetic algorithm (PMBGA is proposed to optimize the sequence of selected rules. First, we use Bayesian networks to model the distribution characteristics of high-quality solutions in the population. Then, the new generation of individuals is produced by sampling the established Bayesian network. Finally, some elitist individuals are further improved by a special local search module based on parameter perturbation. The superiority of the proposed approach is verified by extensive computational experiments and comparisons.

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.

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.

A Comparison of the DISASTER (Trademark) Scheduling Software with a Simultaneous Scheduling Algorithm for Minimizing Maximum Tardiness in Job Shops

Science.gov (United States)

1993-09-01

goal ( Heizer , Render , and Stair, 1993:94). Integer Prgronmming. Integer programming is a general purpose approach used to optimally solve job shop...Scheduling," Operations Research Journal. 29, No 4: 646-667 (July-August 1981). Heizer , Jay, Barry Render and Ralph M. Stair, Jr. Production and Operations

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

An Improved Version of Discrete Particle Swarm Optimization for Flexible Job Shop Scheduling Problem with Fuzzy Processing Time

Directory of Open Access Journals (Sweden)

Song Huang

2016-01-01

Full Text Available The fuzzy processing time occasionally exists in job shop scheduling problem of flexible manufacturing system. To deal with fuzzy processing time, fuzzy flexible job shop model was established in several papers and has attracted numerous researchers’ attention recently. In our research, an improved version of discrete particle swarm optimization (IDPSO is designed to solve flexible job shop scheduling problem with fuzzy processing time (FJSPF. In IDPSO, heuristic initial methods based on triangular fuzzy number are developed, and a combination of six initial methods is applied to initialize machine assignment and random method is used to initialize operation sequence. Then, some simple and effective discrete operators are employed to update particle’s position and generate new particles. In order to guide the particles effectively, we extend global best position to a set with several global best positions. Finally, experiments are designed to investigate the impact of four parameters in IDPSO by Taguchi method, and IDPSO is tested on five instances and compared with some state-of-the-art algorithms. The experimental results show that the proposed algorithm can obtain better solutions for FJSPF and is more competitive than the compared algorithms.

REPAIR SHOP JOB SCHEDULING WITH PARALLEL OPERATORS AND MULTIPLE CONSTRAINTS USING SIMULATED ANNEALING

Directory of Open Access Journals (Sweden)

N. Shivasankaran

2013-04-01

Full Text Available Scheduling problems are generally treated as NP andash; complete combinatorial optimization problems which is a multi-objective and multi constraint one. Repair shop Job sequencing and operator allocation is one such NP andash; complete problem. For such problems, an efficient technique is required that explores a wide range of solution space. This paper deals with Simulated Annealing Technique, a Meta - heuristic to solve the complex Car Sequencing and Operator Allocation problem in a car repair shop. The algorithm is tested with several constraint settings and the solution quality exceeds the results reported in the literature with high convergence speed and accuracy. This algorithm could be considered as quite effective while other heuristic routine fails.

PENGEMBANGAN ALGORITMA PENJADUALAN PRODUKSI JOB SHOP UNTUK MEMINIMUMKAN TOTAL BIAYA EARLINESS DAN TARDINESS

Directory of Open Access Journals (Sweden)

Dian Retno Sari Dewi

2005-12-01

Full Text Available This paper develops job shop production scheduling using Non Delay algorithm through forward and backward-forward algorithm to minimize total earliness and tardiness costs. Backward approach has some disadvantages, such as, if the job is scheduled in backward, there is a possibility that the infeasible situation occurs, in which the job is scheduled at t<0. This paper used hypothetic data generated randomly. This job shop scheduling algorithm development was validated using LINDO software to check the effectiveness heuristic method, compared with the optimation method. The validation proves that the result of backward-forward scheduling method is better than the result of forward scheduling method.

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.

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.

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.

Job shop scheduling model for non-identic machine with fixed delivery time to minimize tardiness

Science.gov (United States)

Kusuma, K. K.; Maruf, A.

2016-02-01

Scheduling non-identic machines problem with low utilization characteristic and fixed delivery time are frequent in manufacture industry. This paper propose a mathematical model to minimize total tardiness for non-identic machines in job shop environment. This model will be categorized as an integer linier programming model and using branch and bound algorithm as the solver method. We will use fixed delivery time as main constraint and different processing time to process a job. The result of this proposed model shows that the utilization of production machines can be increase with minimal tardiness using fixed delivery time as constraint.

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.

Ant colony optimisation for scheduling of flexible job shop with multi-resources requirements

Directory of Open Access Journals (Sweden)

Kalinowski Krzysztof

2017-01-01

Full Text Available The paper presents application of ant colony optimisation algorithm for scheduling multi-resources operations in flexible job shop type of production systems. Operations that require the participation of two or more resources are common in industrial practice, when planning are subject not only machines, but also other additional resources (personnel, tools, etc.. Resource requirements of operation are indicated indirectly by resource groups. The most important parameters of the resource model and resource groups are also described. A basic assumptions for ant colony algorithm used for scheduling in the considered model with multiresources requirements of operations is discussed. The main result of the research is the schema of metaheuristic that enables searching best-score solutions in manufacturing systems satisfying presented constraints.

A Bee Evolutionary Guiding Nondominated Sorting Genetic Algorithm II for Multiobjective Flexible Job-Shop Scheduling

Directory of Open Access Journals (Sweden)

Qianwang Deng

2017-01-01

Full Text Available Flexible job-shop scheduling problem (FJSP is an NP-hard puzzle which inherits the job-shop scheduling problem (JSP characteristics. This paper presents a bee evolutionary guiding nondominated sorting genetic algorithm II (BEG-NSGA-II for multiobjective FJSP (MO-FJSP with the objectives to minimize the maximal completion time, the workload of the most loaded machine, and the total workload of all machines. It adopts a two-stage optimization mechanism during the optimizing process. In the first stage, the NSGA-II algorithm with T iteration times is first used to obtain the initial population N, in which a bee evolutionary guiding scheme is presented to exploit the solution space extensively. In the second stage, the NSGA-II algorithm with GEN iteration times is used again to obtain the Pareto-optimal solutions. In order to enhance the searching ability and avoid the premature convergence, an updating mechanism is employed in this stage. More specifically, its population consists of three parts, and each of them changes with the iteration times. What is more, numerical simulations are carried out which are based on some published benchmark instances. Finally, the effectiveness of the proposed BEG-NSGA-II algorithm is shown by comparing the experimental results and the results of some well-known algorithms already existed.

A Bee Evolutionary Guiding Nondominated Sorting Genetic Algorithm II for Multiobjective Flexible Job-Shop Scheduling.

Science.gov (United States)

Deng, Qianwang; Gong, Guiliang; Gong, Xuran; Zhang, Like; Liu, Wei; Ren, Qinghua

2017-01-01

Flexible job-shop scheduling problem (FJSP) is an NP-hard puzzle which inherits the job-shop scheduling problem (JSP) characteristics. This paper presents a bee evolutionary guiding nondominated sorting genetic algorithm II (BEG-NSGA-II) for multiobjective FJSP (MO-FJSP) with the objectives to minimize the maximal completion time, the workload of the most loaded machine, and the total workload of all machines. It adopts a two-stage optimization mechanism during the optimizing process. In the first stage, the NSGA-II algorithm with T iteration times is first used to obtain the initial population N , in which a bee evolutionary guiding scheme is presented to exploit the solution space extensively. In the second stage, the NSGA-II algorithm with GEN iteration times is used again to obtain the Pareto-optimal solutions. In order to enhance the searching ability and avoid the premature convergence, an updating mechanism is employed in this stage. More specifically, its population consists of three parts, and each of them changes with the iteration times. What is more, numerical simulations are carried out which are based on some published benchmark instances. Finally, the effectiveness of the proposed BEG-NSGA-II algorithm is shown by comparing the experimental results and the results of some well-known algorithms already existed.

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.

COMPARISON BETWEEN MIXED INTEGER PROGRAMMING WITH HEURISTIC METHOD FOR JOB SHOP SCHEDULING WITH SEPARABLE SEQUENCE-DEPENDENT SETUPS

Directory of Open Access Journals (Sweden)

I Gede Agus Widyadana

2001-01-01

Full Text Available The decisions to choose appropriate tools for solving industrial problems are not just tools that achieve optimal solution only but it should consider computation time too. One of industrial problems that still difficult to achieve both criteria is scheduling problem. This paper discuss comparison between mixed integer programming which result optimal solution and heuristic method to solve job shop scheduling problem with separable sequence-dependent setup. The problems are generated and the result shows that the heuristic methods still cannot satisfy optimal solution.

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.

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.

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.

Genetic programming for evolving due-date assignment models in job shop environments.

Science.gov (United States)

Nguyen, Su; Zhang, Mengjie; Johnston, Mark; Tan, Kay Chen

2014-01-01

Due-date assignment plays an important role in scheduling systems and strongly influences the delivery performance of job shops. Because of the stochastic and dynamic nature of job shops, the development of general due-date assignment models (DDAMs) is complicated. In this study, two genetic programming (GP) methods are proposed to evolve DDAMs for job shop environments. The experimental results show that the evolved DDAMs can make more accurate estimates than other existing dynamic DDAMs with promising reusability. In addition, the evolved operation-based DDAMs show better performance than the evolved DDAMs employing aggregate information of jobs and machines.

Un algoritmo genético para el problema de Job Shop Flexible A genetic algorithm for the Flexible Job Shop problem

Directory of Open Access Journals (Sweden)

Rosa Medina Durán

2011-06-01

Full Text Available En este estudio se propone e implementa computacionalmente un algoritmo genético secuencial para resolver el problema del Job Shop Flexible (existente en la Gestión de Operaciones, el cual es parte de la familia de los problemas de programación de tareas o trabajos (Scheduling en un taller que funciona a pedido. Surge como una generalización del problema del Job Shop y permite optimizar el uso de los recursos (máquinas con mayor flexibilidad, ya que cada máquina puede realizar más de una operación. Este problema ha sido estudiado por numerosos autores, los que han propuesto diversos modelos matemáticos y enfoques heurísticos. Debido a la naturaleza combinatoria, los métodos exactos que resuelven modelos matemáticos encuentran soluciones sólo para instancias pequeñas o simples del problema mencionado. Los resultados muestran la efectividad del algoritmo propuesto para entregar buenas soluciones en tiempos computacionales razonables en más de 130 instancias encontradas en la literatura.This study proposes and computationally implements a sequential genetic algorithm to solve the Flexible Job Shop problem (found in Operations Management, which is part of the family of job or task scheduling problems in a shop that works on demand. It is a generalization of the Job Shop problem, and allows optimizing the use of resources (machines in the shop, with greater flexibility, since each machine can perform more than one operation. This problem has been studied by many authors, who have proposed various mathematical models and heuristic approaches. Due to the combinatorial nature of the problem, the exact methods that solve the mathematical models are often solutions for small and simple instances of the problem. The results show the effectiveness of the proposed algorithm to provide good solutions in reasonable computational times in over 130 instances found in the literatura.

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.

DESIGN OF A HYPERHEURISTIC FOR PRODUCTION SCHEDULING IN JOB SHOP ENVIRONMENTS DISEÑO DE UNA HIPERHEURISTICA PARA LA PROGRAMACION DE LA PRODUCCIÓN EN AMBIENTES JOB SHOP

Directory of Open Access Journals (Sweden)

Omar Danilo Castrillón

2010-08-01

Full Text Available The objective of the present work is to diminish the total process time (Makespan and to increase the machine process time, by diminishing the idle time in a job-shop environment. Through the design of a hyper-heuristic based on an ant colony and genetic algorithms. This work is developed in two phases: in the first phase, a hyper-heuristic identification and definition is carried out for sequencing processes in job shop environments. In the second phase, the system effectiveness in the traditional production programming is shown. In the investigation project, an enterprise from the metal mechanic sector was chosen, where by means of a combination of an ant colony and genetic algorithms, the optimal route for an order is scheduled, achieving the optimization or suboptimization of its respective total process time in an upper percentage of 95%.El objetivo del presente trabajo es disminuir el tiempo de proceso (Makespan e incrementar el tiempo de trabajo de las maquinas, diminuyendo el tiempo de ocio en ambientes de Job Shop, a través del diseño de una Hiper-heurística basada en colonia de hormigas y algoritmos genéticos. Este trabajo se desarrolla en dos etapas: en la primera se realiza la definición e identificación de una Hiper-heurística para la secuenciación de procesos en ambientes Job shop. En la segunda etapa, es mostrada la efectividad del sistema en la programación de la producción. En el proyecto de investigación, se seleccionó una empresa del sector metalmecánico, donde por medio de una combinación de colonia de hormigas y algoritmos genéticos, se programa la ruta óptima para un pedido, logrando la optimización o suboptimización de su respectivo tiempo total de proceso en un porcentaje superior al 95%.

Automatic programming via iterated local search for dynamic job shop scheduling.

Science.gov (United States)

Nguyen, Su; Zhang, Mengjie; Johnston, Mark; Tan, Kay Chen

2015-01-01

Dispatching rules have been commonly used in practice for making sequencing and scheduling decisions. Due to specific characteristics of each manufacturing system, there is no universal dispatching rule that can dominate in all situations. Therefore, it is important to design specialized dispatching rules to enhance the scheduling performance for each manufacturing environment. Evolutionary computation approaches such as tree-based genetic programming (TGP) and gene expression programming (GEP) have been proposed to facilitate the design task through automatic design of dispatching rules. However, these methods are still limited by their high computational cost and low exploitation ability. To overcome this problem, we develop a new approach to automatic programming via iterated local search (APRILS) for dynamic job shop scheduling. The key idea of APRILS is to perform multiple local searches started with programs modified from the best obtained programs so far. The experiments show that APRILS outperforms TGP and GEP in most simulation scenarios in terms of effectiveness and efficiency. The analysis also shows that programs generated by APRILS are more compact than those obtained by genetic programming. An investigation of the behavior of APRILS suggests that the good performance of APRILS comes from the balance between exploration and exploitation in its search mechanism.

A Hyper-Heuristic Ensemble Method for Static Job-Shop Scheduling.

Science.gov (United States)

Hart, Emma; Sim, Kevin

2016-01-01

We describe a new hyper-heuristic method NELLI-GP for solving job-shop scheduling problems (JSSP) that evolves an ensemble of heuristics. The ensemble adopts a divide-and-conquer approach in which each heuristic solves a unique subset of the instance set considered. NELLI-GP extends an existing ensemble method called NELLI by introducing a novel heuristic generator that evolves heuristics composed of linear sequences of dispatching rules: each rule is represented using a tree structure and is itself evolved. Following a training period, the ensemble is shown to outperform both existing dispatching rules and a standard genetic programming algorithm on a large set of new test instances. In addition, it obtains superior results on a set of 210 benchmark problems from the literature when compared to two state-of-the-art hyper-heuristic approaches. Further analysis of the relationship between heuristics in the evolved ensemble and the instances each solves provides new insights into features that might describe similar instances.

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.

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.

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.

Ant Foraging Behavior for Job Shop Problem

Directory of Open Access Journals (Sweden)

Mahad Diyana Abdul

2016-01-01

Full Text Available Ant Colony Optimization (ACO is a new algorithm approach, inspired by the foraging behavior of real ants. It has frequently been applied to many optimization problems and one such problem is in solving the job shop problem (JSP. The JSP is a finite set of jobs processed on a finite set of machine where once a job initiates processing on a given machine, it must complete processing and uninterrupted. In solving the Job Shop Scheduling problem, the process is measure by the amount of time required in completing a job known as a makespan and minimizing the makespan is the main objective of this study. In this paper, we developed an ACO algorithm to minimize the makespan. A real set of problems from a metal company in Johor bahru, producing 20 parts with jobs involving the process of clinching, tapping and power press respectively. The result from this study shows that the proposed ACO heuristics managed to produce a god result in a short time.

Flow-shop scheduling problem under uncertainties: Review and trends

OpenAIRE

Eliana María González-Neira; Jairo R. Montoya-Torres; David Barrera

2017-01-01

Among the different tasks in production logistics, job scheduling is one of the most important at the operational decision-making level to enable organizations to achieve competiveness. Scheduling consists in the allocation of limited resources to activities over time in order to achieve one or more optimization objectives. Flow-shop (FS) scheduling problems encompass the sequencing processes in environments in which the activities or operations are performed in a serial flow. This type of co...

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.

Three hybridization models based on local search scheme for job shop scheduling problem

Science.gov (United States)

Balbi Fraga, Tatiana

2015-05-01

This work presents three different hybridization models based on the general schema of Local Search Heuristics, named Hybrid Successive Application, Hybrid Neighborhood, and Hybrid Improved Neighborhood. Despite similar approaches might have already been presented in the literature in other contexts, in this work these models are applied to analyzes the solution of the job shop scheduling problem, with the heuristics Taboo Search and Particle Swarm Optimization. Besides, we investigate some aspects that must be considered in order to achieve better solutions than those obtained by the original heuristics. The results demonstrate that the algorithms derived from these three hybrid models are more robust than the original algorithms and able to get better results than those found by the single Taboo Search.

Analysis of dispatching rules in a stochastic dynamic job shop manufacturing system with sequence-dependent setup times

Science.gov (United States)

Sharma, Pankaj; Jain, Ajai

2014-12-01

Stochastic dynamic job shop scheduling problem with consideration of sequence-dependent setup times are among the most difficult classes of scheduling problems. This paper assesses the performance of nine dispatching rules in such shop from makespan, mean flow time, maximum flow time, mean tardiness, maximum tardiness, number of tardy jobs, total setups and mean setup time performance measures viewpoint. A discrete event simulation model of a stochastic dynamic job shop manufacturing system is developed for investigation purpose. Nine dispatching rules identified from literature are incorporated in the simulation model. The simulation experiments are conducted under due date tightness factor of 3, shop utilization percentage of 90% and setup times less than processing times. Results indicate that shortest setup time (SIMSET) rule provides the best performance for mean flow time and number of tardy jobs measures. The job with similar setup and modified earliest due date (JMEDD) rule provides the best performance for makespan, maximum flow time, mean tardiness, maximum tardiness, total setups and mean setup time measures.

An corrigendum on the paper : Solving the job-shop scheduling problem optimally by dynamic programming (Computers and Operations Research 39(12) (2968–2977) (S0305054812000500) (10.1016/j.cor.2012.02.024))

NARCIS (Netherlands)

van Hoorn, Jelke J.; Nogueira, Agustín; Ojea, Ignacio; Gromicho Dos Santos, Joaquim Antonio

2017-01-01

In [1] an algorithm is proposed for solving the job-shop scheduling problem optimally using a dynamic programming strategy. This is, according to our knowledge, the first exact algorithm for the Job Shop problem which is not based on integer linear programming and branch and bound. Despite the

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

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.

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.

Bi-Objective Flexible Job-Shop Scheduling Problem Considering Energy Consumption under Stochastic Processing Times.

Science.gov (United States)

Yang, Xin; Zeng, Zhenxiang; Wang, Ruidong; Sun, Xueshan

2016-01-01

This paper presents a novel method on the optimization of bi-objective Flexible Job-shop Scheduling Problem (FJSP) under stochastic processing times. The robust counterpart model and the Non-dominated Sorting Genetic Algorithm II (NSGA-II) are used to solve the bi-objective FJSP with consideration of the completion time and the total energy consumption under stochastic processing times. The case study on GM Corporation verifies that the NSGA-II used in this paper is effective and has advantages to solve the proposed model comparing with HPSO and PSO+SA. The idea and method of the paper can be generalized widely in the manufacturing industry, because it can reduce the energy consumption of the energy-intensive manufacturing enterprise with less investment when the new approach is applied in existing systems.

Forecasting of indirect consumables for a Job Shop

Science.gov (United States)

Shakeel, M.; Khan, S.; Khan, W. A.

2016-08-01

A job shop has an arrangement where similar machines (Direct consumables) are grouped together and use indirect consumables to produce a product. The indirect consumables include hack saw blades, emery paper, painting brush etc. The job shop is serving various orders at a particular time for the optimal operation of job shop. Forecasting is required to predict the demand of direct and indirect consumables in a job shop. Forecasting is also needed to manage lead time, optimize inventory cost and stock outs. The objective of this research is to obtain the forecast for indirect consumables. The paper shows how job shop can manage their indirect consumables more accurately by establishing a new technique of forecasting. This results in profitable use of job shop by multiple users.

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.

Approximation algorithms for the parallel flow shop problem

NARCIS (Netherlands)

X. Zhang (Xiandong); S.L. van de Velde (Steef)

2012-01-01

textabstractWe consider the NP-hard problem of scheduling n jobs in m two-stage parallel flow shops so as to minimize the makespan. This problem decomposes into two subproblems: assigning the jobs to parallel flow shops; and scheduling the jobs assigned to the same flow shop by use of Johnson's

Flow-shop scheduling problem under uncertainties: Review and trends

Directory of Open Access Journals (Sweden)

Eliana María González-Neira

2017-03-01

Full Text Available Among the different tasks in production logistics, job scheduling is one of the most important at the operational decision-making level to enable organizations to achieve competiveness. Scheduling consists in the allocation of limited resources to activities over time in order to achieve one or more optimization objectives. Flow-shop (FS scheduling problems encompass the sequencing processes in environments in which the activities or operations are performed in a serial flow. This type of configuration includes assembly lines and the chemical, electronic, food, and metallurgical industries, among others. Scheduling has been mostly investigated for the deterministic cases, in which all parameters are known in advance and do not vary over time. Nevertheless, in real-world situations, events are frequently subject to uncertainties that can affect the decision-making process. Thus, it is important to study scheduling and sequencing activities under uncertainties since they can cause infeasibilities and disturbances. The purpose of this paper is to provide a general overview of the FS scheduling problem under uncertainties and its role in production logistics and to draw up opportunities for further research. To this end, 100 papers about FS and flexible flow-shop scheduling problems published from 2001 to October 2016 were analyzed and classified. Trends in the reviewed literature are presented and finally some research opportunities in the field are proposed.

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.

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.

Solving the flexible job shop problem by hybrid metaheuristics-based multiagent model

Science.gov (United States)

Nouri, Houssem Eddine; Belkahla Driss, Olfa; Ghédira, Khaled

2018-03-01

The flexible job shop scheduling problem (FJSP) is a generalization of the classical job shop scheduling problem that allows to process operations on one machine out of a set of alternative machines. The FJSP is an NP-hard problem consisting of two sub-problems, which are the assignment and the scheduling problems. In this paper, we propose how to solve the FJSP by hybrid metaheuristics-based clustered holonic multiagent model. First, a neighborhood-based genetic algorithm (NGA) is applied by a scheduler agent for a global exploration of the search space. Second, a local search technique is used by a set of cluster agents to guide the research in promising regions of the search space and to improve the quality of the NGA final population. The efficiency of our approach is explained by the flexible selection of the promising parts of the search space by the clustering operator after the genetic algorithm process, and by applying the intensification technique of the tabu search allowing to restart the search from a set of elite solutions to attain new dominant scheduling solutions. Computational results are presented using four sets of well-known benchmark literature instances. New upper bounds are found, showing the effectiveness of the presented approach.

Outsourcing and scheduling for a two-machine flow shop with release times

Science.gov (United States)

Ahmadizar, Fardin; Amiri, Zeinab

2018-03-01

This article addresses a two-machine flow shop scheduling problem where jobs are released intermittently and outsourcing is allowed. The first operations of outsourced jobs are processed by the first subcontractor, they are transported in batches to the second subcontractor for processing their second operations, and finally they are transported back to the manufacturer. The objective is to select a subset of jobs to be outsourced, to schedule both the in-house and the outsourced jobs, and to determine a transportation plan for the outsourced jobs so as to minimize the sum of the makespan and the outsourcing and transportation costs. Two mathematical models of the problem and several necessary optimality conditions are presented. A solution approach is then proposed by incorporating the dominance properties with an ant colony algorithm. Finally, computational experiments are conducted to evaluate the performance of the models and solution approach.

An Explanatory Study of Lean Practices in Job Shop Production/ Special Job Production/ Discrete Production/ Batch Shop Production Industries

OpenAIRE

Lavlesh Kumar Sharma; Ravindra Mohan Saxena

2014-01-01

In this paper, the study explores the benefits and advantages of Lean Practices or Lean Thinking in Job shop production/ Special job production/ Discrete production/ Batch shop production industries. The Lean Practices have been applied more compatible in Job shop production than in the continuous/ mass production because of several barriers and hurdles in the industrial context that influence the whole processes again and again, this happens due to the lack of knowledge about...

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

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.

Flow shop scheduling decisions through Techniques for Order Preference by Similarity to an Ideal Solution (TOPSIS

Directory of Open Access Journals (Sweden)

Arun Gupta

2016-07-01

Full Text Available The flow-shop scheduling problem (FSP has been widely studied in the literature and having a very active research area. Over the last few decades, a number of heuristic/meta-heuristic solution techniques have been developed. Some of these techniques offer excellent effectiveness and efficiency at the expense of substantial implementation efforts and being extremely complicated. This paper brings out the application of a Multi-Criteria Decision Making (MCDM method known as techniques for order preference by similarity to an ideal solution (TOPSIS using different weighting schemes in flow-shop environment. The objective function is identification of a job sequence which in turn would have minimum makespan (total job completion time. The application of the proposed method to flow shop scheduling is presented and explained with a numerical example. The results of the proposed TOPSIS based technique of FSP are also compared on the basis of some benchmark problems and found compatible with the results obtained from other standard procedures.

Multi-objective flexible job-shop scheduling problem using modified discrete particle swarm optimization.

Science.gov (United States)

Huang, Song; Tian, Na; Wang, Yan; Ji, Zhicheng

2016-01-01

Taking resource allocation into account, flexible job shop problem (FJSP) is a class of complex scheduling problem in manufacturing system. In order to utilize the machine resources rationally, multi-objective particle swarm optimization (MOPSO) integrating with variable neighborhood search is introduced to address FJSP efficiently. Firstly, the assignment rules (AL) and dispatching rules (DR) are provided to initialize the population. And then special discrete operators are designed to produce new individuals and earliest completion machine (ECM) is adopted in the disturbance operator to escape the optima. Secondly, personal-best archives (cognitive memories) and global-best archive (social memory), which are updated by the predefined non-dominated archive update strategy, are simultaneously designed to preserve non-dominated individuals and select personal-best positions and the global-best position. Finally, three neighborhoods are provided to search the neighborhoods of global-best archive for enhancing local search ability. The proposed algorithm is evaluated by using Kacem instances and Brdata instances, and a comparison with other approaches shows the effectiveness of the proposed algorithm for FJSP.

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.

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.

Workload control in job shops, grasping the tap

NARCIS (Netherlands)

Land, Martin Jaap

2004-01-01

The term job shops is used to indicate companies that produce customer-specific components in small batches. Jobs (production orders) in a job shop are characterised by a large variety of routings and operation processing times. This variety, combined with irregular order arrivals, generally leads

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.

Machine Shop Suggested Job and Task Sheets. Part II. 21 Advanced Jobs.

Science.gov (United States)

Texas A and M Univ., College Station. Vocational Instructional Services.

This volume consists of advanced job and task sheets adaptable for use in the regular vocational industrial education programs for the training of machinists and machine shop operators. Twenty-one advanced machine shop job sheets are included. Some or all of this material is provided for each job: an introductory sheet with aim, checking…

Machine Shop Suggested Job and Task Sheets. Part I. 25 Elementary Jobs.

Science.gov (United States)

Texas A and M Univ., College Station. Vocational Instructional Services.

This volume consists of elementary job and task sheets adaptable for use in the regular vocational industrial education programs for the training of machinists and machine shop operators. Twenty-five simple machine shop job sheets are included. Some or all of this material is provided for each job sheet: an introductory sheet with aim, checking…

A Local and Global Search Combine Particle Swarm Optimization Algorithm for Job-Shop Scheduling to Minimize Makespan

Directory of Open Access Journals (Sweden)

Zhigang Lian

2010-01-01

Full Text Available The Job-shop scheduling problem (JSSP is a branch of production scheduling, which is among the hardest combinatorial optimization problems. Many different approaches have been applied to optimize JSSP, but for some JSSP even with moderate size cannot be solved to guarantee optimality. The original particle swarm optimization algorithm (OPSOA, generally, is used to solve continuous problems, and rarely to optimize discrete problems such as JSSP. In OPSOA, through research I find that it has a tendency to get stuck in a near optimal solution especially for middle and large size problems. The local and global search combine particle swarm optimization algorithm (LGSCPSOA is used to solve JSSP, where particle-updating mechanism benefits from the searching experience of one particle itself, the best of all particles in the swarm, and the best of particles in neighborhood population. The new coding method is used in LGSCPSOA to optimize JSSP, and it gets all sequences are feasible solutions. Three representative instances are made computational experiment, and simulation shows that the LGSCPSOA is efficacious for JSSP to minimize makespan.

A Novel Memetic Algorithm Based on Decomposition for Multiobjective Flexible Job Shop Scheduling Problem

Directory of Open Access Journals (Sweden)

Chun Wang

2017-01-01

Full Text Available A novel multiobjective memetic algorithm based on decomposition (MOMAD is proposed to solve multiobjective flexible job shop scheduling problem (MOFJSP, which simultaneously minimizes makespan, total workload, and critical workload. Firstly, a population is initialized by employing an integration of different machine assignment and operation sequencing strategies. Secondly, multiobjective memetic algorithm based on decomposition is presented by introducing a local search to MOEA/D. The Tchebycheff approach of MOEA/D converts the three-objective optimization problem to several single-objective optimization subproblems, and the weight vectors are grouped by K-means clustering. Some good individuals corresponding to different weight vectors are selected by the tournament mechanism of a local search. In the experiments, the influence of three different aggregation functions is first studied. Moreover, the effect of the proposed local search is investigated. Finally, MOMAD is compared with eight state-of-the-art algorithms on a series of well-known benchmark instances and the experimental results show that the proposed algorithm outperforms or at least has comparative performance to the other algorithms.

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.

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

A fine-grained parallel algorithm for the cyclic flexible job shop problem

Directory of Open Access Journals (Sweden)

Bożejko Wojciech

2017-06-01

Full Text Available In this paper there is considered a flexible job shop problem of operations scheduling. The new, very fast method of determination of cycle time is presented. In the design of heuristic algorithm there was the neighborhood inspired by the game of golf applied. Lower bound of the criterion function was used in the search of the neighborhood.

The finite horizon economic lot sizing problem in job shops : the multiple cycle approach

NARCIS (Netherlands)

Ouenniche, J.; Bertrand, J.W.M.

2001-01-01

This paper addresses the multi-product, finite horizon, static demand, sequencing, lot sizing and scheduling problem in a job shop environment where the planning horizon length is finite and fixed by management. The objective pursued is to minimize the sum of setup costs, and work-in-process and

REDUCING LEAD TIME USING FUZZY LOGIC AT JOB SHOP

Directory of Open Access Journals (Sweden)

EMİN GÜNDOĞAR

2000-06-01

Full Text Available One problem encountering at the job shop scheduling is minimum production size of machine is different from each another. This case increases lead time. A new approach was improved to reduce lead time. In this new approach, the parts, which materials are in stock and orders coming very frequently are assigned to machine to reduce lead time. Due the fact that there are a lot of machine and orders, it is possible to become so1ne probletns. In this paper, fuzzy logic is used to cope with this problem. New approach was simulated at the job sop that has owner 15 machinery and 50 orders. Simulation results showed that new approach reduced lead time between 27.89% and 32.36o/o

A New Method Based on Simulation-Optimization Approach to Find Optimal Solution in Dynamic Job-shop Scheduling Problem with Breakdown and Rework

Directory of Open Access Journals (Sweden)

Farzad Amirkhani

2017-03-01

The proposed method is implemented on classical job-shop problems with objective of makespan and results are compared with mixed integer programming model. Moreover, the appropriate dispatching priorities are achieved for dynamic job-shop problem minimizing a multi-objective criteria. The results show that simulation-based optimization are highly capable to capture the main characteristics of the shop and produce optimal/near-optimal solutions with highly credibility degree.

A Markov chain analysis of the effectiveness of drum-buffer-rope material flow management in job shop environment

Directory of Open Access Journals (Sweden)

Masoud Rabbani

2015-09-01

Full Text Available The theory of constraints is an approach for production planning and control, which emphasizes on the constraints in the system to increase throughput. The theory of constraints is often referred to as Drum-Buffer-Rope developed originally by Goldratt. Drum-Buffer-Rope uses the drum or constraint to create a schedule based on the finite capacity of the first bottleneck. Because of complexity of the job shop environment, Drum-Buffer-Rope material flow management has very little attention to job shop environment. The objective of this paper is to apply the Drum-Buffer-Rope technique in the job shop environment using a Markov chain analysis to compare traditional method with Drum-Buffer-Rope. Four measurement parameters were considered and the result showed the advantage of Drum-Buffer-Rope approach compared with traditional one.

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.

Penerapan Algoritma Genetika Untuk Masalah Penjadwalan Job Shop Pada Lingkungan Industri Pakaian

OpenAIRE

Sitanggang, Hendrik

2011-01-01

Pada industri pakaian khususnya yang proses produksinya berbaur dan multi produk sering mengalami kesulitan pada penjadwalan job shop. Oleh karena itu, perlu diadakan penelitian untuk penjadwalan job shop yang efektif terutama yang proses produksinya berbaur dan multi produk. Pada tulisan ini akan diajukan metode untuk penjadwalan job shop yang berbaur dan multi produk dengan tujuan meminimalkan total pinalti E/T (Earliness/Tardiness) dengan menentukan start pada masing-masing job shop dan ba...

Revisiting Symbiotic Job Scheduling

OpenAIRE

Eyerman , Stijn; Michaud , Pierre; Rogiest , Wouter

2015-01-01

International audience; —Symbiotic job scheduling exploits the fact that in a system with shared resources, the performance of jobs is impacted by the behavior of other co-running jobs. By coscheduling combinations of jobs that have low interference, the performance of a system can be increased. In this paper, we investigate the impact of using symbiotic job scheduling for increasing throughput. We find that even for a theoretically optimal scheduler, this impact is very low, despite the subs...

Traitement d'un problème de type FJSP (Flexible Job Shop ...

African Journals Online (AJOL)

Dans cet article, nous avons étudié le problème d'optimisation d'une cellule de production flexible de type FJSP (flexible job-shop scheduling problem), dont le contrôle est très complexe. Parmi les multiples techniques et méthodes utilisées pour l‟étude de ce type de problème, il y a celles qui relèvent de la recherche ...

FLOWSHOP SCHEDULING USING A NETWORK APPROACH ...

African Journals Online (AJOL)

eobe

time when the last job completes on the last machine. The objective ... more jobs in a permutation flow shop scheduling problem ... processing time of a job on a machine is zero, it ..... hybrid flow shops with sequence dependent setup times ...

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.

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

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.

Nonstrict vector simulation in multi-operation scheduling

NARCIS (Netherlands)

Sevastianov, S.V.

1995-01-01

We consider several multi??operation scheduling problems with m machines and n jobs??, including fl??ow shop??, open shop,?? assembly line,?? and a few special cases of job shop with the makespan criterion. It is demonstrated that the problems in question can be effi??ciently solved by approximation

Simulation as a planning tool for job-shop production environment

Science.gov (United States)

Maram, Venkataramana; Nawawi, Mohd Kamal Bin Mohd; Rahman, Syariza Abdul; Sultan, Sultan Juma

2015-12-01

In this paper, we made an attempt to use discrete event simulation software ARENA® as a planning tool for job shop production environment. We considered job shop produces three types of Jigs with different sequence of operations to study and improve shop floor performance. The sole purpose of the study is to identifying options to improve machines utilization, reducing job waiting times at bottleneck machines. First, the performance of the existing system was evaluated by using ARENA®. Then identified improvement opportunities by analyzing base system results. Second, updated the model with most economical options. The proposed new system outperforms with that of the current base system by 816% improvement in delay times at paint shop by increase 2 to 3 and Jig cycle time reduces by Jig1 92%, Jig2 65% and Jig3 41% and hence new proposal was recommended.

JOB SHOP METHODOLOGY BASED ON AN ANT COLONY

Directory of Open Access Journals (Sweden)

OMAR CASTRILLON

2009-01-01

Full Text Available The purpose of this study is to reduce the total process time (Makespan and to increase the machines working time, in a job shop environment, using a heuristic based on ant colony optimization. This work is developed in two phases: The first stage describes the identification and definition of heuristics for the sequential processes in the job shop. The second stage shows the effectiveness of the system in the traditional programming of production. A good solution, with 99% efficiency is found using this technique.

Solving multi-objective job shop problem using nature-based algorithms: new Pareto approximation features

Directory of Open Access Journals (Sweden)

Jarosław Rudy

2015-01-01

Full Text Available In this paper the job shop scheduling problem (JSP with minimizing two criteria simultaneously is considered. JSP is frequently used model in real world applications of combinatorial optimization. Multi-objective job shop problems (MOJSP were rarely studied. We implement and compare two multi-agent nature-based methods, namely ant colony optimization (ACO and genetic algorithm (GA for MOJSP. Both of those methods employ certain technique, taken from the multi-criteria decision analysis in order to establish ranking of solutions. ACO and GA differ in a method of keeping information about previously found solutions and their quality, which affects the course of the search. In result, new features of Pareto approximations provided by said algorithms are observed: aside from the slight superiority of the ACO method the Pareto frontier approximations provided by both methods are disjoint sets. Thus, both methods can be used to search mutually exclusive areas of the Pareto frontier.

Revisiting the NEH algorithm- the power of job insertion technique for optimizing the makespan in permutation flow shop scheduling

Directory of Open Access Journals (Sweden)

A. Baskar

2016-04-01

Full Text Available Permutation flow shop scheduling problems have been an interesting area of research for over six decades. Out of the several parameters, minimization of makespan has been studied much over the years. The problems are widely regarded as NP-Complete if the number of machines is more than three. As the computation time grows exponentially with respect to the problem size, heuristics and meta-heuristics have been proposed by many authors that give reasonably accurate and acceptable results. The NEH algorithm proposed in 1983 is still considered as one of the best simple, constructive heuristics for the minimization of makespan. This paper analyses the powerful job insertion technique used by NEH algorithm and proposes seven new variants, the complexity level remains same. 120 numbers of problem instances proposed by Taillard have been used for the purpose of validating the algorithms. Out of the seven, three produce better results than the original NEH algorithm.

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

The performance of workload control concepts in job shops : Improving the release method

NARCIS (Netherlands)

Land, MJ; Gaalman, GJC

1998-01-01

A specific class of production control concepts for jobs shops is based on the principles of workload control. Practitioners emphasise the importance of workload control. However, order release methods that reduce the workload on the shop floor show poor due date performance in job shop simulations.

Apprenticeship Learning: Learning to Schedule from Human Experts

Science.gov (United States)

2016-06-09

identified by the heuristic . A spectrum of problems (i.e. traveling salesman, job-shop scheduling, multi-vehicle routing) was represented , as task locations...caus- ing the codification of this knowledge to become labori- ous. We propose a new approach for capturing domain- expert heuristics through a...demonstrate that this approach accu- rately learns multi-faceted heuristics on both a synthetic data set incorporating job-shop scheduling and vehicle

Integrating make-to-order and make-to-stock in job shop control

NARCIS (Netherlands)

Beemsterboer, Bart; Land, Martin; Teunter, Ruud; Bokhorst, Jos

2017-01-01

Demand fluctuations in make-to-order job shops lead to utilisation fluctuations and delivery delays, particularly in periods with high demand. Many job shop production companies therefore include some standardised products in their product mix and use a hybrid make-to-order/ make-to-stock production

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

A hybrid quantum-inspired genetic algorithm for multiobjective flow shop scheduling.

Science.gov (United States)

Li, Bin-Bin; Wang, Ling

2007-06-01

This paper proposes a hybrid quantum-inspired genetic algorithm (HQGA) for the multiobjective flow shop scheduling problem (FSSP), which is a typical NP-hard combinatorial optimization problem with strong engineering backgrounds. On the one hand, a quantum-inspired GA (QGA) based on Q-bit representation is applied for exploration in the discrete 0-1 hyperspace by using the updating operator of quantum gate and genetic operators of Q-bit. Moreover, random-key representation is used to convert the Q-bit representation to job permutation for evaluating the objective values of the schedule solution. On the other hand, permutation-based GA (PGA) is applied for both performing exploration in permutation-based scheduling space and stressing exploitation for good schedule solutions. To evaluate solutions in multiobjective sense, a randomly weighted linear-sum function is used in QGA, and a nondominated sorting technique including classification of Pareto fronts and fitness assignment is applied in PGA with regard to both proximity and diversity of solutions. To maintain the diversity of the population, two trimming techniques for population are proposed. The proposed HQGA is tested based on some multiobjective FSSPs. Simulation results and comparisons based on several performance metrics demonstrate the effectiveness of the proposed HQGA.

Solving no-wait two-stage flexible flow shop scheduling problem with unrelated parallel machines and rework time by the adjusted discrete Multi Objective Invasive Weed Optimization and fuzzy dominance approach

Energy Technology Data Exchange (ETDEWEB)

Jafarzadeh, Hassan; Moradinasab, Nazanin; Gerami, Ali

2017-07-01

Adjusted discrete Multi-Objective Invasive Weed Optimization (DMOIWO) algorithm, which uses fuzzy dominant approach for ordering, has been proposed to solve No-wait two-stage flexible flow shop scheduling problem. Design/methodology/approach: No-wait two-stage flexible flow shop scheduling problem by considering sequence-dependent setup times and probable rework in both stations, different ready times for all jobs and rework times for both stations as well as unrelated parallel machines with regards to the simultaneous minimization of maximum job completion time and average latency functions have been investigated in a multi-objective manner. In this study, the parameter setting has been carried out using Taguchi Method based on the quality indicator for beater performance of the algorithm. Findings: The results of this algorithm have been compared with those of conventional, multi-objective algorithms to show the better performance of the proposed algorithm. The results clearly indicated the greater performance of the proposed algorithm. Originality/value: This study provides an efficient method for solving multi objective no-wait two-stage flexible flow shop scheduling problem by considering sequence-dependent setup times, probable rework in both stations, different ready times for all jobs, rework times for both stations and unrelated parallel machines which are the real constraints.

Solving no-wait two-stage flexible flow shop scheduling problem with unrelated parallel machines and rework time by the adjusted discrete Multi Objective Invasive Weed Optimization and fuzzy dominance approach

International Nuclear Information System (INIS)

Jafarzadeh, Hassan; Moradinasab, Nazanin; Gerami, Ali

2017-01-01

Adjusted discrete Multi-Objective Invasive Weed Optimization (DMOIWO) algorithm, which uses fuzzy dominant approach for ordering, has been proposed to solve No-wait two-stage flexible flow shop scheduling problem. Design/methodology/approach: No-wait two-stage flexible flow shop scheduling problem by considering sequence-dependent setup times and probable rework in both stations, different ready times for all jobs and rework times for both stations as well as unrelated parallel machines with regards to the simultaneous minimization of maximum job completion time and average latency functions have been investigated in a multi-objective manner. In this study, the parameter setting has been carried out using Taguchi Method based on the quality indicator for beater performance of the algorithm. Findings: The results of this algorithm have been compared with those of conventional, multi-objective algorithms to show the better performance of the proposed algorithm. The results clearly indicated the greater performance of the proposed algorithm. Originality/value: This study provides an efficient method for solving multi objective no-wait two-stage flexible flow shop scheduling problem by considering sequence-dependent setup times, probable rework in both stations, different ready times for all jobs, rework times for both stations and unrelated parallel machines which are the real constraints.

Minimizing tardiness for job shop scheduling under uncertainties

OpenAIRE

Yahouni , Zakaria; Mebarki , Nasser; Sari , Zaki

2016-01-01

International audience; —Many disturbances can occur during the execution of a manufacturing scheduling process. To cope with this drawback , flexible solutions are proposed based on the offline and the online phase of the schedule. Groups of permutable operations is one of the most studied flexible scheduling methods bringing flexibility as well as quality to a schedule. The online phase of this method is based on a human-machine system allowing to choose in real-time one schedule from a set...

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%.

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.

Minimizing makespan in a two-stage flow shop with parallel batch-processing machines and re-entrant jobs

Science.gov (United States)

Huang, J. D.; Liu, J. J.; Chen, Q. X.; Mao, N.

2017-06-01

Against a background of heat-treatment operations in mould manufacturing, a two-stage flow-shop scheduling problem is described for minimizing makespan with parallel batch-processing machines and re-entrant jobs. The weights and release dates of jobs are non-identical, but job processing times are equal. A mixed-integer linear programming model is developed and tested with small-scale scenarios. Given that the problem is NP hard, three heuristic construction methods with polynomial complexity are proposed. The worst case of the new constructive heuristic is analysed in detail. A method for computing lower bounds is proposed to test heuristic performance. Heuristic efficiency is tested with sets of scenarios. Compared with the two improved heuristics, the performance of the new constructive heuristic is superior.

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.

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.

Job Flow Distribution and Ranked Jobs Scheduling in Grid Virtual Organizations

CERN Document Server

Toporkov, Victor; Tselishchev, Alexey; Yemelyanov, Dmitry; Potekhin, Petr

2015-01-01

In this work, we consider the problems of job flow distribution and ranked job framework forming within a model of cycle scheduling in Grid virtual organizations. The problem of job flow distribution is solved in terms of jobs and computing resource domains compatibility. A coefficient estimating such compatibility is introduced and studied experimentally. Two distribution strategies are suggested. Job framework forming is justified with such quality of service indicators as an average job execution time, a number of required scheduling cycles, and a number of job execution declines. Two methods for job selection and scheduling are proposed and compared: the first one is based on the knapsack problem solution, while the second one utilizes the mentioned compatibility coefficient. Along with these methods we present experimental results demonstrating the efficiency of proposed approaches and compare them with random job selection.

Algoritmo genético aplicado a la programación en talleres de maquinado//Genetic algorithm applied to scheduling in machine shops

Directory of Open Access Journals (Sweden)

José Eduardo Márquez-Delgado

2012-09-01

Full Text Available En este trabajo se utiliza la metaheurística nombrada algoritmo genético, para dos variantes típicas de problemas de planificación presentes en un taller de maquinado de piezas: las variantes flujo general y flujo regular, y se ha seleccionado la minimización del tiempo de finalización de todos los trabajos ocamino máximo, como objetivo a optimizar en un plan de trabajo. Este problema es considerado de difícil solución y es típico de la optimización combinatoria. Los resultados demuestran la calidad de las soluciones encontradas en correspondencia con el tiempo de cómputo empleado, al ser comparados conproblemas clásicos reportados por otros autores. La representación propuesta de cada cromosoma genera el universo completo de soluciones factibles, donde es posible encontrar valores óptimos globales de solución y cumple con las restricciones del problema.Palabras claves: algoritmo genético, cromosomas, flujo general, flujo regular, planificación, camino máximo._____________________________________________________________________________AbstractIn this paper we use the metaheuristic named genetic algorithm, for two typical variants of problems of scheduling present in a in a machine shop parts: the variant job shop and flow shop, and the minimization of the time of finalization of all the works has been selected, good known as makespan, as objective tooptimize in a work schedule. This problem is considered to be a difficult solution and is typical in combinatory optimization. The results demonstrate the quality of the solutions found in correspondence with the time of used computation, when being compared with classic problems reported by other authors.The proposed representation of each chromosome generates the complete universe of feasible solutions, where it is possible to find global good values of solution and it fulfills the restrictions of the problem.Key words: genetic algorithm, chromosomes, flow shop, job shop

Genetic Algorithm Combined with Gradient Information for Flexible Job-shop Scheduling Problem with Different Varieties and Small Batches

Directory of Open Access Journals (Sweden)

Chen Ming

2017-01-01

Full Text Available To solve the Flexible Job-shop Scheduling Problem (FJSP with different varieties and small batches, a modified meta-heuristic algorithm based on Genetic Algorithm (GA is proposed in which gene encoding is divided into process encoding and machine encoding, and according to the encoding mode, the machine gene fragment is connected with the process gene fragment and can be changed with the alteration of process genes. In order to get the global optimal solutions, the crossover and mutation operation of the process gene fragment and machine gene fragment are carried out respectively. In the initialization operation, the machines with shorter manufacturing time are more likely to be chosen to accelerate the convergence speed and then the tournament selection strategy is applied due to the minimum optimization objective. Meanwhile, a judgment condition of the crossover point quantity is introduced to speed up the population evolution and as an important interaction bridge between the current machine and alternative machines in the incidence matrix, a novel mutation operation of machine genes is proposed to achieve the replacement of manufacturing machines. The benchmark test shows the correctness of proposed algorithm and the case simulation proves the proposed algorithm has better performance compared with existing 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

Interactive Anticipatory Scheduling for Two Military Applications

National Research Council Canada - National Science Library

Howe, Adele

2003-01-01

...; these models partially explain what makes some job shop scheduling problems difficult. For the second, several algorithms for Air Force Satellite Control Network scheduling have been compared on historical and recent data...

Flow shop scheduling algorithm to optimize warehouse activities

Directory of Open Access Journals (Sweden)

P. Centobelli

2016-01-01

Full Text Available Successful flow-shop scheduling outlines a more rapid and efficient process of order fulfilment in warehouse activities. Indeed the way and the speed of order processing and, in particular, the operations concerning materials handling between the upper stocking area and a lower forward picking one must be optimized. The two activities, drops and pickings, have considerable impact on important performance parameters for Supply Chain wholesaler companies. In this paper, a new flow shop scheduling algorithm is formulated in order to process a greater number of orders by replacing the FIFO logic for the drops activities of a wholesaler company on a daily basis. The System Dynamics modelling and simulation have been used to simulate the actual scenario and the output solutions. Finally, a t-Student test validates the modelled algorithm, granting that it can be used for all wholesalers based on drop and picking activities.

A synergetic combination of small and large neighborhood schemes in developing an effective procedure for solving the job shop scheduling problem.

Science.gov (United States)

Amirghasemi, Mehrdad; Zamani, Reza

2014-01-01

This paper presents an effective procedure for solving the job shop problem. Synergistically combining small and large neighborhood schemes, the procedure consists of four components, namely (i) a construction method for generating semi-active schedules by a forward-backward mechanism, (ii) a local search for manipulating a small neighborhood structure guided by a tabu list, (iii) a feedback-based mechanism for perturbing the solutions generated, and (iv) a very large-neighborhood local search guided by a forward-backward shifting bottleneck method. The combination of shifting bottleneck mechanism and tabu list is used as a means of the manipulation of neighborhood structures, and the perturbation mechanism employed diversifies the search. A feedback mechanism, called repeat-check, detects consequent repeats and ignites a perturbation when the total number of consecutive repeats for two identical makespan values reaches a given threshold. The results of extensive computational experiments on the benchmark instances indicate that the combination of these four components is synergetic, in the sense that they collectively make the procedure fast and robust.

Busca tabu para a programação de tarefas em job shop com datas de entrega

OpenAIRE

Cintia Rigão Scrich

1997-01-01

Resumo: Este trabalho trata do problema de programação de tarefas nos ambientes job shop tradicional e job shop flexível com o objetivo de minimizar o atraso total das tarefas. A principal diferença do job shop flexível em relação ao job shop tradicional é que cada operação possui um conjunto de máquinas alternativas onde pode ser processada. Para cada um dos problemas é desenvolvida uma heurística guiada pela metaheurística Busca Tabu. Estratégias de diversificação e intensificação para a bu...

Hybrid Discrete Differential Evolution Algorithm for Lot Splitting with Capacity Constraints in Flexible Job Scheduling

Directory of Open Access Journals (Sweden)

Xinli Xu

2013-01-01

Full Text Available A two-level batch chromosome coding scheme is proposed to solve the lot splitting problem with equipment capacity constraints in flexible job shop scheduling, which includes a lot splitting chromosome and a lot scheduling chromosome. To balance global search and local exploration of the differential evolution algorithm, a hybrid discrete differential evolution algorithm (HDDE is presented, in which the local strategy with dynamic random searching based on the critical path and a random mutation operator is developed. The performance of HDDE was experimented with 14 benchmark problems and the practical dye vat scheduling problem. The simulation results showed that the proposed algorithm has the strong global search capability and can effectively solve the practical lot splitting problems with equipment capacity constraints.

Project orie:nta.teci pla.:n:ni:ng, scheduling a.:nci controlling technique

African Journals Online (AJOL)

Review Technique. By October 1958 it ... (CPM) to schedule and control a very large project. and during the ... objectives are identified and the total job is broken down into ..... jobs in a single shop or shops in the plant, to scheduf- ing plants ...

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.

Applicability aspects of workload control in job shop production

NARCIS (Netherlands)

Henrich, P.

2005-01-01

The term Job Shop Production (JSP) describes a manufacturing environment that produces piece goods in small batches. It is a common manufacturing environment in small and medium-sized enterprises (SMEs). The incoming orders often differ in the number of ordered products, their design, process

It's a Mall, Mall, Mall, Mall World: Jobs in Shopping Malls.

Science.gov (United States)

Green, Kathleen

1996-01-01

Provides information about a variety of nonsales jobs available in shopping malls: mall management, customer service, marketing, operations, security, maintenance, and administration. Includes information about educational requirements. (JOW)

Performance Implications of Buffer Overflow as a Key (Disturbing) Element in the Flow Control of a Job/Flow Shop Facility

DEFF Research Database (Denmark)

Nielsen, Erland Hejn

2002-01-01

From time to time most real life job/flow shops will experience more or less severe buffer problems in relation to the operation at its various stations in the shop. Due to temporary non-predictable variations in the job flow intensity the assigned buffer space in front of a given critical station...... to temporary buffer overflow situations. This paper will investigate the impact of buffer overflow on several key performance measures of relevance to the overall operation of a job/flow shop facility. Several simple job/flow shop structures will be considered in this paper including re-entrant system set......-ups (a re-entrant system is a system where some of the job-routes revisit a given station more than once)....

Performance Implications of Buffer overflow as a key (Disturbing) Element in the Flow Control of a Job/Flow Shop Facility

DEFF Research Database (Denmark)

Nielsen, Erland Hejn

2002-01-01

From time to time most real life job/flow shops will experience more or less severe buffer problems in relation to the operation at its various stations in the shop. Due to temporary non-predictable variations in the job flow intensity the assigned buffer space in front of a given critical station...... to temporary buffer overflow situations. This paper will investigate the impact of buffer overflow on several key performance measures of relevance to the overall operation of a job/flow shop facility. Several simple job/flow shop structures will be considered in this paper including re-entrant system set......-ups (a re-entrant system is a system where some of the job-routes revisit a given station more than once)....

A bi-criteria M-machine SDST flow shop scheduling using modified ...

African Journals Online (AJOL)

user

In the present work, a modified heuristic based genetic algorithm ..... Due to the large search space in flow shop scheduling, it is expected that random generation ..... ergonomics, anthropometry, inventory management and quality control etc.

Due date assignment procedures with dynamically updated coefficients for multi-level assembly job shops

NARCIS (Netherlands)

Adam, N.R.; Bertrand, J.W.M.; Morehead, D.C.; Surkis, J.

1993-01-01

This paper presents a study of due date assignment procedures in job shop environments where multi-level assembly jobs are processed and due dates are internally assigned. Most of the reported studies in the literature have focused on string type jobs. We propose a dynamic update approach (which

Single-machine scheduling of proportionally deteriorating jobs by two agents

OpenAIRE

S Gawiejnowicz; W-C Lee; C-L Lin; C-C Wu

2011-01-01

We consider a problem of scheduling a set of independent jobs by two agents on a single machine. Every agent has its own subset of jobs to be scheduled and uses its own optimality criterion. The processing time of each job proportionally deteriorates with respect to the starting time of the job. The problem is to find a schedule that minimizes the total tardiness of the first agent, provided that no tardy job is allowed for the second agent. We prove basic properties of the problem and give a...

UN ALGORITMO GENÉTICO HÍBRIDO Y UN ENFRIAMIENTO SIMULADO PARA SOLUCIONAR EL PROBLEMA DE PROGRAMACIÓN DE PEDIDOS JOB SHOP UM ALGORITMO GENÉTICO HÍBRIDO E UM ESFRIAMENTO SIMULADO PARA SOLUCIONAR O PROBLEMA DE PROGRAMAÇÃO DE PEDIDOS JOB SHOP A HYBRID GENETIC ALGORITHM AND A SIMULATED ANNEALING FOR SOLVING THE JOB SHOP SCHEDULING PROBLEM

Directory of Open Access Journals (Sweden)

José David Meisel

2010-07-01

mostraram que os algoritmos propostos arrojam bons resultados, com desvios ao redor dos melhores valores achados que não superam 5 % para os problemas mais complexos.Job Shop Scheduling Problem (JSP, classified as NP-Hard, has been a challenge for the scientific community because achieving an optimal solution to this problem is complicated as it grows in number of machines and jobs. Numerous techniques, including metaheuristics, have been used for its solution; however, the efficiency of the techniques, in terms of computational time, has not been very satisfactory. Because of this and for contributing to the solution of this problem, a simulated annealing (SA and an improved genetic algorithm (IGA have been proposed. The latter, by implementing a strategy of simulated annealing in the mutation phase, allows the algorithm to enhance and diversify the solutions at the same time, in order not to converge prematurely to a local optimum. The results showed that the proposed algorithms yield good results with deviations around the best values found not exceeding 5 % for more complex problems.

PERBANDINGAN KINERJA ALGORITMA GENETIKA DAN ALGORITMA HEURISTIK RAJENDRAN UNTUK PENJADUALAN PRODUKSI JENIS FLOW SHOP

Directory of Open Access Journals (Sweden)

Tessa Vanina Soetanto

1999-01-01

Full Text Available Flow shop scheduling problem is to schedule a production process of n jobs that go through the same process sequence and the same m machines. Most researches are don to accomplish only one objective, i.e. minimizing makespan. The other objective, such as total flow time, or multiple objectives that is minimizing makespan, total flow time and machine idle time, will be more effective in reducing scheduling cost, as written in French (1982. Rajendran algorithm (1995 that solves flow shop problem with multiple objectives will be used to evaluate the proposed algorithm: Genetic Algorithm, developed by Sridhar & Rajendran (1996 on a problem that existed in a shoe factory. Abstract in Bahasa Indonesia : Masalah penjadualan flow shop adalah menjadualkan proses produksi dari masing-masing n job yang mempunyai urutan proses produksi dan melalui m mesin yang sama. Kebanyakan penelitian hanya mengacu pada satu tujuan saja yaitu meminimumkan makespan. Tujuan yang lain, seperti meminimumkan total flow time atau multiple objectives yang meminimumkan makespan, total flow time dan machine idle time akan lebih efektif dalam mengurangi biaya penjadualan, sebagaimana dikatakan oleh French (1982. Algoritma Rajendran (1995 yang menyelesaikan masalah flow shop dengan multiple objectives akan dipergunakan untuk mengevaluasi algoritma usulan: Algoritma Genetika, yang dikembangkan oleh Sridhar & Rajendran (1996 pada suatu masalah yang ditemui di suatu perusahaan sepatu. Kata kunci: flow shop, algoritma genetika, multiple objectives

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.

Integrating job scheduling and constrained network routing

DEFF Research Database (Denmark)

Gamst, Mette

2010-01-01

This paper examines the NP-hard problem of scheduling jobs on resources such that the overall profit of executed jobs is maximized. Job demand must be sent through a constrained network to the resource before execution can begin. The problem has application in grid computing, where a number...

Avaliação de regras de sequenciamento da produção em ambientes Job shop e Flow shop por meio de simulação computacional

Directory of Open Access Journals (Sweden)

Edna Barbosa da Silva

2012-01-01

Full Text Available In this work, the computational simulation is employed to study the effects of production sequencing rules in the performance of Job shop and Flow shop manufacturing environments. Eight sequencing rules were considered: SIPT (Shortest Imminent Processing Time, EDD (Earliest Due Date, DLS (Dynamic Least Slack, LWQ (Least Work in next Queue, FIFO (First In First Out, LIFO (Last In Last Out, CR (Critical Ratio and LS (Least Slack. These different sequencing rules were evaluated in relation to the makespan, total tardiness and number of tardy jobs, considering an experimental scenario which includes two configurations with eight machines (processes and ten different types of orders. A simulation model was developed with Arena software, incorporating randomness of order arrivals and the production times in such environments. The results show that the EDD and SIPT rules presented the best performances in the Job shop and in the Flow shop environments, respectively.

Worker flexibility in a parallel dual resource constrained job shop

NARCIS (Netherlands)

Yue, H.; Slomp, J.; Molleman, E.; van der Zee, D.J.

2008-01-01

In this paper we investigate cross-training policies in a dual resource constraint (DRC) parallel job shop where new part types are frequently introduced into the system. Each new part type introduction induces the need for workers to go through a learning curve. A cross-training policy relates to

Método para definição de layout em sistemas job-shop baseado em dados históricos Historical data-based job-shop layout systems definition method

Directory of Open Access Journals (Sweden)

Maurício Tomelin

2010-01-01

Full Text Available O presente trabalho propõe um método para a solução do problema de definição de layout tipo job-shop baseado em dados históricos de produção, recursos disponíveis e características de produção. Os parâmetros utilizados foram a quantidade total e a frequência de vendas, a lucratividade, o tempo total de processamento e o tempo de espera de cada produto, gerando assim a classificação dos produtos. Os roteiros de produção foram comparados e, em função dos parâmetros, foi determinado o grau de importância de cada ligação entre os recursos. As ligações foram submetidas a um modelo matemático para a determinação da posição de cada recurso no layout. O método desenvolvido foi aplicado a uma empresa de usinagem com característica de job-shop. Os dados submetidos ao método permitiram uma sugestão de layout que tem como objetivo minimizar a distância dos recursos de processamento.This paper proposes a method for solving the job-shop layout problem definition, based on historical production data, available resources and production characteristics. The products were classified according to total sales, sales frequency, profitability, total processing time and stand-by time. The production path was compared and the degree of importance of each link between resources was determined. Path comparisons were made to quantify the same routes and the route differences, generating similar routes. The links were submitted to a mathematical model to determine the position of resources in the layout. The method developed was applied to a machining company with a job-shop profile. When the company's data was subjected to the method, it enabled the development of a layout, the main goal of which was to minimize distances between product-processing resources.

Neural nets for job-shop scheduling, will they do the job?

NARCIS (Netherlands)

Rooda, J.E.; Willems, T.M.; Goodwin, G.C.; Evans, R.J.

1993-01-01

A neural net structure has been developed which is capable of solving deterministic jobshop scheduling problems, part of the large class of np-complete problems. The problem was translated in an integer linear-programming format which facilitated translation in an adequate neural net structure. Use

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.

Prevalence of job strain among Indian foundry shop floor workers.

Science.gov (United States)

Mohan, G Madhan; Elangovan, S; Prasad, P S S; Krishna, P Rama; Mokkapati, Anil Kumar

2008-01-01

Global competition in manufacturing sector demand higher productivity levels. In this context, workers in this sector are set with high output targets, leading to job strain. In addition to the strain, hazardous conditions also prevail in some of the manufacturing processes like foundry activities. This paper attempts to appraise the prevalence of job strain among foundry shop floor workers in India with the help of Demands-Control model [8]. In this study, data was collected through a survey using 49-item Job Content Questionnaire (JCQ) [9], a widely used and well-validated test for job strain. Then the data was subjected to statistical analysis after ascertaining the reliability. This survey has revealed that 25% of workers in foundry were experiencing high job strain. Hazardous working conditions, limited decision making authority, etc. appear to be the main contributing factors for the higher levels of strain.

An extended continuous estimation of distribution algorithm for solving the permutation flow-shop scheduling problem

Science.gov (United States)

Shao, Zhongshi; Pi, Dechang; Shao, Weishi

2017-11-01

This article proposes an extended continuous estimation of distribution algorithm (ECEDA) to solve the permutation flow-shop scheduling problem (PFSP). In ECEDA, to make a continuous estimation of distribution algorithm (EDA) suitable for the PFSP, the largest order value rule is applied to convert continuous vectors to discrete job permutations. A probabilistic model based on a mixed Gaussian and Cauchy distribution is built to maintain the exploration ability of the EDA. Two effective local search methods, i.e. revolver-based variable neighbourhood search and Hénon chaotic-based local search, are designed and incorporated into the EDA to enhance the local exploitation. The parameters of the proposed ECEDA are calibrated by means of a design of experiments approach. Simulation results and comparisons based on some benchmark instances show the efficiency of the proposed algorithm for solving the PFSP.

Shopping for Jobs: Mall Internship Program Opens Doors for HVAC Students.

Science.gov (United States)

Nolot, Terry

1995-01-01

Ivy Tech State College uses River Falls, a shopping mall, as an enormous heating, ventilation, and air conditioning laboratory. Students spend Saturdays working with full-time technicians getting invaluable training and experience. Students see the program as a professional opportunity and a direct route to jobs. (JOW)

ARTIFICIAL INTELLIGENCE EFFECTIVENESS IN JOB SHOP ENVIRONMENTS

OpenAIRE

OMAR CASTRILLON; WILLIAM SARACHE; JAIME GIRALDO

2011-01-01

El objetivo del presente trabajo, es definir una nueva metodología la cual permita comparar la efectividad de algunas de las principales técnicas de inteligencia artificial (aleatorias, búsqueda tabú, minería de datos, algoritmos evolutivos). Esta metodología es aplicada en los procesos de secuenciación de la producción en ambientes job shop, en un problema con N pedidos y M máquinas, donde cada uno de los pedidos debe pasar por todas las máquinas sin importar el orden. Estas técnicas son med...

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

Does self-scheduling increase nurses' job satisfaction? An integrative literature review.

Science.gov (United States)

Koning, Clare

2014-09-25

Flexible work schedules give nurses the freedom and control to manage the demands of work and home, allow organisations to meet their staffing needs and can improve job satisfaction. This article reports the results of an integrative review of published peer-reviewed research and personal narratives that examined nurses' perceptions of the relationship between job satisfaction and a self-scheduling system. Results suggest that self-scheduling is one of a number of factors that influence job satisfaction, but that implementing and sustaining such a system can be challenging. The review also found that self-scheduling programmes underpin more flexible work schedules and can benefit nurses and their organisations.

Moving from job-shop to production cells without losing flexibility: a case study from the wooden frames industry

Directory of Open Access Journals (Sweden)

Dinis-Carvalho, J.

2014-11-01

Full Text Available Cellular production is usually seen as a hybrid approach between job-shop and flow-line paradigms, reducing the major disadvantages of these two paradigms: the low productivity of job-shops and the low flexibility (in terms of products’ variety of the flow-lines. This paper describes the implementation of a production cell in a production unit of wood- framed pictures and mirrors, which was originally configured as a traditional job-shop, without losing the necessary flexibility to face market demand and simultaneously increasing the production unit’s performance. By implementing a highly flexible cell, very significant improvements were expected for the system’s overall performance and the quality of the products. These expectations were met, and the implementation was successful, as demonstrated by the results presented.

Job schedulers for Big data processing in Hadoop environment: testing real-life schedulers using benchmark programs

Directory of Open Access Journals (Sweden)

Mohd Usama

2017-11-01

Full Text Available At present, big data is very popular, because it has proved to be much successful in many fields such as social media, E-commerce transactions, etc. Big data describes the tools and technologies needed to capture, manage, store, distribute, and analyze petabyte or larger-sized datasets having different structures with high speed. Big data can be structured, unstructured, or semi structured. Hadoop is an open source framework that is used to process large amounts of data in an inexpensive and efficient way, and job scheduling is a key factor for achieving high performance in big data processing. This paper gives an overview of big data and highlights the problems and challenges in big data. It then highlights Hadoop Distributed File System (HDFS, Hadoop MapReduce, and various parameters that affect the performance of job scheduling algorithms in big data such as Job Tracker, Task Tracker, Name Node, Data Node, etc. The primary purpose of this paper is to present a comparative study of job scheduling algorithms along with their experimental results in Hadoop environment. In addition, this paper describes the advantages, disadvantages, features, and drawbacks of various Hadoop job schedulers such as FIFO, Fair, capacity, Deadline Constraints, Delay, LATE, Resource Aware, etc, and provides a comparative study among these schedulers.

Scheduling Parallel Jobs Using Migration and Consolidation in the Cloud

Directory of Open Access Journals (Sweden)

Xiaocheng Liu

2012-01-01

Full Text Available An increasing number of high performance computing parallel applications leverages the power of the cloud for parallel processing. How to schedule the parallel applications to improve the quality of service is the key to the successful host of parallel applications in the cloud. The large scale of the cloud makes the parallel job scheduling more complicated as even simple parallel job scheduling problem is NP-complete. In this paper, we propose a parallel job scheduling algorithm named MEASY. MEASY adopts migration and consolidation to enhance the most popular EASY scheduling algorithm. Our extensive experiments on well-known workloads show that our algorithm takes very good care of the quality of service. For two common parallel job scheduling objectives, our algorithm produces an up to 41.1% and an average of 23.1% improvement on the average response time; an up to 82.9% and an average of 69.3% improvement on the average slowdown. Our algorithm is robust even in terms that it allows inaccurate CPU usage estimation and high migration cost. Our approach involves trivial modification on EASY and requires no additional technique; it is practical and effective in the cloud environment.

An Enhanced Discrete Artificial Bee Colony Algorithm to Minimize the Total Flow Time in Permutation Flow Shop Scheduling with Limited Buffers

Directory of Open Access Journals (Sweden)

Guanlong Deng

2016-01-01

Full Text Available This paper presents an enhanced discrete artificial bee colony algorithm for minimizing the total flow time in the flow shop scheduling problem with buffer capacity. First, the solution in the algorithm is represented as discrete job permutation to directly convert to active schedule. Then, we present a simple and effective scheme called best insertion for the employed bee and onlooker bee and introduce a combined local search exploring both insertion and swap neighborhood. To validate the performance of the presented algorithm, a computational campaign is carried out on the Taillard benchmark instances, and computations and comparisons show that the proposed algorithm is not only capable of solving the benchmark set better than the existing discrete differential evolution algorithm and iterated greedy algorithm, but also capable of performing better than two recently proposed discrete artificial bee colony algorithms.

A genetic algorithm-based job scheduling model for big data analytics.

Science.gov (United States)

Lu, Qinghua; Li, Shanshan; Zhang, Weishan; Zhang, Lei

Big data analytics (BDA) applications are a new category of software applications that process large amounts of data using scalable parallel processing infrastructure to obtain hidden value. Hadoop is the most mature open-source big data analytics framework, which implements the MapReduce programming model to process big data with MapReduce jobs. Big data analytics jobs are often continuous and not mutually separated. The existing work mainly focuses on executing jobs in sequence, which are often inefficient and consume high energy. In this paper, we propose a genetic algorithm-based job scheduling model for big data analytics applications to improve the efficiency of big data analytics. To implement the job scheduling model, we leverage an estimation module to predict the performance of clusters when executing analytics jobs. We have evaluated the proposed job scheduling model in terms of feasibility and accuracy.

Job schedul in Grid batch farms

International Nuclear Information System (INIS)

Gellrich, Andreas

2014-01-01

We present here a study for a scheduler which cooperates with the queueing system TORQUE and is tailored to the needs of a HEP-dominated large Grid site with around 10000 jobs slots. Triggered by severe scaling problems of MAUI, a scheduler, referred to as MYSCHED, was developed and put into operation. We discuss conceptional aspects as well as experiences after almost two years of running.

Due Date Assignment in a Dynamic Job Shop with the Orthogonal Kernel Least Squares Algorithm

Science.gov (United States)

Yang, D. H.; Hu, L.; Qian, Y.

2017-06-01

Meeting due dates is a key goal in the manufacturing industries. This paper proposes a method for due date assignment (DDA) by using the Orthogonal Kernel Least Squares Algorithm (OKLSA). A simulation model is built to imitate the production process of a highly dynamic job shop. Several factors describing job characteristics and system state are extracted as attributes to predict job flow-times. A number of experiments under conditions of varying dispatching rules and 90% shop utilization level have been carried out to evaluate the effectiveness of OKLSA applied for DDA. The prediction performance of OKLSA is compared with those of five conventional DDA models and back-propagation neural network (BPNN). The experimental results indicate that OKLSA is statistically superior to other DDA models in terms of mean absolute lateness and root mean squares lateness in most cases. The only exception occurs when the shortest processing time rule is used for dispatching jobs, the difference between OKLSA and BPNN is not statistically significant.

Heuristic for production scheduling on job-shop plants considering preventive maintenance tasks

Directory of Open Access Journals (Sweden)

Ronald Díaz-Cazaña

2014-01-01

Full Text Available El análisis simultáneo de la programación de la producción y la s tareas de mantenimiento preventivo atrae especial atención en los investigadores debido a su gran complejidad y por ende la neces idad de encontrar métodos eficientes para resolver este tipo de problema combinatorio. Este artículo presenta un enfoque heurístico para resolver dicha problemática en plantas tipo job-shop . El método de solución incluye un modelo de programación lineal inspirado en el proble ma del Agente Vendedor, donde el tiempo de iniciación es consid erado como métrica de distancia. El método persigue obtener una secue ncia de las órdenes de producción y tareas de mantenimiento pre ventivo que reduzcan el tiempo ocioso y los retrasos simultáneamente, c umpliendo con el programa de mantenimiento. Luego de encontrar la solución óptima para cada máquina, un factor de corrección ( CF es determinado como la nueva medida de distancia. El factor CF considera la estructura inicial de solución, la utilización de las máquin as y las prioridades en los productos. De esta forma, la soluci ón final es alcanzada solucionando el modelo de programación lineal usando los valores de distancia actualizados. Finalmente, la heurístic a propuesta es aplicada en un caso de estudio real de la Industria Cubana. Los resultados experimentales indicaron una reducción significa tiva del tiempo ocioso para la compañía objeto de estudio.

Scheduling Non-Preemptible Jobs to Minimize Peak Demand

Directory of Open Access Journals (Sweden)

Sean Yaw

2017-10-01

Full Text Available This paper examines an important problem in smart grid energy scheduling; peaks in power demand are proportionally more expensive to generate and provision for. The issue is exacerbated in local microgrids that do not benefit from the aggregate smoothing experienced by large grids. Demand-side scheduling can reduce these peaks by taking advantage of the fact that there is often flexibility in job start times. We focus attention on the case where the jobs are non-preemptible, meaning once started, they run to completion. The associated optimization problem is called the peak demand minimization problem, and has been previously shown to be NP-hard. Our results include an optimal fixed-parameter tractable algorithm, a polynomial-time approximation algorithm, as well as an effective heuristic that can also be used in an online setting of the problem. Simulation results show that these methods can reduce peak demand by up to 50% versus on-demand scheduling for household power jobs.

Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard

NARCIS (Netherlands)

Hoogeveen, J.A.; Lenstra, J.K.; Veltman, B.

1996-01-01

In 1954, Johnson gave an efficient algorithm for minimizing makespan in a two-machine flow shop; there is no advantage to preemption in this case. McNaughton's wrap-around rule of 1959 finds a shortest preemptive schedule on identical parallel machines in linear time. A similarly efficient algorithm

Backfilling with Fairness and Slack for Parallel Job Scheduling

International Nuclear Information System (INIS)

Sodan, Angela C; Wei Jin

2010-01-01

Parallel job scheduling typically combines a basic policy like FCFS with backfilling, i.e. moving jobs to an earlier than their regular scheduling position if they do not delay the jobs ahead in the queue according to the rules of the backfilling approach applied. Commonly used are conservative and easy backfilling which either have worse response times but better predictability or better response times and poor predictability. The paper proposes a relaxation of conservative backfilling by permitting to shift jobs within certain constraints to backfill more jobs and reduce fragmentation and subsequently obtain better response times. At the same time, deviation from fairness is kept low and predictability remains high. The results of the experimentation evaluation show that the goals are met, with response-time performance lying as expected between conservative and easy backfilling.

Backfilling with Fairness and Slack for Parallel Job Scheduling

Energy Technology Data Exchange (ETDEWEB)

Sodan, Angela C; Wei Jin, E-mail: acsodan@uwindsor.ca [University of Windsor, Computer Science, Windsor, Ontario (Canada)

2010-11-01

Parallel job scheduling typically combines a basic policy like FCFS with backfilling, i.e. moving jobs to an earlier than their regular scheduling position if they do not delay the jobs ahead in the queue according to the rules of the backfilling approach applied. Commonly used are conservative and easy backfilling which either have worse response times but better predictability or better response times and poor predictability. The paper proposes a relaxation of conservative backfilling by permitting to shift jobs within certain constraints to backfill more jobs and reduce fragmentation and subsequently obtain better response times. At the same time, deviation from fairness is kept low and predictability remains high. The results of the experimentation evaluation show that the goals are met, with response-time performance lying as expected between conservative and easy backfilling.

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.

Designing an advanced available-to-promise mechanism compatible with the make-to-forecast production systems through integrating inventory allocation and job shop scheduling with due dates and weighted earliness/tardiness cost

Directory of Open Access Journals (Sweden)

Masoud Rabbani

2016-06-01

Full Text Available In the competitive business world, applying a reliable and powerful mechanism to support decision makers in manufacturing companies and helping them save time by considering varieties of effective factors is an inevitable issue. Advanced Available-to-Promise is a perfect tool to design and perform such a mechanism. In this study, this mechanism which is compatible with the Make-to-Forecast production systems is presented. The ability to distinguish between batch mode and real-time mode advanced available-to-promise is one of the unique superiorities of the proposed model. We also try to strengthen this mechanism by integrating the inventory allocation and job shop scheduling by considering due dates and weighted earliness/tardiness cost that leads to more precise decisions. A mixed integer programming (MIP model and a heuristic algorithm according to its disability to solve large size problems are presented. The designed experiments and the obtained results have proved the efficiency of the proposed heuristic method.

A multi-criteria model for maintenance job scheduling

Directory of Open Access Journals (Sweden)

Sunday A. Oke

2007-12-01

Full Text Available This paper presents a multi-criteria maintenance job scheduling model, which is formulated using a weighted multi-criteria integer linear programming maintenance scheduling framework. Three criteria, which have direct relationship with the primary objectives of a typical production setting, were used. These criteria are namely minimization of equipment idle time, manpower idle time and lateness of job with unit parity. The mathematical model constrained by available equipment, manpower and job available time within planning horizon was tested with a 10-job, 8-hour time horizon problem with declared equipment and manpower available as against the required. The results, analysis and illustrations justify multi-criteria consideration. Thus, maintenance managers are equipped with a tool for adequate decision making that guides against error in the accumulated data which may lead to wrong decision making. The idea presented is new since it provides an approach that has not been documented previously in the literature.

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.

Selection and scheduling of jobs with time-dependent duration

OpenAIRE

DM Seegmuller; SE Visagie; HC de Kock; WJ Pienaar

2007-01-01

In this paper two mathematical programming models, both with multiple objective functions, are proposed to solve four related categories of job scheduling problems. All four of these categories have the property that the duration of the jobs is dependent on the time of implementation and in some cases the preceding job. Furthermore, some jobs (restricted to subsets of the total pool of jobs) can, to different extents, run in parallel. In addition, not all the jobs need necessarily be implemen...

Batch Scheduling for Hybrid Assembly Differentiation Flow Shop to Minimize Total Actual Flow Time

Science.gov (United States)

Maulidya, R.; Suprayogi; Wangsaputra, R.; Halim, A. H.

2018-03-01

A hybrid assembly differentiation flow shop is a three-stage flow shop consisting of Machining, Assembly and Differentiation Stages and producing different types of products. In the machining stage, parts are processed in batches on different (unrelated) machines. In the assembly stage, each part of the different parts is assembled into an assembly product. Finally, the assembled products will further be processed into different types of final products in the differentiation stage. In this paper, we develop a batch scheduling model for a hybrid assembly differentiation flow shop to minimize the total actual flow time defined as the total times part spent in the shop floor from the arrival times until its due date. We also proposed a heuristic algorithm for solving the problems. The proposed algorithm is tested using a set of hypothetic data. The solution shows that the algorithm can solve the problems effectively.

Dynamic scheduling and analysis of real time systems with multiprocessors

Directory of Open Access Journals (Sweden)

M.D. Nashid Anjum

2016-08-01

Full Text Available This research work considers a scenario of cloud computing job-shop scheduling problems. We consider m realtime jobs with various lengths and n machines with different computational speeds and costs. Each job has a deadline to be met, and the profit of processing a packet of a job differs from other jobs. Moreover, considered deadlines are either hard or soft and a penalty is applied if a deadline is missed where the penalty is considered as an exponential function of time. The scheduling problem has been formulated as a mixed integer non-linear programming problem whose objective is to maximize net-profit. The formulated problem is computationally hard and not solvable in deterministic polynomial time. This research work proposes an algorithm named the Tube-tap algorithm as a solution to this scheduling optimization problem. Extensive simulation shows that the proposed algorithm outperforms existing solutions in terms of maximizing net-profit and preserving deadlines.

Integrating make-to-order and make-to-stock in job shop control (Reprint of International Journal of Production Economics 185, pp 1-10)

NARCIS (Netherlands)

Beemsterboer, Bart; Land, Martin; Teunter, Ruud; Bokhorst, Jos

2017-01-01

Demand fluctuations in make-to-order job shops lead to utilisation fluctuations and delivery delays, particularly in periods with high demand. Many job shop production companies therefore include some standardised products in their product mix and use a hybrid make-to-order/make-to-stock production

Learning Dispatching Rules for Scheduling: A Synergistic View Comprising Decision Trees, Tabu Search and Simulation

Directory of Open Access Journals (Sweden)

Atif Shahzad

2016-02-01

Full Text Available A promising approach for an effective shop scheduling that synergizes the benefits of the combinatorial optimization, supervised learning and discrete-event simulation is presented. Though dispatching rules are in widely used by shop scheduling practitioners, only ordinary performance rules are known; hence, dynamic generation of dispatching rules is desired to make them more effective in changing shop conditions. Meta-heuristics are able to perform quite well and carry more knowledge of the problem domain, however at the cost of prohibitive computational effort in real-time. The primary purpose of this research lies in an offline extraction of this domain knowledge using decision trees to generate simple if-then rules that subsequently act as dispatching rules for scheduling in an online manner. We used similarity index to identify parametric and structural similarity in problem instances in order to implicitly support the learning algorithm for effective rule generation and quality index for relative ranking of the dispatching decisions. Maximum lateness is used as the scheduling objective in a job shop scheduling environment.

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.

Optimising Job-Shop Functions Utilising the Score-Function Method

DEFF Research Database (Denmark)

Nielsen, Erland Hejn

2000-01-01

During the last 1-2 decades, simulation optimisation of discrete event dynamic systems (DEDS) has made considerable theoretical progress with respect to computational efficiency. The score-function (SF) method and the infinitesimal perturbation analysis (IPA) are two candidates belonging to this ......During the last 1-2 decades, simulation optimisation of discrete event dynamic systems (DEDS) has made considerable theoretical progress with respect to computational efficiency. The score-function (SF) method and the infinitesimal perturbation analysis (IPA) are two candidates belonging...... of a Job-Shop can be handled by the SF method....

A New Artificial Immune System Algorithm for Multiobjective Fuzzy Flow Shop Problems

Directory of Open Access Journals (Sweden)

Cengiz Kahraman

2009-12-01

Full Text Available In this paper a new artificial immune system (AIS algorithm is proposed to solve multi objective fuzzy flow shop scheduling problems. A new mutation operator is also described for this AIS. Fuzzy sets are used to model processing times and due dates. The objectives are to minimize the average tardiness and the number of tardy jobs. The developed new AIS algorithm is tested on real world data collected at an engine cylinder liner manufacturing process. The feasibility and effectiveness of the proposed AIS is demonstrated by comparing it with genetic algorithms. Computational results demonstrate that the proposed AIS algorithm is more effective meta-heuristic for multi objective flow shop scheduling problems with fuzzy processing time and due date.

Two-Agent Scheduling to Minimize the Maximum Cost with Position-Dependent Jobs

Directory of Open Access Journals (Sweden)

Long Wan

2015-01-01

Full Text Available This paper investigates a single-machine two-agent scheduling problem to minimize the maximum costs with position-dependent jobs. There are two agents, each with a set of independent jobs, competing to perform their jobs on a common machine. In our scheduling setting, the actual position-dependent processing time of one job is characterized by variable function dependent on the position of the job in the sequence. Each agent wants to fulfil the objective of minimizing the maximum cost of its own jobs. We develop a feasible method to achieve all the Pareto optimal points in polynomial time.

Selection and scheduling of jobs with time-dependent duration

Directory of Open Access Journals (Sweden)

DM Seegmuller

2007-06-01

Full Text Available In this paper two mathematical programming models, both with multiple objective functions, are proposed to solve four related categories of job scheduling problems. All four of these categories have the property that the duration of the jobs is dependent on the time of implementation and in some cases the preceding job. Furthermore, some jobs (restricted to subsets of the total pool of jobs can, to different extents, run in parallel. In addition, not all the jobs need necessarily be implemented during the given time period.

Two-agent scheduling in open shops subject to machine availability and eligibility constraints

Directory of Open Access Journals (Sweden)

Ling-Huey Su

2015-09-01

Full Text Available Purpose: The aims of this article are to develop a new mathematical formulation and a new heuristic for the problem of preemptive two-agent scheduling in open shops subject to machine maintenance and eligibility constraints. Design/methodology: Using the ideas of minimum cost flow network and constraint programming, a heuristic and a network based linear programming are proposed to solve the problem. Findings: Computational experiments show that the heuristic generates a good quality schedule with a deviation of 0.25% on average from the optimum and the network based linear programming model can solve problems up to 110 jobs combined with 10 machines without considering the constraint that each operation can be processed on at most one machine at a time. In order to satisfy this constraint, a time consuming Constraint Programming is proposed. For n = 80 and m = 10, the average execution time for the combined models (linear programming model combined with Constraint programming exceeds two hours. Therefore, the heuristic algorithm we developed is very efficient and is in need. Practical implications: Its practical implication occurs in TFT-LCD and E-paper manufacturing wherein units go through a series of diagnostic tests that do not have to be performed in any specified order. Originality/value: The main contribution of the article is to split the time horizon into many time intervals and use the dispatching rule for each time interval in the heuristic algorithm, and also to combine the minimum cost flow network with the Constraint Programming to solve the problem optimally. 

Performance analysis of job scheduling policies in parallel supercomputing environments

Energy Technology Data Exchange (ETDEWEB)

Naik, V.K.; Squillante, M.S. [IBM T.J. Watson Research Center, Yorktown Heights, NY (United States); Setia, S.K. [George Mason Univ., Fairfax, VA (United States). Dept. of Computer Science

1993-12-31

In this paper the authors analyze three general classes of scheduling policies under a workload typical of largescale scientific computing. These policies differ in the manner in which processors are partitioned among the jobs as well as the way in which jobs are prioritized for execution on the partitions. Their results indicate that existing static schemes do not perform well under varying workloads. Adaptive policies tend to make better scheduling decisions, but their ability to adjust to workload changes is limited. Dynamic partitioning policies, on the other hand, yield the best performance and can be tuned to provide desired performance differences among jobs with varying resource demands.

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

Tendências de aplicações da otimização por colônia de formigas na progamação de JOB-SHOPS

Directory of Open Access Journals (Sweden)

Felipe Fonseca Tavares de Freitas

2009-11-01

Full Text Available A programação da produção revela-se como uma atividade que, se bem planejada, otimizada e controlada, gera grandes vantagens competitivas e duradouras para a empresa. Um dos problemas mais complexos de programação da produção ocorre em sistemas do tipo job-shop – os quais envolvem otimização combinatória, cuja resolução em tempo computacional aceitável é quase sempre improvável (NP-hard. Neste contexto, vários métodos de otimização têm sido pesquisados e desenvolvidos nas últimas décadas, almejando-se planos de produção cada vez melhores, sob tempos de execução computacional gradativamente menores e viáveis para a indústria. Em especial, destaca-se o uso das técnicas de inteligência coletiva que, mimetizando fenômenos biológicos e sociais da natureza, vêm obtendo bons resultados quando aplicadas a problemas do tipo job shop scheduling (JSS. Revisando-se a teoria referente à meta-heurística de Otimização por Colônia de Formigas (ou Ant Colony Optimization - ACO e suas aplicações em problemas de JSS, este artigo identifica e explica as principais tendências de pesquisa nessa área, tanto a nível mundial quanto nacional. Como resultados deste estudo, pode-se vislumbrar a hibridização entre ACO e outros algoritmos de otimização e o tratamento de cenários de JSS cada vez mais complexos como as tendências mais relevantes dos trabalhos envolvendo ACO e problemas de programação de job-shops.

Filling the Holes: Work Schedulers as Job Crafters of Employment Practice in Long-Term Health Care

Science.gov (United States)

Kossek, Ellen Ernst; Piszczek, Matthew M.; Mcalpine, Kristie L.; Hammer, Leslie B.; Burke, Lisa

2016-01-01

Although work schedulers serve an organizational role influencing decisions about balancing conflicting stakeholder interests over schedules and staffing, scheduling has primarily been described as an objective activity or individual job characteristic. The authors use the lens of job crafting to examine how schedulers in 26 health care facilities enact their roles as they “fill holes” to schedule workers. Qualitative analysis of interview data suggests that schedulers expand their formal scope and influence to meet their interpretations of how to manage stakeholders (employers, workers, and patients). The authors analyze variations in the extent of job crafting (cognitive, physical, relational) to broaden role repertoires. They find evidence that some schedulers engage in rule-bound interpretation to avoid role expansion. They also identify four types of schedulers: enforcers, patient-focused schedulers, employee-focused schedulers, and balancers. The article adds to the job-crafting literature by showing that job crafting is conducted not only to create meaningful work but also to manage conflicting demands and to mediate among the competing labor interests of workers, clients, and employers. PMID:27721517

Time complexity and linear-time approximation of the ancient two-machine flow shop

NARCIS (Netherlands)

Rote, G.; Woeginger, G.J.

1998-01-01

We consider the scheduling problems F2¿Cmax and F2|no-wait|Cmax, i.e. makespan minimization in a two-machine flow shop, with and without no wait in process. For both problems solution algorithms based on sorting with O(n log n) running time are known, where n denotes the number of jobs. [1, 2]. We

Two-Agent Single-Machine Scheduling of Jobs with Time-Dependent Processing Times and Ready Times

Directory of Open Access Journals (Sweden)

Jan-Yee Kung

2013-01-01

Full Text Available Scheduling involving jobs with time-dependent processing times has recently attracted much research attention. However, multiagent scheduling with simultaneous considerations of jobs with time-dependent processing times and ready times is relatively unexplored. Inspired by this observation, we study a two-agent single-machine scheduling problem in which the jobs have both time-dependent processing times and ready times. We consider the model in which the actual processing time of a job of the first agent is a decreasing function of its scheduled position while the actual processing time of a job of the second agent is an increasing function of its scheduled position. In addition, each job has a different ready time. The objective is to minimize the total completion time of the jobs of the first agent with the restriction that no tardy job is allowed for the second agent. We propose a branch-and-bound and several genetic algorithms to obtain optimal and near-optimal solutions for the problem, respectively. We also conduct extensive computational results to test the proposed algorithms and examine the impacts of different problem parameters on their performance.

Scheduling Agreeable Jobs On A Single Machine To Minimize ...

African Journals Online (AJOL)

Journal of Applied Science and Technology ... (NP) scheduling of number of jobs on a single machine to minimize weighted number of early and tardy jobs where the earliest start times and latest due date are agreeable (i.e. earliest start time must increase in the same sequence as latest due dates) has been considered.

Design and simulation of CONWIP in the complex flexible job shop of a Make-To-Order manufacturing firm ,

Directory of Open Access Journals (Sweden)

Giovanni Romagnoli

2015-01-01

Full Text Available This paper presents a methodology for the design and integration of CONWIP in a make-to-order firm. The approach proposed was applied directly to the flexible job shop of a real manufacturing firm in order to assess the validity of the methodology. After the description of the whole plant layout, attention was focused on a section of the shop floor (21 workstations. The CONWIP system deals with multiple-product families and is characterized by path-type cards and a pull-from-the-bottleneck scheme. The cards release strategy and a customized dispatching rule were created to meet the firm’s specific needs. After the simulation model of the present state was built and validated, the future state to be implemented was created and simulated (i.e. the CONWIP system. The comparison between the two systems achieved excellent results, and showed that CONWIP is a very interesting tool for planning and controlling a complex flexible job shop.

Work schedule manager gap analysis : assessing the future training needs of work schedule managers using a strategic job analysis approach

Science.gov (United States)

2010-05-01

This report documents the results of a strategic job analysis that examined the job tasks and knowledge, skills, abilities, and other characteristics (KSAOs) needed to perform the job of a work schedule manager. The strategic job analysis compared in...

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

Scheduling preemptable jobs on identical processors under varying availability of an additional continuous resource

Directory of Open Access Journals (Sweden)

Różycki Rafał

2016-09-01

Full Text Available In this work we consider a problem of scheduling preemptable, independent jobs, characterized by the fact that their processing speeds depend on the amounts of a continuous, renewable resource allocated to jobs at a time. Jobs are scheduled on parallel, identical machines, with the criterion of minimization of the schedule length. Since two categories of resources occur in the problem: discrete (set of machines and continuous, it is generally called a discrete-continuous scheduling problem. The model studied in this paper allows the total available amount of the continuous resource to vary over time, which is a practically important generalization that has not been considered yet for discrete-continuous scheduling problems. For this model we give some properties of optimal schedules on a basis of which we propose a general methodology for solving the considered class of problems. The methodology uses a two-phase approach in which, firstly, an assignment of machines to jobs is defined and, secondly, for this assignment an optimal continuous resource allocation is found by solving an appropriate mathematical programming problem. In the approach various cases are considered, following from assumptions made on the form of the processing speed functions of jobs. For each case an iterative algorithm is designed, leading to an optimal solution in a finite number of steps.

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.

Cobacabana (control of balance by card-based navigation) : A card-based system for job shop control

NARCIS (Netherlands)

Land, M.J.

Existing card-based production control systems such as Kanban are mostly dedicated to repetitive production environments. Cards-based systems for job shop control are lacking, while particularly this industry segment shows a need for simple control systems. This paper aims at filling the gap by

A New Approach to Solve Flowshop Scheduling Problems by Artificial Immune Systems = Akış Tipi Çizelgeleme Problemlerinin Yapay Bağışıklık Sistemleri ile Çözümünde Yeni Bir Yaklaşım

Directory of Open Access Journals (Sweden)

Alper DÖYEN

2007-01-01

Full Text Available The n-job, m-machine flow shop scheduling problem is one of the most general job scheduling problems. This study deals with the criteria of makespan minimization for the flow shop scheduling problem. Artificial Immune Systems (AIS are new intelligent problem solving techniques that are being used in scheduling problems. AIS can be defined as computational systems inspired by theoretical immunology, observed immune functions, principles and mechanisms in order to solve problems. In this research, a computational method based on clonal selection principle and affinity maturation mechanisms of the immune response is used. The operation parameters of meta-heuristics have an important role on the quality of the solution. Thus, a generic systematic procedure which bases on a multi-step experimental design approach for determining the efficient system parameters for AIS is presented. Experimental results show that, the artificial immune system algorithm is more efficient than both the classical heuristic flow shop scheduling algorithms and simulated annealing.

Proportionate Flow Shop Games

NARCIS (Netherlands)

Estevez Fernandez, M.A.; Mosquera, M.A.; Borm, P.E.M.; Hamers, H.J.M.

2006-01-01

In a proportionate flow shop problem several jobs have to be processed through a fixed sequence of machines and the processing time of each job is equal on all machines.By identifying jobs with agents, whose costs linearly depend on the completion time of their jobs, and assuming an initial

An effective PSO-based memetic algorithm for flow shop scheduling.

Science.gov (United States)

Liu, Bo; Wang, Ling; Jin, Yi-Hui

2007-02-01

This paper proposes an effective particle swarm optimization (PSO)-based memetic algorithm (MA) for the permutation flow shop scheduling problem (PFSSP) with the objective to minimize the maximum completion time, which is a typical non-deterministic polynomial-time (NP) hard combinatorial optimization problem. In the proposed PSO-based MA (PSOMA), both PSO-based searching operators and some special local searching operators are designed to balance the exploration and exploitation abilities. In particular, the PSOMA applies the evolutionary searching mechanism of PSO, which is characterized by individual improvement, population cooperation, and competition to effectively perform exploration. On the other hand, the PSOMA utilizes several adaptive local searches to perform exploitation. First, to make PSO suitable for solving PFSSP, a ranked-order value rule based on random key representation is presented to convert the continuous position values of particles to job permutations. Second, to generate an initial swarm with certain quality and diversity, the famous Nawaz-Enscore-Ham (NEH) heuristic is incorporated into the initialization of population. Third, to balance the exploration and exploitation abilities, after the standard PSO-based searching operation, a new local search technique named NEH_1 insertion is probabilistically applied to some good particles selected by using a roulette wheel mechanism with a specified probability. Fourth, to enrich the searching behaviors and to avoid premature convergence, a simulated annealing (SA)-based local search with multiple different neighborhoods is designed and incorporated into the PSOMA. Meanwhile, an effective adaptive meta-Lamarckian learning strategy is employed to decide which neighborhood to be used in SA-based local search. Finally, to further enhance the exploitation ability, a pairwise-based local search is applied after the SA-based search. Simulation results based on benchmarks demonstrate the effectiveness

A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems

Directory of Open Access Journals (Sweden)

Nader Ghaffari-Nasab

2010-07-01

Full Text Available During the past two decades, there have been increasing interests on permutation flow shop with different types of objective functions such as minimizing the makespan, the weighted mean flow-time etc. The permutation flow shop is formulated as a mixed integer programming and it is classified as NP-Hard problem. Therefore, a direct solution is not available and meta-heuristic approaches need to be used to find the near-optimal solutions. In this paper, we present a new discrete firefly meta-heuristic to minimize the makespan for the permutation flow shop scheduling problem. The results of implementation of the proposed method are compared with other existing ant colony optimization technique. The preliminary results indicate that the new proposed method performs better than the ant colony for some well known benchmark problems.

Job Scheduling with Efficient Resource Monitoring in Cloud Datacenter

Directory of Open Access Journals (Sweden)

Shyamala Loganathan

2015-01-01

Full Text Available Cloud computing is an on-demand computing model, which uses virtualization technology to provide cloud resources to users in the form of virtual machines through internet. Being an adaptable technology, cloud computing is an excellent alternative for organizations for forming their own private cloud. Since the resources are limited in these private clouds maximizing the utilization of resources and giving the guaranteed service for the user are the ultimate goal. For that, efficient scheduling is needed. This research reports on an efficient data structure for resource management and resource scheduling technique in a private cloud environment and discusses a cloud model. The proposed scheduling algorithm considers the types of jobs and the resource availability in its scheduling decision. Finally, we conducted simulations using CloudSim and compared our algorithm with other existing methods, like V-MCT and priority scheduling algorithms.

Parallelization and scheduling of data intensive particle physics analysis jobs on clusters of PCs

CERN Document Server

Ponce, S

2004-01-01

Summary form only given. Scheduling policies are proposed for parallelizing data intensive particle physics analysis applications on computer clusters. Particle physics analysis jobs require the analysis of tens of thousands of particle collision events, each event requiring typically 200ms processing time and 600KB of data. Many jobs are launched concurrently by a large number of physicists. At a first view, particle physics jobs seem to be easy to parallelize, since particle collision events can be processed independently one from another. However, since large amounts of data need to be accessed, the real challenge resides in making an efficient use of the underlying computing resources. We propose several job parallelization and scheduling policies aiming at reducing job processing times and at increasing the sustainable load of a cluster server. Since particle collision events are usually reused by several jobs, cache based job splitting strategies considerably increase cluster utilization and reduce job ...

Decentralized Job Scheduling in the Cloud Based on a Spatially Generalized Prisoner’s Dilemma Game

Directory of Open Access Journals (Sweden)

Gąsior Jakub

2015-12-01

Full Text Available We present in this paper a novel distributed solution to a security-aware job scheduling problem in cloud computing infrastructures. We assume that the assignment of the available resources is governed exclusively by the specialized brokers assigned to individual users submitting their jobs to the system. The goal of this scheme is allocating a limited quantity of resources to a specific number of jobs minimizing their execution failure probability and total completion time. Our approach is based on the Pareto dominance relationship and implemented at an individual user level. To select the best scheduling strategies from the resulting Pareto frontiers and construct a global scheduling solution, we developed a decision-making mechanism based on the game-theoretic model of Spatial Prisoner’s Dilemma, realized by selfish agents operating in the two-dimensional cellular automata space. Their behavior is conditioned by the objectives of the various entities involved in the scheduling process and driven towards a Nash equilibrium solution by the employed social welfare criteria. The performance of the scheduler applied is verified by a number of numerical experiments. The related results show the effectiveness and scalability of the scheme in the presence of a large number of jobs and resources involved in the scheduling process.

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.

An Extended Flexible Job Shop Scheduling Model for Flight Deck Scheduling with Priority, Parallel Operations, and Sequence Flexibility

Directory of Open Access Journals (Sweden)

Lianfei Yu

2017-01-01

Full Text Available Efficient scheduling for the supporting operations of aircrafts in flight deck is critical to the aircraft carrier, and even several seconds’ improvement may lead to totally converse outcome of a battle. In the paper, we ameliorate the supporting operations of carrier-based aircrafts and investigate three simultaneous operation relationships during the supporting process, including precedence constraints, parallel operations, and sequence flexibility. Furthermore, multifunctional aircrafts have to take off synergistically and participate in a combat cooperatively. However, their takeoff order must be restrictively prioritized during the scheduling period accorded by certain operational regulations. To efficiently prioritize the takeoff order while minimizing the total time budget on the whole takeoff duration, we propose a novel mixed integer liner programming formulation (MILP for the flight deck scheduling problem. Motivated by the hardness of MILP, we design an improved differential evolution algorithm combined with typical local search strategies to improve computational efficiency. We numerically compare the performance of our algorithm with the classical genetic algorithm and normal differential evolution algorithm and the results show that our algorithm obtains better scheduling schemes that can meet both the operational relations and the takeoff priority requirements.

Data location-aware job scheduling in the grid. Application to the GridWay metascheduler

International Nuclear Information System (INIS)

Delgado Peris, Antonio; Hernandez, Jose; Huedo, Eduardo; Llorente, Ignacio M

2010-01-01

Grid infrastructures constitute nowadays the core of the computing facilities of the biggest LHC experiments. These experiments produce and manage petabytes of data per year and run thousands of computing jobs every day to process that data. It is the duty of metaschedulers to allocate the tasks to the most appropriate resources at the proper time. Our work reviews the policies that have been proposed for the scheduling of grid jobs in the context of very data-intensive applications. We indicate some of the practical problems that such models will face and describe what we consider essential characteristics of an optimum scheduling system: aim to minimise not only job turnaround time but also data replication, flexibility to support different virtual organisation requirements and capability to coordinate the tasks of data placement and job allocation while keeping their execution decoupled. These ideas have guided the development of an enhanced prototype for GridWay, a general purpose metascheduler, part of the Globus Toolkit and member of the EGEE's RESPECT program. Current GridWay's scheduling algorithm is unaware of data location. Our prototype makes it possible for job requests to set data needs not only as absolute requirements but also as functions for resource ranking. As our tests show, this makes it more flexible than currently used resource brokers to implement different data-aware scheduling algorithms.

Evaluating the mathematical models to Solve Job Shop Problem with the Use of human resources specialists in projects

Directory of Open Access Journals (Sweden)

Renato Penha

2012-10-01

Full Text Available A project can be defined as a complex system. This requires the use of resources (human, material, technology, etc., allocated among alternative uses, as a means to achieve specific goals by the presence of constraints of different orders. The planning, allocation and prioritization of resources, including human resource specialists (HRE, is performed by means of single project management.This treatment can cause internal strife by using the same resource or even its underuse, and may worsen in software development environments due to the high degree of interdependence, uncertainty and risk of each project. This need is related to the so called Job Shop Problem (JSP. In this context, the objective of this study is to evaluate the mathematical models of genetic algorithm and optimization and their contributions to solve Job Shop Problem in software development projects with the use of human resources specialists.

On-line scheduling on a single machine : maximizing the number of early jobs

NARCIS (Netherlands)

Hoogeveen, J.A.; Potts, C.N.; Woeginger, G.J.

2000-01-01

This note deals with the scheduling problem of maximizing the number of early jobs on a single machine. We investigate the on-line version of this problem in the Preemption-Restart model. This means that jobs may be preempted, but preempting results in all the work done on this job so far being

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.

One-machine job-scheduling with non-constant capacity - Minimizing weighted completion times

NARCIS (Netherlands)

Amaddeo, H.F.; Amaddeo, H.F.; Nawijn, W.M.; van Harten, Aart

1997-01-01

In this paper an n-job one-machine scheduling problem is considered, in which the machine capacity is time-dependent and jobs are characterized by their work content. The objective is to minimize the sum of weighted completion times. A necessary optimality condition is presented and we discuss some

ARTIFICIAL INTELLIGENCE EFFECTIVENESS IN JOB SHOP ENVIRONMENTS

Directory of Open Access Journals (Sweden)

OMAR CASTRILLON

2011-01-01

Full Text Available El objetivo del presente trabajo, es definir una nueva metodología la cual permita comparar la efectividad de algunas de las principales técnicas de inteligencia artificial (aleatorias, búsqueda tabú, minería de datos, algoritmos evolutivos. Esta metodología es aplicada en los procesos de secuenciación de la producción en ambientes job shop, en un problema con N pedidos y M máquinas, donde cada uno de los pedidos debe pasar por todas las máquinas sin importar el orden. Estas técnicas son medidas en las variables tiempo total de proceso, tiempo total muerto y porcentaje de utilización de las máquinas. Inicialmente, una revisión teórica fue realizada, esta muestra la utilidad y efectividad de la inteligencia artificial en los procesos de secuenciación de la producción. Posteriormente y con base en la experimentación planteada, los resultados obtenidos, muestran que estas técnicas presentan una efectividad superior al 95%, con un intervalo de confiabilidad del 99.5% medido en las variables objeto de estudio.

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.

Online Algorithms for Parallel Job Scheduling and Strip Packing

NARCIS (Netherlands)

Hurink, Johann L.; Paulus, J.J.

We consider the online scheduling problem of parallel jobs on parallel machines, $P|online{−}list,m_j |C_{max}$. For this problem we present a 6.6623-competitive algorithm. This improves the best known 7-competitive algorithm for this problem. The presented algorithm also applies to the problem

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.

Job Burnout and its Association With Work Schedules and Job Satisfaction Among Iranian Nurses in a Public Hospital: A Questionnaire Survey

Directory of Open Access Journals (Sweden)

Asghari

2016-08-01

Full Text Available Background Job burnout, defined as a syndrome derived from prolonged exposure to stressors at work, is often observed in health care workers. Shift work and job satisfaction are considered two of the occupational risks for burnout in nurses. Nurses have stress and health complaints. In addition, nurses are likely to job burnout. Objectives The current study aimed to determine the prevalence of job burnout and its association with work schedules and job satisfaction among Iranian nurses in a public hospital. Methods This cross-sectional study was conducted in one of the largest Iranian public hospitals among 362 nurses (response rate: 80.44% in Tehran, Iran. The Maslach burnout inventory (MBI-22 and demographic factors questionnaire were used in the present study. The relationship between job burnout with work schedules and job satisfaction was investigated with multiple logistic regression analysis. Results The mean age and work experience of the participants were 36.14 ± 8.59 and 15.23 ±9.30 years, respectively. The result indicated a relatively high prevalence of burnout (particularly, personal accomplishment among the study population. In general, 64.4% of participants reported low personal accomplishment level. The nurses engaged in shift work reported higher levels of emotional exhaustion (odds ratio (OR = 1.02, 95% confidence interval (CI = 1.006 - 1.041, P-value = 0.008; there was no relationship between work schedules with depersonalization and personal accomplishment. The result showed significant relationship between job satisfaction and emotional exhaustion (OR = 0.945, 95% CI = 0.928 - 0.963, P-value < 0.001 and personal accomplishment (OR = 1.003, 95% CI = 1.014 - 1.058, P-value = 0.001. Conclusions The current study revealed that the Iranian nurses are exposed to a considerable risk of personal accomplishment. Also, job burnout is in association with shift working and low job satisfaction level. In this regard, working pressure

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

Optimasi Penjadwalan Pengerjaan Software Pada Software House Dengan Flow-Shop Problem Menggunakan Artificial Bee Colony

Directory of Open Access Journals (Sweden)

Muhammad Fhadli

2016-12-01

This research proposed an implementation related to software execution scheduling process at a software house with Flow-Shop Problem (FSP using Artificial Bee Colony (ABC algorithm. Which in FSP required a solution to complete some job/task along with its overall cost at a minimum. There is a constraint that should be kept to note in this research, that is the uncertainty completion time of its jobs. In this research, we will present a solution that is a sequence order of project execution with its overall completion time at a minimum. An experiment will be performed with 3 attempts on each experiment conditions, that is an experiment of iteration parameter and experiment of limit parameter. From this experiment, we concluded that the use of this algorithm explained in this paper can reduce project execution time if we increase the value of total iteration and total colony. Keywords: optimization, flow-shop problem, artificial bee colony, swarm intelligence, meta-heuristic.

An Evaluation of Parallel Job Scheduling for ASCI Blue-Pacific

International Nuclear Information System (INIS)

Franke, H.; Jann, J.; Moreira, J.; Pattnaik, P.; Jette, M.

1999-01-01

In this paper we analyze the behavior of a gang-scheduling strategy that we are developing for the ASCI Blue-Pacific machines. Using actual job logs for one of the ASCI machines we generate a statistical model of the current workload with hyper Erlang distributions. We then vary the parameters of those distributions to generate various workloads, representative of different operating points of the machine. Through simulation we obtain performance parameters for three different scheduling strategies: (i) first-come first-serve, (ii) gang-scheduling, and (iii) backfilling. Our results show that backfilling, can be very effective for the common operating points in the 60-70% utilization range. However, for higher utilization rates, time-sharing techniques such as gang-scheduling offer much better performance

Multiobjective Variable Neighborhood Search algorithm for scheduling independent jobs on computational grid

Directory of Open Access Journals (Sweden)

S. Selvi

2015-07-01

Full Text Available Grid computing solves high performance and high-throughput computing problems through sharing resources ranging from personal computers to super computers distributed around the world. As the grid environments facilitate distributed computation, the scheduling of grid jobs has become an important issue. In this paper, an investigation on implementing Multiobjective Variable Neighborhood Search (MVNS algorithm for scheduling independent jobs on computational grid is carried out. The performance of the proposed algorithm has been evaluated with Min–Min algorithm, Simulated Annealing (SA and Greedy Randomized Adaptive Search Procedure (GRASP algorithm. Simulation results show that MVNS algorithm generally performs better than other metaheuristics methods.

Single machine total completion time minimization scheduling with a time-dependent learning effect and deteriorating jobs

Science.gov (United States)

Wang, Ji-Bo; Wang, Ming-Zheng; Ji, Ping

2012-05-01

In this article, we consider a single machine scheduling problem with a time-dependent learning effect and deteriorating jobs. By the effects of time-dependent learning and deterioration, we mean that the job processing time is defined by a function of its starting time and total normal processing time of jobs in front of it in the sequence. The objective is to determine an optimal schedule so as to minimize the total completion time. This problem remains open for the case of -1 < a < 0, where a denotes the learning index; we show that an optimal schedule of the problem is V-shaped with respect to job normal processing times. Three heuristic algorithms utilising the V-shaped property are proposed, and computational experiments show that the last heuristic algorithm performs effectively and efficiently in obtaining near-optimal solutions.

A multipopulation PSO based memetic algorithm for permutation flow shop scheduling.

Science.gov (United States)

Liu, Ruochen; Ma, Chenlin; Ma, Wenping; Li, Yangyang

2013-01-01

The permutation flow shop scheduling problem (PFSSP) is part of production scheduling, which belongs to the hardest combinatorial optimization problem. In this paper, a multipopulation particle swarm optimization (PSO) based memetic algorithm (MPSOMA) is proposed in this paper. In the proposed algorithm, the whole particle swarm population is divided into three subpopulations in which each particle evolves itself by the standard PSO and then updates each subpopulation by using different local search schemes such as variable neighborhood search (VNS) and individual improvement scheme (IIS). Then, the best particle of each subpopulation is selected to construct a probabilistic model by using estimation of distribution algorithm (EDA) and three particles are sampled from the probabilistic model to update the worst individual in each subpopulation. The best particle in the entire particle swarm is used to update the global optimal solution. The proposed MPSOMA is compared with two recently proposed algorithms, namely, PSO based memetic algorithm (PSOMA) and hybrid particle swarm optimization with estimation of distribution algorithm (PSOEDA), on 29 well-known PFFSPs taken from OR-library, and the experimental results show that it is an effective approach for the PFFSP.

A Multipopulation PSO Based Memetic Algorithm for Permutation Flow Shop Scheduling

Directory of Open Access Journals (Sweden)

Ruochen Liu

2013-01-01

Full Text Available The permutation flow shop scheduling problem (PFSSP is part of production scheduling, which belongs to the hardest combinatorial optimization problem. In this paper, a multipopulation particle swarm optimization (PSO based memetic algorithm (MPSOMA is proposed in this paper. In the proposed algorithm, the whole particle swarm population is divided into three subpopulations in which each particle evolves itself by the standard PSO and then updates each subpopulation by using different local search schemes such as variable neighborhood search (VNS and individual improvement scheme (IIS. Then, the best particle of each subpopulation is selected to construct a probabilistic model by using estimation of distribution algorithm (EDA and three particles are sampled from the probabilistic model to update the worst individual in each subpopulation. The best particle in the entire particle swarm is used to update the global optimal solution. The proposed MPSOMA is compared with two recently proposed algorithms, namely, PSO based memetic algorithm (PSOMA and hybrid particle swarm optimization with estimation of distribution algorithm (PSOEDA, on 29 well-known PFFSPs taken from OR-library, and the experimental results show that it is an effective approach for the PFFSP.

Handbook for Trade and Industrial Shop Teachers.

Science.gov (United States)

Texas A and M Univ., College Station. Vocational Instructional Services.

This handbook is intended to help teachers of pre-employment shop courses in organizing and delivering instruction in both the shop and classroom. Addressed in the guide are the following topics: the instructor's place in the local school organization; the instructor's job (objectives, advisory committees, occupational analysis, shop/classroom and…

Mix-oriented manufacturing control (MOMC): a quasi-optimal procedure for dynamic scheduling control

Science.gov (United States)

Cristofari, Marco; Caron, Franco; McDuffie, Ernest L.

1997-12-01

The total system throughput (ST) is one of the most important decision variables at the planning/scheduling phase of a manufacturing system. Material requirement planning (MRP) and master production schedule (MPS) are based on the assumption that ST is known. All the subsequent developments (e.g. jobs- release, system work-load, input-product mix, etc.) depends on such an assumption. If this assumption is incorrect, the production activity control (PAC) will not be able to satisfy the planned targets during the scheduling phase. Delays and bottlenecks will be unavoidable in the system. In case of random flexible manufacturing system (FMS) (or, in general, job-shop production), the measure of ST can not be evaluated a priori without running simulations or observing the actual flow of the operations in the system. The way entities enter the system (sequencing and percentage of the input products) effects the value of ST in such a way that estimation based on historical data are highly risky. The methodology proposed in this paper allows the scheduler to assess the analytical functions which link ST, and other output performance variables, to the input product mix (IPM). This way the robustness of the scheduling plan can be verified before the actual release of the jobs into the system.

Fog computing job scheduling optimization based on bees swarm

Science.gov (United States)

Bitam, Salim; Zeadally, Sherali; Mellouk, Abdelhamid

2018-04-01

Fog computing is a new computing architecture, composed of a set of near-user edge devices called fog nodes, which collaborate together in order to perform computational services such as running applications, storing an important amount of data, and transmitting messages. Fog computing extends cloud computing by deploying digital resources at the premise of mobile users. In this new paradigm, management and operating functions, such as job scheduling aim at providing high-performance, cost-effective services requested by mobile users and executed by fog nodes. We propose a new bio-inspired optimization approach called Bees Life Algorithm (BLA) aimed at addressing the job scheduling problem in the fog computing environment. Our proposed approach is based on the optimized distribution of a set of tasks among all the fog computing nodes. The objective is to find an optimal tradeoff between CPU execution time and allocated memory required by fog computing services established by mobile users. Our empirical performance evaluation results demonstrate that the proposal outperforms the traditional particle swarm optimization and genetic algorithm in terms of CPU execution time and allocated memory.

A hybrid flow shop model for an ice cream production scheduling problem

Directory of Open Access Journals (Sweden)

Imma Ribas Vila

2009-07-01

Full Text Available Normal 0 21 false false false ES X-NONE X-NONE /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Taula normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-qformat:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman","serif";} In this paper we address the scheduling problem that comes from an ice cream manufacturing company. This production system can be modelled as a three stage nowait hybrid flow shop with batch dependent setup costs. To contribute reducing the gap between theory and practice we have considered the real constraints and the criteria used by planners. The problem considered has been formulated as a mixed integer programming. Further, two competitive heuristic procedures have been developed and one of them will be proposed to schedule in the ice cream factory.

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.

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.

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.

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.

Simultaneous Scheduling of Jobs, AGVs and Tools Considering Tool Transfer Times in Multi Machine FMS By SOS Algorithm

Science.gov (United States)

Sivarami Reddy, N.; Ramamurthy, D. V., Dr.; Prahlada Rao, K., Dr.

2017-08-01

This article addresses simultaneous scheduling of machines, AGVs and tools where machines are allowed to share the tools considering transfer times of jobs and tools between machines, to generate best optimal sequences that minimize makespan in a multi-machine Flexible Manufacturing System (FMS). Performance of FMS is expected to improve by effective utilization of its resources, by proper integration and synchronization of their scheduling. Symbiotic Organisms Search (SOS) algorithm is a potent tool which is a better alternative for solving optimization problems like scheduling and proven itself. The proposed SOS algorithm is tested on 22 job sets with makespan as objective for scheduling of machines and tools where machines are allowed to share tools without considering transfer times of jobs and tools and the results are compared with the results of existing methods. The results show that the SOS has outperformed. The same SOS algorithm is used for simultaneous scheduling of machines, AGVs and tools where machines are allowed to share tools considering transfer times of jobs and tools to determine the best optimal sequences that minimize makespan.

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.

An improved ant colony optimization algorithm with fault tolerance for job scheduling in grid computing systems.

Directory of Open Access Journals (Sweden)

Hajara Idris

Full Text Available The Grid scheduler, schedules user jobs on the best available resource in terms of resource characteristics by optimizing job execution time. Resource failure in Grid is no longer an exception but a regular occurring event as resources are increasingly being used by the scientific community to solve computationally intensive problems which typically run for days or even months. It is therefore absolutely essential that these long-running applications are able to tolerate failures and avoid re-computations from scratch after resource failure has occurred, to satisfy the user's Quality of Service (QoS requirement. Job Scheduling with Fault Tolerance in Grid Computing using Ant Colony Optimization is proposed to ensure that jobs are executed successfully even when resource failure has occurred. The technique employed in this paper, is the use of resource failure rate, as well as checkpoint-based roll back recovery strategy. Check-pointing aims at reducing the amount of work that is lost upon failure of the system by immediately saving the state of the system. A comparison of the proposed approach with an existing Ant Colony Optimization (ACO algorithm is discussed. The experimental results of the implemented Fault Tolerance scheduling algorithm show that there is an improvement in the user's QoS requirement over the existing ACO algorithm, which has no fault tolerance integrated in it. The performance evaluation of the two algorithms was measured in terms of the three main scheduling performance metrics: makespan, throughput and average turnaround time.

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.

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.

The Relationship between Managerial Satisfaction and Job Turnover Intention: The Mediating Role of Job Satisfaction

Directory of Open Access Journals (Sweden)

Rüveyda Öztürk Basol

2017-09-01

Full Text Available The growth of service sector in Turkey occurs faster than the other sectors and the number of shopping malls increases correspondingly. The rapid growth of the number of shopping malls has necessitated the measurement of the attitudes of the employees in this sector. This study demonstrated that the gender, marital status and age were not the significant variables on job satisfaction, managerial satisfaction and job turnover intention; however, education status and income status were found to be significant variables on job satisfaction and job turnover intention. In addition, job satisfaction fully mediated the relationship between managerial satisfaction and job turnover intention.

Comparison of Firefly algorithm and Artificial Immune System algorithm for lot streaming in -machine flow shop scheduling

Directory of Open Access Journals (Sweden)

G. Vijay Chakaravarthy

2012-11-01

Full Text Available Lot streaming is a technique used to split the processing of lots into several sublots (transfer batches to allow the overlapping of operations in a multistage manufacturing systems thereby shortening the production time (makespan. The objective of this paper is to minimize the makespan and total flow time of -job, -machine lot streaming problem in a flow shop with equal and variable size sublots and also to determine the optimal sublot size. In recent times researchers are concentrating and applying intelligent heuristics to solve flow shop problems with lot streaming. In this research, Firefly Algorithm (FA and Artificial Immune System (AIS algorithms are used to solve the problem. The results obtained by the proposed algorithms are also compared with the performance of other worked out traditional heuristics. The computational results shows that the identified algorithms are more efficient, effective and better than the algorithms already tested for this problem.

ADAPTATION OF JOHNSON SEQUENCING ALGORITHM FOR JOB SCHEDULING TO MINIMISE THE AVERAGE WAITING TIME IN CLOUD COMPUTING ENVIRONMENT

Directory of Open Access Journals (Sweden)

SOUVIK PAL

2016-09-01

Full Text Available Cloud computing is an emerging paradigm of Internet-centric business computing where Cloud Service Providers (CSPs are providing services to the customer according to their needs. The key perception behind cloud computing is on-demand sharing of resources available in the resource pool provided by CSP, which implies new emerging business model. The resources are provisioned when jobs arrive. The job scheduling and minimization of waiting time are the challenging issue in cloud computing. When a large number of jobs are requested, they have to wait for getting allocated to the servers which in turn may increase the queue length and also waiting time. This paper includes system design for implementation which is concerned with Johnson Scheduling Algorithm that provides the optimal sequence. With that sequence, service times can be obtained. The waiting time and queue length can be reduced using queuing model with multi-server and finite capacity which improves the job scheduling model.

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.

Selective methodology of population dynamics for optimizing a multiobjective environment of job shop production

Directory of Open Access Journals (Sweden)

Santiago Ruiz

2015-01-01

Full Text Available This paper develops a methodology based on population genetics to improve the performance of two or more variables in job shop production systems. The methodology applies a genetic algorithm with special features in the individual selection when they pass from generation to generation. In comparison with the FIFO method, the proposed methodology showed better results in the variables makespan, idle time and energy cost. When compared with NSGA II, the methodology did not showed relevant differences in makespan and idle time; however better performance was obtained in energy cost and, especially, in the number of required iterations to get the optimal makespan.

Regras de prioridade eficientes que exploram características do Job Shop Flexível para a minimização do atraso total

Directory of Open Access Journals (Sweden)

Everton Luiz de Melo

2015-03-01

Full Text Available Este trabalho aborda o ambiente de produção Job Shop Flexível (JSF, extensão do problema NP-Difícil Job Shop. O JSF envolve um conjunto de jobs compostos por operações e cada operação deve ser processada em uma das máquinas habilitadas. O critério considerado é a minimização do atraso total. Inicialmente são identificadas características relacionadas à flexibilidade do sistema de produção, mais especificamente às máquinas habilitadas por operação e aos seus tempos de processamento. A seguir são propostas novas regras que exploram tais características e que são capazes de antever estados futuros do sistema. São realizados experimentos computacionais com 600 instâncias. Comparações com regras da literatura mostram que a melhor heurística proposta supera a melhor regra conhecida em 81% das instâncias.

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

Comparison of job stress and obesity in nurses with favorable and unfavorable work schedules.

Science.gov (United States)

Han, Kihye; Trinkoff, Alison M; Storr, Carla L; Geiger-Brown, Jeanne; Johnson, Karen L; Park, Sungae

2012-08-01

To compare obesity-related factors between female nurses with favorable work schedules (WSs) and unfavorable WSs. In a cross-sectional study, 1724 female nurses were stratified by WS (favorable vs unfavorable). For each schedule type, the odds of obesity were related to health behaviors, home demands, and job stress using logistic regression models. Among nurses with unfavorable WSs, healthy behaviors (exercise, sleep) were inversely associated with obesity, whereas for those with favorable WSs, obese nurses reported significantly more unhealthy behaviors (smoking, alcohol use; odds ratio [OR], 1.19; 95% confidence interval [CI], 1.02-1.38), more physical lifting of children/dependents (OR, 1.43; 95% CI, 1.06-1.93), having more nurse input into their jobs (OR, 1.21; 95% CI, 1.02-1.44), yet less boss support at work (OR, 0.83; 95% CI, 0.68-0.99). Considering impacts of WSs on obesity and potential obesity-related health outcomes, healthful scheduling should be provided to nurses.

Approximate models of job shops

OpenAIRE

Diamantidis, Alexandros

1999-01-01

Scheduling can be described as “the allocation of scarce resources over time to perform a collection of tasks”. They arise in many practical applications in manufacturing, marketing, service industries and within the operating systems of computers. Scheduling problems are frequently encountered in various activities of every day life. They exist whenever there is a choice o f the order in which a number of tasks can be performed Some examples are scheduling of classes in academic inst...

A proposal simulated annealing algorithm for proportional parallel flow shops with separated setup times

Directory of Open Access Journals (Sweden)

Helio Yochihiro Fuchigami

2014-08-01

Full Text Available This article addresses the problem of minimizing makespan on two parallel flow shops with proportional processing and setup times. The setup times are separated and sequence-independent. The parallel flow shop scheduling problem is a specific case of well-known hybrid flow shop, characterized by a multistage production system with more than one machine working in parallel at each stage. This situation is very common in various kinds of companies like chemical, electronics, automotive, pharmaceutical and food industries. This work aimed to propose six Simulated Annealing algorithms, their perturbation schemes and an algorithm for initial sequence generation. This study can be classified as “applied research” regarding the nature, “exploratory” about the objectives and “experimental” as to procedures, besides the “quantitative” approach. The proposed algorithms were effective regarding the solution and computationally efficient. Results of Analysis of Variance (ANOVA revealed no significant difference between the schemes in terms of makespan. It’s suggested the use of PS4 scheme, which moves a subsequence of jobs, for providing the best percentage of success. It was also found that there is a significant difference between the results of the algorithms for each value of the proportionality factor of the processing and setup times of flow shops.

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

Minimizing total weighted completion time in a proportionate flow shop

NARCIS (Netherlands)

Shakhlevich, N.V.; Hoogeveen, J.A.; Pinedo, M.L.

1998-01-01

We study the special case of the m machine flow shop problem in which the processing time of each operation of job j is equal to pj; this variant of the flow shop problem is known as the proportionate flow shop problem. We show that for any number of machines and for any regular performance

Future Shop: A Model Career Placement & Transition Laboratory.

Science.gov (United States)

Floyd, Deborah L.; And Others

During 1988-89, the Collin County Community College District (CCCCD) conducted a project to develop, implement, and evaluate a model career laboratory called a "Future Shop." The laboratory was designed to let users explore diverse career options, job placement opportunities, and transfer resources. The Future Shop lab had three major components:…

A Mutualism Quantum Genetic Algorithm to Optimize the Flow Shop Scheduling with Pickup and Delivery Considerations

Directory of Open Access Journals (Sweden)

Jinwei Gu

2015-01-01

Full Text Available A mutualism quantum genetic algorithm (MQGA is proposed for an integrated supply chain scheduling with the materials pickup, flow shop scheduling, and the finished products delivery. The objective is to minimize the makespan, that is, the arrival time of the last finished product to the customer. In MQGA, a new symbiosis strategy named mutualism is proposed to adjust the size of each population dynamically by regarding the mutual influence relation of the two subpopulations. A hybrid Q-bit coding method and a local speeding-up method are designed to increase the diversity of genes, and a checking routine is carried out to ensure the feasibility of each solution; that is, the total physical space of each delivery batch could not exceed the capacity of the vehicle. Compared with the modified genetic algorithm (MGA and the quantum-inspired genetic algorithm (QGA, the effectiveness and efficiency of the MQGA are validated by numerical experiments.

Emergency Radiology Practice Patterns: Shifts, Schedules, and Job Satisfaction.

Science.gov (United States)

Hanna, Tarek N; Shekhani, Haris; Lamoureux, Christine; Mar, Hanna; Nicola, Refky; Sliker, Clint; Johnson, Jamlik-Omari

2017-03-01

To assess the practice environment of emergency radiologists with a focus on schedule, job satisfaction, and self-perception of health, wellness, and diagnostic accuracy. A survey drawing from prior radiology and health care shift-work literature was distributed via e-mail to national societies, teleradiology groups, and private practices. The survey remained open for 4 weeks in 2016, with one reminder. Data were analyzed using hypothesis testing and logistic regression modeling. Response rate was 29.6% (327/1106); 69.1% of respondents (n = 226) were greater than 40 years old, 73% (n = 240) were male, and 87% (n = 284) practiced full time. With regard to annual overnight shifts (NS): 36% (n = 118) did none, 24.9% (n = 81) did 182 or more, and 15.6% (n = 51) did 119. There was a significant association between average NS worked per year and both perceived negative health effects (P impact on memory (P job enjoyment and number of annual NS (P job" for radiologists who work no NS is 2.21 times greater than for radiologists who work at least 119 NS, when shift length is held constant. Radiologists with 11+ years of experience who work no NS or 1 to 100 NS annually have lower odds of feeling overwhelmed when compared with those working the same number of NS with job satisfaction and negative health self-perception. Copyright © 2016 American College of Radiology. Published by Elsevier Inc. All rights reserved.

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.

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.

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

The Relationship between Managerial Satisfaction and Job Turnover Intention: The Mediating Role of Job Satisfaction

OpenAIRE

Rüveyda Öztürk Basol; Harun Demirkaya

2017-01-01

The growth of service sector in Turkey occurs faster than the other sectors and the number of shopping malls increases correspondingly. The rapid growth of the number of shopping malls has necessitated the measurement of the attitudes of the employees in this sector. This study demonstrated that the gender, marital status and age were not the significant variables on job satisfaction, managerial satisfaction and job turnover intention; however, education status and income...

A Mathematical Model for Scheduling a Batch Processing Machine with Multiple Incompatible Job Families, Non-identical Job dimensions, Non-identical Job sizes, Non-agreeable release times and due dates

International Nuclear Information System (INIS)

Ramasubramaniam, M; Mathirajan, M

2013-01-01

The paper addresses the problem scheduling a batch processing machine with multiple incompatible job families, non-identical job dimensions, non-identical job sizes and non-agreeable release dates to minimize makespan. The research problem is solved by proposing a mixed integer programming model that appropriately takes into account the parameters considered in the problem. The proposed is validated using a numerical example. The experiment conducted show that the model can pose significant difficulties in solving the large scale instances. The paper concludes by giving the scope for future work and some alternative approaches one can use for solving these class of problems.

Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays

NARCIS (Netherlands)

Fishkin, A.V.; Jansen, K.; Sevastyanov, S.V.; Sitters, R.A.; Leonardi, S.

2005-01-01

We present hardness and approximation results for the problem of scheduling n independent jobs on m identical parallel machines subject to a migration delay d so as to minimize the makespan. We give a sharp threshold on the value of d for which the complexity of the problem changes from polynomial

Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays

NARCIS (Netherlands)

Sevastyanov, S. V.; Sitters, R. A.; Fishkin, A.V.

2010-01-01

We present hardness and approximation results for the problem of preemptive scheduling of n independent jobs on m identical parallel machines subject to a migration delay d with the objective to minimize the makespan. We give a sharp threshold on the value of d for which the complexity of the

Parallel genetic algorithms with migration for the hybrid flow shop scheduling problem

Directory of Open Access Journals (Sweden)

K. Belkadi

2006-01-01

Full Text Available This paper addresses scheduling problems in hybrid flow shop-like systems with a migration parallel genetic algorithm (PGA_MIG. This parallel genetic algorithm model allows genetic diversity by the application of selection and reproduction mechanisms nearer to nature. The space structure of the population is modified by dividing it into disjoined subpopulations. From time to time, individuals are exchanged between the different subpopulations (migration. Influence of parameters and dedicated strategies are studied. These parameters are the number of independent subpopulations, the interconnection topology between subpopulations, the choice/replacement strategy of the migrant individuals, and the migration frequency. A comparison between the sequential and parallel version of genetic algorithm (GA is provided. This comparison relates to the quality of the solution and the execution time of the two versions. The efficiency of the parallel model highly depends on the parameters and especially on the migration frequency. In the same way this parallel model gives a significant improvement of computational time if it is implemented on a parallel architecture which offers an acceptable number of processors (as many processors as subpopulations.

A new Nawaz-Enscore-Ham-based heuristic for permutation flow-shop problems with bicriteria of makespan and machine idle time

Science.gov (United States)

Liu, Weibo; Jin, Yan; Price, Mark

2016-10-01

A new heuristic based on the Nawaz-Enscore-Ham algorithm is proposed in this article for solving a permutation flow-shop scheduling problem. A new priority rule is proposed by accounting for the average, mean absolute deviation, skewness and kurtosis, in order to fully describe the distribution style of processing times. A new tie-breaking rule is also introduced for achieving effective job insertion with the objective of minimizing both makespan and machine idle time. Statistical tests illustrate better solution quality of the proposed algorithm compared to existing benchmark heuristics.

English in the Garment Shops.

Science.gov (United States)

Verplaetse, Lorrie

This text for limited-English-speaking workers in the garment industry consits of illustrated vocabulary words, grammar lessons, narratives or brief readings, and exercises on employment-related topics. The first section focuses on shop talk, including job-specific vocabulary, simple expressions and explanations, social language, seeking and…

Parallel-aware, dedicated job co-scheduling within/across symmetric multiprocessing nodes

Science.gov (United States)

Jones, Terry R.; Watson, Pythagoras C.; Tuel, William; Brenner, Larry; ,Caffrey, Patrick; Fier, Jeffrey

2010-10-05

In a parallel computing environment comprising a network of SMP nodes each having at least one processor, a parallel-aware co-scheduling method and system for improving the performance and scalability of a dedicated parallel job having synchronizing collective operations. The method and system uses a global co-scheduler and an operating system kernel dispatcher adapted to coordinate interfering system and daemon activities on a node and across nodes to promote intra-node and inter-node overlap of said interfering system and daemon activities as well as intra-node and inter-node overlap of said synchronizing collective operations. In this manner, the impact of random short-lived interruptions, such as timer-decrement processing and periodic daemon activity, on synchronizing collective operations is minimized on large processor-count SPMD bulk-synchronous programming styles.

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.

The Impact of the Implementation Cost of Replication in Data Grid Job Scheduling

Directory of Open Access Journals (Sweden)

Babar Nazir

2018-05-01

Full Text Available Data Grids deal with geographically-distributed large-scale data-intensive applications. Schemes scheduled for data grids attempt to not only improve data access time, but also aim to improve the ratio of data availability to a node, where the data requests are generated. Data replication techniques manage large data by storing a number of data files efficiently. In this paper, we propose centralized dynamic scheduling strategy-replica placement strategies (CDSS-RPS. CDSS-RPS schedule the data and task so that it minimizes the implementation cost and data transfer time. CDSS-RPS consists of two algorithms, namely (a centralized dynamic scheduling (CDS and (b replica placement strategy (RPS. CDS considers the computing capacity of a node and finds an appropriate location for the job. RPS attempts to improve file access time by using replication on the basis of number of accesses, storage capacity of a computing node, and response time of a requested file. Extensive simulations are carried out to demonstrate the effectiveness of the proposed strategy. Simulation results demonstrate that the replication and scheduling strategies improve the implementation cost and average access time significantly.

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.

ROBUST-HYBRID GENETIC ALGORITHM FOR A FLOW-SHOP SCHEDULING PROBLEM (A Case Study at PT FSCM Manufacturing Indonesia

Directory of Open Access Journals (Sweden)

Johan Soewanda

2007-01-01

Full Text Available This paper discusses the application of Robust Hybrid Genetic Algorithm to solve a flow-shop scheduling problem. The proposed algorithm attempted to reach minimum makespan. PT. FSCM Manufacturing Indonesia Plant 4's case was used as a test case to evaluate the performance of the proposed algorithm. The proposed algorithm was compared to Ant Colony, Genetic-Tabu, Hybrid Genetic Algorithm, and the company's algorithm. We found that Robust Hybrid Genetic produces statistically better result than the company's, but the same as Ant Colony, Genetic-Tabu, and Hybrid Genetic. In addition, Robust Hybrid Genetic Algorithm required less computational time than Hybrid Genetic Algorithm

The moderating effect of control over work scheduling and overtime on the relationship between workload demands and perceived job risk.

Science.gov (United States)

Näswall, Katharina; Burt, Christopher D B; Pearce, Megan

2015-01-01

This study investigated the impact of workload demands on perceived job risk using the Job Demand-Control model as a research framework. The primary objective was to test the hypothesis that employee control over work scheduling and overtime would moderate the relationship between workload demands and perceived job risk. Ninety-six participants working in a variety of industries completed measures of workload demands, and of control over work scheduling and overtime, and a measure of perceived job risk. Workload demands predicted higher perceptions of job risk. However, the results also suggest that control over overtime moderated this relationship, where those with the combination of high workload demands and low control over overtime reported higher levels of perceived risk. The results indicate that the JDC model is applicable to safety research. The results suggest that employee control over workload demands is an important variable to consider in terms of managing workplace safety. The present study also points to important areas for future research to explore in order to further understand the connection between demands and safety.

Estimation of distribution algorithm with path relinking for the blocking flow-shop scheduling problem

Science.gov (United States)

Shao, Zhongshi; Pi, Dechang; Shao, Weishi

2018-05-01

This article presents an effective estimation of distribution algorithm, named P-EDA, to solve the blocking flow-shop scheduling problem (BFSP) with the makespan criterion. In the P-EDA, a Nawaz-Enscore-Ham (NEH)-based heuristic and the random method are combined to generate the initial population. Based on several superior individuals provided by a modified linear rank selection, a probabilistic model is constructed to describe the probabilistic distribution of the promising solution space. The path relinking technique is incorporated into EDA to avoid blindness of the search and improve the convergence property. A modified referenced local search is designed to enhance the local exploitation. Moreover, a diversity-maintaining scheme is introduced into EDA to avoid deterioration of the population. Finally, the parameters of the proposed P-EDA are calibrated using a design of experiments approach. Simulation results and comparisons with some well-performing algorithms demonstrate the effectiveness of the P-EDA for solving BFSP.

MIP Models and Hybrid Algorithms for Simultaneous Job Splitting and Scheduling on Unrelated Parallel Machines

Science.gov (United States)

Ozmutlu, H. Cenk

2014-01-01

We developed mixed integer programming (MIP) models and hybrid genetic-local search algorithms for the scheduling problem of unrelated parallel machines with job sequence and machine-dependent setup times and with job splitting property. The first contribution of this paper is to introduce novel algorithms which make splitting and scheduling simultaneously with variable number of subjobs. We proposed simple chromosome structure which is constituted by random key numbers in hybrid genetic-local search algorithm (GAspLA). Random key numbers are used frequently in genetic algorithms, but it creates additional difficulty when hybrid factors in local search are implemented. We developed algorithms that satisfy the adaptation of results of local search into the genetic algorithms with minimum relocation operation of genes' random key numbers. This is the second contribution of the paper. The third contribution of this paper is three developed new MIP models which are making splitting and scheduling simultaneously. The fourth contribution of this paper is implementation of the GAspLAMIP. This implementation let us verify the optimality of GAspLA for the studied combinations. The proposed methods are tested on a set of problems taken from the literature and the results validate the effectiveness of the proposed algorithms. PMID:24977204

MIP models and hybrid algorithms for simultaneous job splitting and scheduling on unrelated parallel machines.

Science.gov (United States)

Eroglu, Duygu Yilmaz; Ozmutlu, H Cenk

2014-01-01

We developed mixed integer programming (MIP) models and hybrid genetic-local search algorithms for the scheduling problem of unrelated parallel machines with job sequence and machine-dependent setup times and with job splitting property. The first contribution of this paper is to introduce novel algorithms which make splitting and scheduling simultaneously with variable number of subjobs. We proposed simple chromosome structure which is constituted by random key numbers in hybrid genetic-local search algorithm (GAspLA). Random key numbers are used frequently in genetic algorithms, but it creates additional difficulty when hybrid factors in local search are implemented. We developed algorithms that satisfy the adaptation of results of local search into the genetic algorithms with minimum relocation operation of genes' random key numbers. This is the second contribution of the paper. The third contribution of this paper is three developed new MIP models which are making splitting and scheduling simultaneously. The fourth contribution of this paper is implementation of the GAspLAMIP. This implementation let us verify the optimality of GAspLA for the studied combinations. The proposed methods are tested on a set of problems taken from the literature and the results validate the effectiveness of the proposed algorithms.

The One-Stop Job Shop.

Science.gov (United States)

Kiser, Kim

1998-01-01

Minnesota's WorkForce Centers are a model of state employment services. The centers assist those in need of initiatives such as dislocated worker programs, welfare-to-work services, services for the blind, employment-and-training programs, veterans' services, and job-search assistance. (JOW)

Job shop fails choosy nurses.

Science.gov (United States)

1993-10-13

Only 181 people have used the Clearing House set up to find jobs for redundant London nurses. And almost a quarter have rejected the posts which it says are suitable for them, with 21 per cent of employers turning down candidates selected by the initiative.

77 FR 34854 - Prevailing Rate Systems; Special Wage Schedules for Nonappropriated Fund Automotive Mechanics

Science.gov (United States)

2012-06-12

... hours required to complete a particular job. Since the change would de-link shop labor rates from..., and job-grading standards for uniform application by all Federal agencies. While most FWS employees... percentage of sales. Under the current commission pay plan, management controls the shop labor rate and...

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.

The triangle scheduling problem

NARCIS (Netherlands)

Dürr, Christoph; Hanzálek, Zdeněk; Konrad, Christian; Seddik, Yasmina; Sitters, R.A.; Vásquez, Óscar C.; Woeginger, Gerhard

2017-01-01

This paper introduces a novel scheduling problem, where jobs occupy a triangular shape on the time line. This problem is motivated by scheduling jobs with different criticality levels. A measure is introduced, namely the binary tree ratio. It is shown that the Greedy algorithm solves the problem to

Broadcast scheduling for mobile advertising

OpenAIRE

De Reyck, B.; Degraeve, Z.

2003-01-01

We describe a broadcast scheduling system developed for a precision marketing firm specialized in location-sensitive permission-based mobile advertising using SMS (Short Message Service) text messaging. Text messages containing advertisements were sent to registered customers when they were shopping in one of two shopping centers in the vicinity of London. The ads typically contained a limited-time promotional offer. The company's problem was deciding which ads to send out to which customers ...

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

Mechanisms for scheduling games with selfish players

NARCIS (Netherlands)

Hoeksma, R.P.

2015-01-01

Many challenges in operations research involve optimization. In particular, scheduling treats the optimal planning of tasks. This thesis focuses on machine scheduling models, where a number of tasks, called jobs, need to be scheduled on one or more machines. The outcome is determined by which job is

Work Scheduling by Use of Worker Model in Consideration of Learning by On-The-Job Training

Science.gov (United States)

Tateno, Toshitake; Shimizu, Keiko

This paper deals with a method of scheduling manual work in consideration of learning by on-the-job training (OJT). In skilled work such as maintenance of trains and airplanes, workers must learn many tasks by OJT. While the work processing time of novice workers is longer than that of experts, the time will be reduced with repeated OJT. Therefore, OJT is important for maintaining the skill level and the long-term work efficiency of an organization. In order to devise a schedule considering OJT, the scheduler must incorporate a management function of workers to trace dynamically changing work experience. In this paper, after the relationship between scheduling problems and worker management problems is defined, a simulation method, in which a worker model and an agent-based mechanism are utilized, is proposed to derive the optimal OJT strategy toward high long-term performance. Finally, we present some case studies showing the effectiveness of OJT planning based on the simulation.

Job Grading Standard for Materials Expediter WG-6705.

Science.gov (United States)

Civil Service Commission, Washington, DC. Bureau of Policies and Standards.

The standard is used to grade nonsupervisory jobs involved in routing and expediting the movement of parts, end items, supplies, and materials within production and repair facilities to meet priority needs. The work requires knowledge of material characteristics, uses, condition, industrial production shop procedures, shop layout, and internal…

Analyse af problemstillinger i moderne produktionssystemer ved hjælp af operationsanalytiske metoder

DEFF Research Database (Denmark)

Paulli, Jan

This PhD thesis consists of 6 volumes, the first being the above-mentioned Resumé. Vol. 2: Some Aspects of Applying Simulated Annealing and Tabu Search to the Quadratic Assignment Problem. Vol. 3: A Hierarchical Approach for the FMS Scheduling Problem Vol. 4: Solving the General Multiprocessor Job-shop...... Scheduling Problem (co-author: S. Dauzèrérès) Vol. 5: A Global Tabu Search Procedure for the General Multiprocessor Job-shop Scheduling Problem (co-author: S. Dauzère-Pérès) Vol. 6: Makespan Estimations in Flexible Manufacturing Systems (co-author: J.C. Fransoo, T.G. de Kok)...

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.

Design of an automatic production monitoring system on job shop manufacturing

Science.gov (United States)

Prasetyo, Hoedi; Sugiarto, Yohanes; Rosyidi, Cucuk Nur

2018-02-01

Every production process requires monitoring system, so the desired efficiency and productivity can be monitored at any time. This system is also needed in the job shop type of manufacturing which is mainly influenced by the manufacturing lead time. Processing time is one of the factors that affect the manufacturing lead time. In a conventional company, the recording of processing time is done manually by the operator on a sheet of paper. This method is prone to errors. This paper aims to overcome this problem by creating a system which is able to record and monitor the processing time automatically. The solution is realized by utilizing electric current sensor, barcode, RFID, wireless network and windows-based application. An automatic monitoring device is attached to the production machine. It is equipped with a touch screen-LCD so that the operator can use it easily. Operator identity is recorded through RFID which is embedded in his ID card. The workpiece data are collected from the database by scanning the barcode listed on its monitoring sheet. A sensor is mounted on the machine to measure the actual machining time. The system's outputs are actual processing time and machine's capacity information. This system is connected wirelessly to a workshop planning application belongs to the firm. Test results indicated that all functions of the system can run properly. This system successfully enables supervisors, PPIC or higher level management staffs to monitor the processing time quickly with a better accuracy.

MODELING AND IMPLEMENTATION OF A DISTRIBUTED SHOP FLOOR MANAGEMENT AND CONTROL SYSTEM

Institute of Scientific and Technical Information of China (English)

无

2002-01-01

Adopting distributed control architecture is the important development direction for shop floor management and control system,is also the requirement of making it agile,intelligent and concurrent. Some key problems in achieving distributed control architecture are researched. An activity model of shop floor is presented as the requirement definition of the prototype system. The multi-agent based software architecture is constructed. How the core part in shop floor management and control system,production plan and scheduling is achieved. The cooperation of different agents is illustrated. Finally,the implementation of the prototype system is narrated.

Minimizing the Makespan for a Two-Stage Three-Machine Assembly Flow Shop Problem with the Sum-of-Processing-Time Based Learning Effect

Directory of Open Access Journals (Sweden)

Win-Chin Lin

2018-01-01

Full Text Available Two-stage production process and its applications appear in many production environments. Job processing times are usually assumed to be constant throughout the process. In fact, the learning effect accrued from repetitive work experiences, which leads to the reduction of actual job processing times, indeed exists in many production environments. However, the issue of learning effect is rarely addressed in solving a two-stage assembly scheduling problem. Motivated by this observation, the author studies a two-stage three-machine assembly flow shop problem with a learning effect based on sum of the processing times of already processed jobs to minimize the makespan criterion. Because this problem is proved to be NP-hard, a branch-and-bound method embedded with some developed dominance propositions and a lower bound is employed to search for optimal solutions. A cloud theory-based simulated annealing (CSA algorithm and an iterated greedy (IG algorithm with four different local search methods are used to find near-optimal solutions for small and large number of jobs. The performances of adopted algorithms are subsequently compared through computational experiments and nonparametric statistical analyses, including the Kruskal–Wallis test and a multiple comparison procedure.

Decay-usage scheduling in multiprocessors

NARCIS (Netherlands)

Epema, D.H.J.

1998-01-01

Decay-usage scheduling is a priority-aging time-sharing scheduling policy capable of dealing with a workload of both interactive and batch jobs by decreasing the priority of a job when it acquires CPU time, and by increasing its priority when it does not use the (a) CPU. In this article we deal with

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

Machine shop basics

CERN Document Server

Miller, Rex

2004-01-01

Use the right tool the right wayHere, fully updated to include new machines and electronic/digital controls, is the ultimate guide to basic machine shop equipment and how to use it. Whether you're a professional machinist, an apprentice, a trade student, or a handy homeowner, this fully illustrated volume helps you define tools and use them properly and safely. It's packed with review questions for students, and loaded with answers you need on the job.Mark Richard Miller is a Professor and Chairman of the Industrial Technology Department at Texas A&M University in Kingsville, T

The power of reordering for online minimum makespan scheduling

OpenAIRE

Englert, Matthias; Özmen, Deniz; Westermann, Matthias

2014-01-01

In the classic minimum makespan scheduling problem, we are given an input sequence of jobs with processing times. A scheduling algorithm has to assign the jobs to m parallel machines. The objective is to minimize the makespan, which is the time it takes until all jobs are processed. In this paper, we consider online scheduling algorithms without preemption. However, we do not require that each arriving job has to be assigned immediately to one of the machines. A reordering buffer with limited...

Concurrent validation of a neurocognitive assessment protocol for clients with mental illness in job matching as shop sales in supported employment.

Science.gov (United States)

Ng, S S W; Lak, D C C; Lee, S C K; Ng, P P K

2015-03-01

Occupational therapists play a major role in the assessment and referral of clients with severe mental illness for supported employment. Nonetheless, there is scarce literature about the content and predictive validity of the process. In addition, the criteria of successful job matching have not been analysed and job supervisors have relied on experience rather than objective standards in recruitment. This study aimed to explore the profile of successful clients working in 'shop sales' in a supportive environment using a neurocognitive assessment protocol, and to validate the protocol against 'internal standards' of the job supervisors. This was a concurrent validation study of criterion-related scales for a single job type. The subjective ratings from the supervisors were concurrently validated against the results of neurocognitive assessment of intellectual function and work-related cognitive behaviour. A regression model was established for clients who succeeded and failed in employment using supervisor's ratings and a cutoff value of 10.5 for the Performance Fitness Rating Scale (R(2) = 0.918, F[41] = 3.794, p = 0.003). Classification And Regression Tree was also plotted to identify the profile of cases, with an overall accuracy of 0.861 (relative error, 0.26). Use of both inference statistics and data mining techniques enables the decision tree of neurocognitive assessments to be more readily applied by therapists in vocational rehabilitation, and thus directly improve the efficiency and efficacy of the process.

Staff Scheduling within the Retail Business in Denmark

DEFF Research Database (Denmark)

Leedgaard, Jesper; Mortensen, Kim H.; Larsen, Allan

2002-01-01

Staff Scheduling within the retail business deals with the assignment of employees such as shop assistants to work tasks so that the right number of employees are available at any given times and the total staff costs are minimized. In this paper the retail staff scheduling problem is formulated...... as a Mixed Integer Problem. The retail staff scheduling problem is solved using the metaheuristic {\\$\\backslash\\$it Simulated Annealing}. The heuristic is implemented by modifying the original MIP model. Some of the constraints defined in the MIP are relaxed, entered into the objective function and weighted...... according to their relative importance. The problem is then formulated as minimizing the overall constraint violation. A thorough parameter test has been applied to the developed heuristics. The developed system has successfully been implemented in a number of shops and stores in Denmark....

Uma propriedade estrutural do problema de programação da produção flow shop permutacional com tempos de setup

Directory of Open Access Journals (Sweden)

João Vitor Moccellin

2007-01-01

Full Text Available Neste artigo apresenta-se uma propriedade estrutural do problema de programação da produção flow shop permutacional com tempos de setup das máquinas separados dos tempos de processamento das tarefas, a qual foi identificada a partir de investigações que foram realizadas sobre as características do problema. Tal propriedade fornece um limitante superior do tempo de máquina parada entre a sua preparação e o início de execução das tarefas. Utilizando a propriedade, o problema original de programação da produção com minimização do makespan pode ser resolvido de maneira heurística por meio de uma analogia com o problema assimétrico do caixeiro-viajante.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 a structural property is introduced. Such a property provides an upper bound on the idle time of the machines between the setup task and the job processing. As an application of this property, the original scheduling problem with the makespan criterion can be heuristically solved by an analogy with the asymmetric traveling salesman problem.

CMS multicore scheduling strategy

International Nuclear Information System (INIS)

Yzquierdo, Antonio Pérez-Calero; Hernández, Jose; Holzman, Burt; Majewski, Krista; McCrea, Alison

2014-01-01

In the next years, processor architectures based on much larger numbers of cores will be most likely the model to continue 'Moore's Law' style throughput gains. This not only results in many more jobs in parallel running the LHC Run 1 era monolithic applications, but also the memory requirements of these processes push the workernode architectures to the limit. One solution is parallelizing the application itself, through forking and memory sharing or through threaded frameworks. CMS is following all of these approaches and has a comprehensive strategy to schedule multicore jobs on the GRID based on the glideinWMS submission infrastructure. The main component of the scheduling strategy, a pilot-based model with dynamic partitioning of resources that allows the transition to multicore or whole-node scheduling without disallowing the use of single-core jobs, is described. This contribution also presents the experiences made with the proposed multicore scheduling schema and gives an outlook of further developments working towards the restart of the LHC in 2015.

Optimal Scheduling for Retrieval Jobs in Double-Deep AS/RS by Evolutionary Algorithms

Directory of Open Access Journals (Sweden)

Kuo-Yang Wu

2013-01-01

Full Text Available We investigate the optimal scheduling of retrieval jobs for double-deep type Automated Storage and Retrieval Systems (AS/RS in the Flexible Manufacturing System (FMS used in modern industrial production. Three types of evolutionary algorithms, the Genetic Algorithm (GA, the Immune Genetic Algorithm (IGA, and the Particle Swarm Optimization (PSO algorithm, are implemented to obtain the optimal assignments. The objective is to minimize the working distance, that is, the shortest retrieval time travelled by the Storage and Retrieval (S/R machine. Simulation results and comparisons show the advantages and feasibility of the proposed methods.

Artificial intelligence for the CTA Observatory scheduler

Science.gov (United States)

Colomé, Josep; Colomer, Pau; Campreciós, Jordi; Coiffard, Thierry; de Oña, Emma; Pedaletti, Giovanna; Torres, Diego F.; Garcia-Piquer, Alvaro

2014-08-01

The Cherenkov Telescope Array (CTA) project will be the next generation ground-based very high energy gamma-ray instrument. The success of the precursor projects (i.e., HESS, MAGIC, VERITAS) motivated the construction of this large infrastructure that is included in the roadmap of the ESFRI projects since 2008. CTA is planned to start the construction phase in 2015 and will consist of two arrays of Cherenkov telescopes operated as a proposal-driven open observatory. Two sites are foreseen at the southern and northern hemispheres. The CTA observatory will handle several observation modes and will have to operate tens of telescopes with a highly efficient and reliable control. Thus, the CTA planning tool is a key element in the control layer for the optimization of the observatory time. The main purpose of the scheduler for CTA is the allocation of multiple tasks to one single array or to multiple sub-arrays of telescopes, while maximizing the scientific return of the facility and minimizing the operational costs. The scheduler considers long- and short-term varying conditions to optimize the prioritization of tasks. A short-term scheduler provides the system with the capability to adapt, in almost real-time, the selected task to the varying execution constraints (i.e., Targets of Opportunity, health or status of the system components, environment conditions). The scheduling procedure ensures that long-term planning decisions are correctly transferred to the short-term prioritization process for a suitable selection of the next task to execute on the array. In this contribution we present the constraints to CTA task scheduling that helped classifying it as a Flexible Job-Shop Problem case and finding its optimal solution based on Artificial Intelligence techniques. We describe the scheduler prototype that uses a Guarded Discrete Stochastic Neural Network (GDSN), for an easy representation of the possible long- and short-term planning solutions, and Constraint

A microeconomic scheduler for parallel computers

Science.gov (United States)

Stoica, Ion; Abdel-Wahab, Hussein; Pothen, Alex

1995-01-01

We describe a scheduler based on the microeconomic paradigm for scheduling on-line a set of parallel jobs in a multiprocessor system. In addition to the classical objectives of increasing the system throughput and reducing the response time, we consider fairness in allocating system resources among the users, and providing the user with control over the relative performances of his jobs. We associate with every user a savings account in which he receives money at a constant rate. When a user wants to run a job, he creates an expense account for that job to which he transfers money from his savings account. The job uses the funds in its expense account to obtain the system resources it needs for execution. The share of the system resources allocated to the user is directly related to the rate at which the user receives money; the rate at which the user transfers money into a job expense account controls the job's performance. We prove that starvation is not possible in our model. Simulation results show that our scheduler improves both system and user performances in comparison with two different variable partitioning policies. It is also shown to be effective in guaranteeing fairness and providing control over the performance of jobs.

Evaluation of a twelve-hour/day shift schedule

International Nuclear Information System (INIS)

Lewis, P.M.; Swaim, D.J.

1986-01-01

In April 1985, the operating crews at the Fast Flux Test Facility near Richland, Washington, changed their rotating shift schedule from an 8-hour to a 12-hour a day work schedule. The primary purpose of the change was to reduce the attrition of operators by increasing their job satisfaction. Eighty-four percent of the operators favored the change. A program was established to evaluate the effects on plant performance, operator alertness, attrition, sleep, health, job satisfaction, and off-the-job satisfaction. Preliminary results from that evaluation program indicate that the 12-hour shift schedule is a reasonable alternative to an 8-hour schedule at this facility

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

Doctor and pharmacy shopping for controlled substances.

Science.gov (United States)

Peirce, Gretchen L; Smith, Michael J; Abate, Marie A; Halverson, Joel

2012-06-01

Prescription drug abuse is a major health concern nationwide, with West Virginia having one of the highest prescription drug death rates in the United States. Studies are lacking that compare living subjects with persons who died from drug overdose for evidence of doctor and pharmacy shopping for controlled substances. The study objectives were to compare deceased and living subjects in West Virginia for evidence of prior doctor and pharmacy shopping for controlled substances and to identify factors associated with drug-related death. A secondary data study was conducted using controlled substance, Schedule II-IV, prescription data from the West Virginia Controlled Substance Monitoring Program and drug-related death data compiled by the Forensic Drug Database between July 2005 and December 2007. A case-control design compared deceased subjects 18 years and older whose death was drug related with living subjects for prior doctor and pharmacy shopping. Logistic regression identified factors related to the odds of drug-related death. A significantly greater proportion of deceased subjects were doctor shoppers (25.21% vs. 3.58%) and pharmacy shoppers (17.48% vs. 1.30%) than living subjects. Approximately 20.23% of doctor shoppers were also pharmacy shoppers, and 55.60% of pharmacy shoppers were doctor shoppers. Younger age, greater number of prescriptions dispensed, exposure to opioids and benzodiazepines, and doctor and pharmacy shopping were factors with greater odds of drug-related death. Doctor and pharmacy shopping involving controlled substances were identified, and shopping behavior was associated with drug-related death. Prescription monitoring programs may be useful in identifying potential shoppers at the point of care.

KASS v.2.2. scheduling software for construction

OpenAIRE

Krzemiński Michał

2016-01-01

The paper presents fourth version of specialist useful software in scheduling KASS v.2.2 (Algorithm Scheduling Krzeminski System). KASS software is designed for construction scheduling, specially form flow shop models. The program is being dedicated closely for the purposes of the construction. In distinguishing to other used programs in tasks of this type operational research criteria were designed closely with the thought about construction works and about the specificity of the building pr...

Opioid shopping behavior: how often, how soon, which drugs, and what payment method.

Science.gov (United States)

Cepeda, M Soledad; Fife, Daniel; Chow, Wing; Mastrogiovanni, Gregory; Henderson, Scott C

2013-01-01

Doctor shopping (obtaining opioid prescriptions from multiple prescribers) is one example of opioid abuse and diversion. The authors assessed how soon shopping behavior was observed after opioid exposure, number of events per shopper, preferred opioids, and method of payment. This was a cohort study. Individuals with ≤1 dispensing for any opioid in 2008 were followed for 18 months. Shopping behavior was defined as ≤2 prescriptions by different prescribers with ≤1 day of overlap and filled at ≤3 pharmacies. Of 25,161,024 subjects, 0.30% exhibited shopping behavior. Opioid-experienced subjects were 13.7 times more likely to exhibit shopping behavior and had more shopping episodes than opioid-naive subjects. Time to first shopping event was 246.90 ± 163.61 days. Number of episodes was 2.74 ± 4.66. Most subjects with shopping behavior (55.27%) had 1 shopping episode, whereas 9.52% had ≤6 episodes; 88.99% had ≤4 prescribers. Subjects with shopping behavior filled schedule II opioids more often than subjects without shopping behavior (19.51% vs 10.89%) and more often paid in cash (44.85% vs 18.54%). Three of 1000 people exposed to opioids exhibit shopping behavior, on average, 8 months after exposure. Opioid shoppers seek strong opioids, avoid combination products, often pay cash, and obtain prescriptions from few prescribers. © 2012 The Author(s).

To Capture Dynamic Shop Floor Knowledge in Global Production Networks

DEFF Research Database (Denmark)

Madsen, Erik Skov; Riis, Jens Ove; Sørensen, Brian Vejrum

2007-01-01

­ing of the jobs to be transferred and has led to a changed focus for training new workers. Secondly, the paper will address how to capture the knowl­edge associated with carrying out these jobs. And third, planning the trans­fer process will be discussed to form a basis for future continuous improve...... industrial companies with plans to transfer production units to an­other location, this paper addresses  the initial steps of pursuing this issue by presenting and testing a model for identification of the activities, task and  knowledge on the shop floor jobs. This has provided a broader understand...

Peer-to-peer Cooperative Scheduling Architecture for National Grid Infrastructure

Science.gov (United States)

Matyska, Ludek; Ruda, Miroslav; Toth, Simon

For some ten years, the Czech National Grid Infrastructure MetaCentrum uses a single central PBSPro installation to schedule jobs across the country. This centralized approach keeps a full track about all the clusters, providing support for jobs spanning several sites, implementation for the fair-share policy and better overall control of the grid environment. Despite a steady progress in the increased stability and resilience to intermittent very short network failures, growing number of sites and processors makes this architecture, with a single point of failure and scalability limits, obsolete. As a result, a new scheduling architecture is proposed, which relies on higher autonomy of clusters. It is based on a peer to peer network of semi-independent schedulers for each site or even cluster. Each scheduler accepts jobs for the whole infrastructure, cooperating with other schedulers on implementation of global policies like central job accounting, fair-share, or submission of jobs across several sites. The scheduling system is integrated with the Magrathea system to support scheduling of virtual clusters, including the setup of their internal network, again eventually spanning several sites. On the other hand, each scheduler is local to one of several clusters and is able to directly control and submit jobs to them even if the connection of other scheduling peers is lost. In parallel to the change of the overall architecture, the scheduling system itself is being replaced. Instead of PBSPro, chosen originally for its declared support of large scale distributed environment, the new scheduling architecture is based on the open-source Torque system. The implementation and support for the most desired properties in PBSPro and Torque are discussed and the necessary modifications to Torque to support the MetaCentrum scheduling architecture are presented, too.

Machine Shop Practice. Trade and Industrial Education Course of Study.

Science.gov (United States)

Emerly, Robert J.; And Others

Designed for secondary school students who are interested in becoming machinists, this beginning course guide in machine shop practice is organized into the following sections: (1) Introduction, (2) instructional plan, (3) educational philosophy, (4) specific course objectives, (5) course outline, (6) job sheets, and (7) operation sheets. The…

Construction schedules slack time minimizing

Science.gov (United States)

Krzemiński, Michał

2017-07-01

The article presents two copyright models for minimizing downtime working brigades. Models have been developed for construction schedules performed using the method of work uniform. Application of flow shop models is possible and useful for the implementation of large objects, which can be divided into plots. The article also presents a condition describing gives which model should be used, as well as a brief example of optimization schedule. The optimization results confirm the legitimacy of the work on the newly-developed models.

Sadhana | Indian Academy of Sciences

Indian Academy of Sciences (India)

Heuristic algorithms for scheduling heat-treatment furnaces of steel casting industries ... batch processors in the presence of dynamic job arrivals, incompatible job-families and non-identical job sizes. We were ... Hybrid LES – Review and assessment ... Heat transfer and heating rate of food stuffs in commercial shop ovens.

Finding Worst-Case Flexible Schedules using Coevolution

DEFF Research Database (Denmark)

Jensen, Mikkel Thomas

2001-01-01

Finding flexible schedules is important to industry, since in many environments changes such as machine breakdowns or the appearance of new jobs can happen at short notice.......Finding flexible schedules is important to industry, since in many environments changes such as machine breakdowns or the appearance of new jobs can happen at short notice....

Fatigue Risk Management: The Impact of Anesthesiology Residents' Work Schedules on Job Performance and a Review of Potential Countermeasures.

Science.gov (United States)

Wong, Lily R; Flynn-Evans, Erin; Ruskin, Keith J

2018-04-01

Long duty periods and overnight call shifts impair physicians' performance on measures of vigilance, psychomotor functioning, alertness, and mood. Anesthesiology residents typically work between 64 and 70 hours per week and are often required to work 24 hours or overnight shifts, sometimes taking call every third night. Mitigating the effects of sleep loss, circadian misalignment, and sleep inertia requires an understanding of the relationship among work schedules, fatigue, and job performance. This article reviews the current Accreditation Council for Graduate Medical Education guidelines for resident duty hours, examines how anesthesiologists' work schedules can affect job performance, and discusses the ramifications of overnight and prolonged duty hours on patient safety and resident well-being. We then propose countermeasures that have been implemented to mitigate the effects of fatigue and describe how training programs or practice groups who must work overnight can adapt these strategies for use in a hospital setting. Countermeasures include the use of scheduling interventions, strategic naps, microbreaks, caffeine use during overnight and extended shifts, and the use of bright lights in the clinical setting when possible or personal blue light devices when the room lights must be turned off. Although this review focuses primarily on anesthesiology residents in training, many of the mitigation strategies described here can be used effectively by physicians in practice.

Split scheduling with uniform setup times.

NARCIS (Netherlands)

F. Schalekamp; R.A. Sitters (René); S.L. van der Ster; L. Stougie (Leen); V. Verdugo; A. van Zuylen

2015-01-01

htmlabstractWe study a scheduling problem in which jobs may be split into parts, where the parts of a split job may be processed simultaneously on more than one machine. Each part of a job requires a setup time, however, on the machine where the job part is processed. During setup, a

Split Scheduling with Uniform Setup Times

NARCIS (Netherlands)

Schalekamp, F.; Sitters, R.A.; van der Ster, S.L.; Stougie, L.; Verdugo, V.; van Zuylen, A.

2015-01-01

We study a scheduling problem in which jobs may be split into parts, where the parts of a split job may be processed simultaneously on more than one machine. Each part of a job requires a setup time, however, on the machine where the job part is processed. During setup, a machine cannot process or

Collectives for Multiple Resource Job Scheduling Across Heterogeneous Servers

Science.gov (United States)

Tumer, K.; Lawson, J.

2003-01-01

Efficient management of large-scale, distributed data storage and processing systems is a major challenge for many computational applications. Many of these systems are characterized by multi-resource tasks processed across a heterogeneous network. Conventional approaches, such as load balancing, work well for centralized, single resource problems, but breakdown in the more general case. In addition, most approaches are often based on heuristics which do not directly attempt to optimize the world utility. In this paper, we propose an agent based control system using the theory of collectives. We configure the servers of our network with agents who make local job scheduling decisions. These decisions are based on local goals which are constructed to be aligned with the objective of optimizing the overall efficiency of the system. We demonstrate that multi-agent systems in which all the agents attempt to optimize the same global utility function (team game) only marginally outperform conventional load balancing. On the other hand, agents configured using collectives outperform both team games and load balancing (by up to four times for the latter), despite their distributed nature and their limited access to information.

The local–global conjecture for scheduling with non-linear cost

NARCIS (Netherlands)

Bansal, N.; Dürr, C.; Thang, N.K.K.; Vásquez, Ó.C.

2017-01-01

We consider the classical scheduling problem on a single machine, on which we need to schedule sequentially n given jobs. Every job j has a processing time pj and a priority weight wj, and for a given schedule a completion time Cj. In this paper, we consider the problem of minimizing the objective

Job system generation in grid taking into account user preferences

Directory of Open Access Journals (Sweden)

D. M. Yemelyanov

2016-01-01

Full Text Available Distributed computing environments like Grid are characterized by heterogeneity, low cohesion and dynamic structure of computing nodes. This is why the task of resource scheduling in such environments is complex. Different approaches to job scheduling in grid exist. Some of them use economic principles. Economic approaches to scheduling have shown their efficiency. One of such approaches is cyclic scheduling scheme which is considered in this paper.Cyclic scheduling scheme takes into account the preferences of computing environment users by means of an optimization criterion, which is included in the resource request. Besides, the scheme works cyclically by scheduling a certain job batch at each scheduling step. This is why there is a preliminary scheduling step which is job batch generation.The purpose of this study was to estimate the infl uence of job batch structure by the user criterion on the degree of its satisfaction. In other words we had to find the best way to form the batch with relation to the user optimization criterion. For example if it is more efficient to form the batch with jobs with the same criterion value or with different criterion values. Also we wanted to find the combination of criterion values which would give the most efficient scheduling results.To achieve this purpose an experiment in a simulation environment was conducted. The experiment consisted of scheduling of job batches with different values of the user criterion, other parameters of the resource request and the characteristics of the computing environment being the same. Three job batch generation strategies were considered. In the first strategy the batch consisted of jobs with the same criterion value. In the second strategy the batch consisted of jobs with all the considered criteria equally likely. The third strategy was similar to the second one, but only two certain criteria were considered. The third strategy was considered in order to find the most

Optimal Grid Scheduling Using Improved Artificial Bee Colony Algorithm

OpenAIRE

T. Vigneswari; M. A. Maluk Mohamed

2015-01-01

Job Scheduling plays an important role for efficient utilization of grid resources available across different domains and geographical zones. Scheduling of jobs is challenging and NPcomplete. Evolutionary / Swarm Intelligence algorithms have been extensively used to address the NP problem in grid scheduling. Artificial Bee Colony (ABC) has been proposed for optimization problems based on foraging behaviour of bees. This work proposes a modified ABC algorithm, Cluster Hete...

Science Shops

DEFF Research Database (Denmark)

Jørgensen, Michael Søgaard

1999-01-01

The paper prsents the overall concept of science shops as practised in most of the European science shops and present the concept practised and some experience obtained at the Technical University of Denmark. An outline for the planning of new sceince shops is presented.......The paper prsents the overall concept of science shops as practised in most of the European science shops and present the concept practised and some experience obtained at the Technical University of Denmark. An outline for the planning of new sceince shops is presented....

PENJADWALAN FLOWSHOP MENGGUNAKAN ALGORITMA NAWAZ ENSCORE HAM

Directory of Open Access Journals (Sweden)

Ilyas Masudin

2014-06-01

Full Text Available This article attempts to schedule flow shop production using Nawaz Enscore Ham (NEH to schedule jobs machining. The objective of this paper is to minimize total makespan which could reduce total production costs. This paper is based on the case study where NEH is applied in scheduling jobs in machines and then compared with the existing machine’s scheduling. The algorithm of NEH is also used to reduce idle time of machines so that the utility or performances of the machine are maintained.  The results of NEH simulation indicate that by applying NEH algorithm to scheduling machines for 10 jobs and 5 machines can reduce 2.5 per cent or 118 minutes of completing time of jobs. It also decreases total idle time of machines about 582 minutes compared with the existing scheduling.

PENJADWALAN FLOWSHOP MENGGUNAKAN ALGORITMA NAWAZ ENSCORE HAM

Directory of Open Access Journals (Sweden)

Ilyas Masudin

2014-06-01

Full Text Available This article attempts to schedule flow shop production using Nawaz Enscore Ham (NEH to schedule jobs machining. The objective of this paper is to minimize total makespan which could reduce total production costs. This paper is based on the case study where NEH is applied in scheduling jobs in machines and then compared with the existing machine’s scheduling. The algorithm of NEH is also used to reduce idle time of machines so that the utility or performances of the machine are maintained. The results of NEH simulation indicate that by applying NEH algorithm to scheduling machines for 10 jobs and 5 machines can reduce 2.5 per cent or 118 minutes of completing time of jobs. It also decreases total idle time of machines about 582 minutes compared with the existing scheduling.

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.

Tourist market segmentation by motivation to shop: A case study of Istanbul, Turkey

Directory of Open Access Journals (Sweden)

Egresi István

2017-01-01

Full Text Available Previous research has indicated that shopping could make up for a significant part of the tourist experience and could provide significant benefits to destinations by contributing to local retail revenue and by generating many jobs. In order to design better marketing strategies, destination managers must understand what attracts tourists to a destination and makes them shop while there. However, tourists represent a heterogeneous group and subgroups of individuals are motivated to visit a destination for a variety of reasons. The primary purpose of this study is to segment tourist shoppers visiting Istanbul according to their motivation to shop. Five distinctive groups of 'product-focused shoppers', 'shoppers for cultural experience', 'reluctant shoppers', 'difference seekers' and 'total shoppers' were found and compared by the geographical origin of the tourists, their socio-demographic characteristics, travel characteristics and behaviour, primary motivation for the trip, activity participation and shopping preferences and attitudes. The findings indicate that destination marketers must develop their strategies and marketing products to address the heterogeneity of motivations underlying tourist shopping.

Marriage in Honey Bees Optimization Algorithm for Flow-shop Problems

Directory of Open Access Journals (Sweden)

Pedro PALOMINOS

2012-01-01

Full Text Available The objective of this work is to make a comparative study of the Marriage in Honeybees Op-timization (MBO metaheuristic for flow-shop scheduling problems. This paper is focused on the design possibilities of the mating flight space shared by queens and drones. The proposed algorithm uses a 2-dimensional torus as an explicit mating space instead of the simulated an-nealing one in the original MBO. After testing different alternatives with benchmark datasets, the results show that the modeled and implemented metaheuristic is effective to solve flow-shop type problems, providing a new approach to solve other NP-Hard problems.

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.

Eyes Wide Shopped: Shopping Situations Trigger Arousal in Impulsive Buyers

Science.gov (United States)

Serfas, Benjamin G.; Büttner, Oliver B.; Florack, Arnd

2014-01-01

The present study proposes arousal as an important mechanism driving buying impulsiveness. We examined the effect of buying impulsiveness on arousal in non-shopping and shopping contexts. In an eye-tracking experiment, we measured pupil dilation while participants viewed and rated pictures of shopping scenes and non-shopping scenes. The results demonstrated that buying impulsiveness is closely associated with arousal as response to viewing pictures of shopping scenes. This pertained for hedonic shopping situations as well as for utilitarian shopping situations. Importantly, the effect did not emerge for non-shopping scenes. Furthermore, we demonstrated that arousal of impulsive buyers is independent from cognitive evaluation of scenes in the pictures. PMID:25489955

Eyes wide shopped: shopping situations trigger arousal in impulsive buyers.

Science.gov (United States)

Serfas, Benjamin G; Büttner, Oliver B; Florack, Arnd

2014-01-01

The present study proposes arousal as an important mechanism driving buying impulsiveness. We examined the effect of buying impulsiveness on arousal in non-shopping and shopping contexts. In an eye-tracking experiment, we measured pupil dilation while participants viewed and rated pictures of shopping scenes and non-shopping scenes. The results demonstrated that buying impulsiveness is closely associated with arousal as response to viewing pictures of shopping scenes. This pertained for hedonic shopping situations as well as for utilitarian shopping situations. Importantly, the effect did not emerge for non-shopping scenes. Furthermore, we demonstrated that arousal of impulsive buyers is independent from cognitive evaluation of scenes in the pictures.

Stochastic scheduling on unrelated machines

NARCIS (Netherlands)

Skutella, Martin; Sviridenko, Maxim; Uetz, Marc Jochen

2013-01-01

Two important characteristics encountered in many real-world scheduling problems are heterogeneous machines/processors and a certain degree of uncertainty about the actual sizes of jobs. The first characteristic entails machine dependent processing times of jobs and is captured by the classical

Semi-autonomous Intersection Collision Avoidance through Job-shop Scheduling

OpenAIRE

Ahn, Heejin; Del Vecchio, Domitilla

2016-01-01

In this paper, we design a supervisor to prevent vehicle collisions at intersections. An intersection is modeled as an area containing multiple conflict points where vehicle paths cross in the future. At every time step, the supervisor determines whether there will be more than one vehicle in the vicinity of a conflict point at the same time. If there is, then an impending collision is detected, and the supervisor overrides the drivers to avoid collision. A major challenge in the design of a ...

Lower bounds for the head-body-tail problem on parallel machines: a computational study for the multiprocessor flow shop

NARCIS (Netherlands)

A. Vandevelde; J.A. Hoogeveen; C.A.J. Hurkens (Cor); J.K. Lenstra (Jan Karel)

2005-01-01

htmlabstractThe multiprocessor flow-shop is the generalization of the flow-shop in which each machine is replaced by a set of identical machines. As finding a minimum-length schedule is NP-hard, we set out to find good lower and upper bounds. The lower bounds are based on relaxation of the

Eyes wide shopped: shopping situations trigger arousal in impulsive buyers.

Directory of Open Access Journals (Sweden)

Benjamin G Serfas

Full Text Available The present study proposes arousal as an important mechanism driving buying impulsiveness. We examined the effect of buying impulsiveness on arousal in non-shopping and shopping contexts. In an eye-tracking experiment, we measured pupil dilation while participants viewed and rated pictures of shopping scenes and non-shopping scenes. The results demonstrated that buying impulsiveness is closely associated with arousal as response to viewing pictures of shopping scenes. This pertained for hedonic shopping situations as well as for utilitarian shopping situations. Importantly, the effect did not emerge for non-shopping scenes. Furthermore, we demonstrated that arousal of impulsive buyers is independent from cognitive evaluation of scenes in the pictures.

How useful are preemptive schedules?

NARCIS (Netherlands)

Brucker, P.; Heitmann, S.; Hurink, J.L.

2001-01-01

Machine scheduling admits two options to process jobs. In a preemptive mode processing may be interrupted and resumed later even on a different machine. In a nonpreemptive mode interruptions are not allowed. Usually, the possibility to preempt jobs leads to better performance values. However, also

Multi-core processing and scheduling performance in CMS

International Nuclear Information System (INIS)

Hernández, J M; Evans, D; Foulkes, S

2012-01-01

Commodity hardware is going many-core. We might soon not be able to satisfy the job memory needs per core in the current single-core processing model in High Energy Physics. In addition, an ever increasing number of independent and incoherent jobs running on the same physical hardware not sharing resources might significantly affect processing performance. It will be essential to effectively utilize the multi-core architecture. CMS has incorporated support for multi-core processing in the event processing framework and the workload management system. Multi-core processing jobs share common data in memory, such us the code libraries, detector geometry and conditions data, resulting in a much lower memory usage than standard single-core independent jobs. Exploiting this new processing model requires a new model in computing resource allocation, departing from the standard single-core allocation for a job. The experiment job management system needs to have control over a larger quantum of resource since multi-core aware jobs require the scheduling of multiples cores simultaneously. CMS is exploring the approach of using whole nodes as unit in the workload management system where all cores of a node are allocated to a multi-core job. Whole-node scheduling allows for optimization of the data/workflow management (e.g. I/O caching, local merging) but efficient utilization of all scheduled cores is challenging. Dedicated whole-node queues have been setup at all Tier-1 centers for exploring multi-core processing workflows in CMS. We present the evaluation of the performance scheduling and executing multi-core workflows in whole-node queues compared to the standard single-core processing workflows.

Lower bounds for the head-body-tail problem on parallel machines : a computational study of the multiprocessor flow shop

NARCIS (Netherlands)

Vandevelde, A.; Hoogeveen, J.A.; Hurkens, C.A.J.; Lenstra, J.K.

2005-01-01

The multiprocessor flow-shop is the generalization of the flow-shop in which each machine is replaced by a set of identical machines. As finding a minimum-length schedule is NP-hard, we set out to find good lower and upper bounds. The lower bounds are based on relaxation of the capacities of all

Approximating Preemptive Stochastic Scheduling

OpenAIRE

Megow Nicole; Vredeveld Tjark

2009-01-01

We present constant approximative policies for preemptive stochastic scheduling. We derive policies with a guaranteed performance ratio of 2 for scheduling jobs with release dates on identical parallel machines subject to minimizing the sum of weighted completion times. Our policies as well as their analysis apply also to the recently introduced more general model of stochastic online scheduling. The performance guarantee we give matches the best result known for the corresponding determinist...

A United Framework for Solving Multiagent Task Assignment Problems

National Research Council Canada - National Science Library

Cousin, Kevin

2007-01-01

.... The CMTS descriptor represents a wide range of classical and modern problems, such as job shop scheduling, the traveling salesman problem, vehicle routing, and cooperative multi-object tracking...

Genotoxic damage in auto body shop workers.

Science.gov (United States)

Siebel, Anna Maria; Basso da Silva, Luciano

2010-10-01

Some studies have shown increased DNA damage among car painters, but other professionals working in auto body and paint shops have not been extensively assessed. The aim of this study was to assess DNA damage in different types of auto body shop workers by measuring micronucleus (MN) levels in exfoliated buccal cells. The mean number of cells with MN per 2000 exfoliated buccal cells was analyzed in three groups of male workers: auto body repair technicians, painters, and office workers (control group). All participants answered a questionnaire inquiring about age, smoking habits, alcohol consumption, work practices, occupational exposure time, job activities, and use of protective equipment. The mean number of cells with MN was 3.50 ± 1.50 in auto body painters, 3.91 ± 2.10 in auto body repair technicians, and 0.80 ± 0.78 in office workers, with a significant difference between the control group and the two other groups (p = 0.0001). Age, occupational exposure time, use of protective masks, alcohol consumption, and smoking habit did not affect MN results. The findings indicate that technicians and painters working in auto body shops are at risk for genotoxic damage, while office workers seem to be protected.

Duality-based algorithms for scheduling on unrelated parallel machines

NARCIS (Netherlands)

van de Velde, S.L.; van de Velde, S.L.

1993-01-01

We consider the following parallel machine scheduling problem. Each of n independent jobs has to be scheduled on one of m unrelated parallel machines. The processing of job J[sub l] on machine Mi requires an uninterrupted period of positive length p[sub lj]. The objective is to find an assignment of

Generic Formal Framework for Compositional Analysis of Hierarchical Scheduling Systems

DEFF Research Database (Denmark)

Boudjadar, Jalil; Hyun Kim, Jin; Thi Xuan Phan, Linh

We present a compositional framework for the specification and analysis of hierarchical scheduling systems (HSS). Firstly we provide a generic formal model, which can be used to describe any type of scheduling system. The concept of Job automata is introduced in order to model job instantiation...

MaGate Simulator: A Simulation Environment for a Decentralized Grid Scheduler

Science.gov (United States)

Huang, Ye; Brocco, Amos; Courant, Michele; Hirsbrunner, Beat; Kuonen, Pierre

This paper presents a simulator for of a decentralized modular grid scheduler named MaGate. MaGate’s design emphasizes scheduler interoperability by providing intelligent scheduling serving the grid community as a whole. Each MaGate scheduler instance is able to deal with dynamic scheduling conditions, with continuously arriving grid jobs. Received jobs are either allocated on local resources, or delegated to other MaGates for remote execution. The proposed MaGate simulator is based on GridSim toolkit and Alea simulator, and abstracts the features and behaviors of complex fundamental grid elements, such as grid jobs, grid resources, and grid users. Simulation of scheduling tasks is supported by a grid network overlay simulator executing distributed ant-based swarm intelligence algorithms to provide services such as group communication and resource discovery. For evaluation, a comparison of behaviors of different collaborative policies among a community of MaGates is provided. Results support the use of the proposed approach as a functional ready grid scheduler simulator.

A review of lot streaming in a flow shop environment with makespan criteria

Directory of Open Access Journals (Sweden)

Pedro Gómez-Gasquet

2013-07-01

Full Text Available Purpose: This paper reviews current literature and contributes a set of findings that capture the current state-of-the-art of the topic of lot streaming in a flow-shop. Design/methodology/approach: A literature review to capture, classify and summarize the main body of knowledge on lot streaming in a flow-shop with makespan criteria and, translate this into a form that is readily accessible to researchers and practitioners in the more mainstream production scheduling community. Findings and Originality/value: The existing knowledge base is somewhat fragmented. This is a relatively unexplored topic within mainstream operations management research and one which could provide rich opportunities for further exploration. Originality/value: This paper sets out to review current literature, from an advanced production scheduling perspective, and contributes a set of findings that capture the current state-of-the-art of this topic.

Work-related factors, job satisfaction and intent to leave the current job among United States nurses.

Science.gov (United States)

Han, Kihye; Trinkoff, Alison M; Gurses, Ayse P

2015-11-01

To examine the relationships of work-related factors (e.g., autonomy, work schedule, supervisory and peer support) to nurses' job satisfaction and intent to leave their current position. Low job satisfaction and high turnover of nurses are major problems for health care. To improve nurse retention, work-related factors associated with job satisfaction and intent to leave should be investigated. A cross-sectional secondary data analysis. Data were obtained in 2004 from Wave 3 of the Nurses' Worklife and Health Study. A random sample of 5000 actively licenced nurses in Illinois and North Carolina (two U.S. states) were sent the survey in wave 1, of which 1641 actively working bedside nurses participated in wave 3. We examined associations of various work-related factors with job satisfaction and intent to leave the current position. Nurses who were dissatisfied with their job reported significantly higher psychological demands and lower autonomy than nurses who were satisfied. Nurses were significantly less satisfied with their jobs when they worked longer hours with inadequate breaks or sick days. Lack of support from peers and supervisors was also related to significantly lower odds of job satisfaction. For intention to leave, nurses who said they planned to leave their current job reported significantly lower autonomy and less support from their peers than nurses who intended to stay. A variety of modifiable work-related factors were significantly related to job satisfaction and intention to leave the current job among nurses. Future research should focus on developing interventions that could mitigate these factors (e.g., by improving work schedules, increasing autonomy and/or nurse support). The impact of such interventions on job satisfaction and intention to leave the current position could then be evaluated. To increase nurse retention, improved schedules, autonomy and supportive work environments should be promoted. © 2015 John Wiley & Sons Ltd.

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

The Costs of Today's Jobs: Job Characteristics and Organizational Supports as Antecedents of Negative Spillover

Science.gov (United States)

Grotto, Angela R.; Lyness, Karen S.

2010-01-01

This study examined job characteristics and organizational supports as antecedents of negative work-to-nonwork spillover for 1178 U.S. employees. Based on hierarchical regression analyses of 2002 National Study of the Changing Workforce data and O*NET data, job demands (requirements to work at home beyond scheduled hours, job complexity, time and…

Coffee Shop As a Media for Self-Actualization Today's Youth

Directory of Open Access Journals (Sweden)

Salendra Salendra

2014-07-01

Full Text Available Trends go to a coffee shop that is currently self-actualization can be a medium for today's youth. In this study, the author uses Dramaturgy Theory introduced by Erving Goffman 1955 in The Presentation of Self in Everyday Life.                This research methods using qualitative methodology and data collection technique was done by observation, interviews and  study by literature. Trends goes to coffee shop by teen nowdays be assumed as teen’s activity to follow modern life style and it does to complete needs of self actualization.             It was concluded that the phenomenon of teenage habit to go to the coffee shop is an adolescent self-actualization behaviors performed by following a growing trend. Dramaturgy Theory discusses the two sides of teenage life in self actualize, front stage of a teenager is a person who has wide connections and likes to follow the trend of going to the coffee shop, and the back stage of the teenager is the pupil / student in an educational institution and a child in a family whose primary job is to learn and serve the elderly.

Análise de problemas de partição de instalações em sistemas job-shops por meio de modelos de redes de filas

OpenAIRE

Silva,Claudio Rogerio Negri da; Morabito,Reinaldo

2007-01-01

Este artigo estuda o problema de projeto de fábrica focalizada envolvendo a partição da instalação (planta) em subplantas e a alocação de capacidade em cada estação de trabalho das subplantas. O sistema de manufatura job-shop é representado por meio de uma rede de filas aberta genérica, e aproximações baseadas em métodos de decomposição são utilizadas para avaliar e otimizar o desempenho do sistema. O objetivo é reduzir a complexidade do sistema do ponto de vista da gestão do produto ou da ge...

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.

Simulation models generator. Applications in scheduling

Directory of Open Access Journals (Sweden)

Omar Danilo Castrillón

2013-08-01

Rev.Mate.Teor.Aplic. (ISSN 1409-2433 Vol. 20(2: 231–241, July 2013 generador de modelos de simulacion 233 will, in order to have an approach to reality to evaluate decisions in order to take more assertive. To test prototype was used as the modeling example of a production system with 9 machines and 5 works as a job shop configuration, testing stops processing times and stochastic machine to measure rates of use of machines and time average jobs in the system, as measures of system performance. This test shows the goodness of the prototype, to save the user the simulation model building

M-machine SDST flow shop scheduling using modified heuristic ...

African Journals Online (AJOL)

A computational analysis has been made to evaluate the performance of the proposed MHGA for upto 200 jobs and 20 machines problems. Comparative analysis with the help of defined performance index known as relative percentage deviation (RPD) verifies that it is viable and effective approach when compared with ...

Multi-core job submission and grid resource scheduling for ATLAS AthenaMP

CERN Document Server

Crooks, D; The ATLAS collaboration; Harrington, R; Purdie, S; Severini, H; Skipsey, S; Tsulaia, V; Washbrook, A

2012-01-01

AthenaMP is the multi-core implementation of the ATLAS software framework and allows the efficient sharing of memory pages between multiple threads of execution. This has now been validated for production and delivers a significant reduction on overall memory footprint with negligible CPU overhead. Before AthenaMP can be routinely run on the LHC Computing Grid, it must be determined how the computing resources available to ATLAS can best exploit the notable improvements delivered by switching to this multi-process model. In particular, there is a need to identify and assess the potential impact of scheduling issues where single core and multi-core job queues have access to the same underlying resources. A study into the effectiveness and scalability of AthenaMP in a production environment will be presented. Submitting AthenaMP tasks to the Tier-0 and candidate Tier-2 sites will allow detailed measurement of worker node performance and also highlight the relative performance of local resource management system...

Hygiene of work in main shops of modern coking by-product industry. [USSR

Energy Technology Data Exchange (ETDEWEB)

Kapitul' skii, V B

1984-07-01

The hygiene of working conditions is evaluated and compared for coking by-product industry shops using modern technology and machines with those using obsolete equipment and methods. Most basic factors in contamination of atmosphere of coking, pitch-coking and metal-refining shops are coal and coke dust, carbon monoxide and polycyclic aromatic hydrocarbons, especially carcinogenic benzpyrene. Contamination of air of working zone is determined by details of technology: periodicity or continuity of industrial processes, use of improved equipment for smokeless injection of charge into stoves and of hermetic pipes to remove gas with hydraulically operated caps, position of machines in shops and in coal tar distillation removal of carcinogenic benzpyrene by sulfonation and aeration. In modernized shops of coking by-product industry, illness and loss of work capacity are significantly lower than in plants using obsolete methods and equipment. Measures are presented for hygienic improvement of working conditions; both methods to further increase efficiency of technological processes and methods to protect individual worker on job such as use of respirators, protective clothing, plexiglass shields, shampoos and skin creams. 14 references.

Gold-decorated shopping centre; Golddekoriertes Shopping Center

Energy Technology Data Exchange (ETDEWEB)

Altmannshofer, Robert

2010-11-15

In the autumn 2009, the German quality seal sustainable construction for commercial new buildings was introduced. Thus, owners and operators of retail real estate and shopping centres can make clear their commitment in the matter of sustainability. The Ernst-August-Galerie (Hanover, Federal Republic of Germany) developed and operated by ECE Projektmanagement GmbH and Co. KG (Hamburg, Federal Republic of Germany) was a pilot project and also the first gold in one. With its around 150 shops, the Ernst-August-Galerie offers a supermarket, fashion outlets, a food court, service outlets and restaurants/cafes. The spacious and elegantly designed shopping mall with its piazzas and light-flooded rotundas exudes a Mediterranean air, making it a high-quality venue for shopping, strolling and leisure activities.

20 CFR 628.420 - Job training plan.

Science.gov (United States)

2010-04-01

... 20 Employees' Benefits 3 2010-04-01 2010-04-01 false Job training plan. 628.420 Section 628.420... THE JOB TRAINING PARTNERSHIP ACT Local Service Delivery System § 628.420 Job training plan. (a) The Governor shall issue instructions and schedules to assure that job training plans and plan modifications...

Differential Validities for Shop Courses: Proposal B: Follow-Up of Subjects' Work Experiences. Final Report. Vol I: Procedures and Results.

Science.gov (United States)

Isabelle, L. A.; Lokan, J. J.

Follow-up information was collected on 1500 students who attended a two-year occupational high school, in order to relate predictor measures to success during training and subsequent job success. Although not predictive of dropouts, variables in the pre-test battery did predict performance in academic and shop courses; ratings of job success were…

Doctor shopping: a concept analysis.

Science.gov (United States)

Worley, Julie; Hall, Joanne M

2012-01-01

Prescription drug abuse is a significant problem in the United States that poses a serious health risk to Americans and is therefore significant to the field of nursing. The prescription drugs that are designated in the United States as having abuse potential are called controlled or scheduled drugs. The most common types of abused prescription drugs are benzodiazepines prescribed for anxiety, opioids prescribed for pain, and stimulants prescribed for attention deficit disorder. These prescription drugs are abused by taking larger doses than prescribed for nonmedical use to achieve a high or euphoric feeling, or are sold illicitly for profit. In 2009, there were 2.4 million nonmedical users of prescription opioids in the United States. These prescription drugs are often obtained by seeing multiple prescribers, often under false pretenses or with complicity from the prescribers that leads to abuse and illicit sales. The term doctor shopping has been used not only to refer to this phenomenon but has also had other meanings throughout the past decades. Thus, concept analysis is the focus of this article for clarification using the Walker and Avant method. Health implications and suggestions for minimizing doctor shopping are included.

Significant Tasks in Training of Job-Shop Supervisors

Science.gov (United States)

Pederson, Leonard S.; Dresdow, Sally; Benson, Joy

2013-01-01

Purpose: The need for effective training of first-line supervisors is well established. Well-trained supervision is essential to our future as a country. A fundamental step in developing effective training is to develop a jobs needs assessment. In order to develop an effective needs assessment, it is necessary to know what the tasks are of…

Comparison Shopping Agents and Czech Online Customers’ Shopping Behaviour

Directory of Open Access Journals (Sweden)

Pilik Michal

2016-12-01

Full Text Available The internet has changed the lifestyles and shopping behaviours of customers. Online purchasing enables people to obtain information about products and services provided more effectively and easily, with the result that home shopping has become ordinary and usual. This paper presents part of a research focusing on online shopping customers’ behaviour in the Czech Republic. The article pertains to comparison shopping agents (CPAs, a tool which provides information to customers and helps find the best offer. The research was conducted on the basis of an online questionnaire available on an internet web page. The main results confirmed a dependency between online purchasing and the use of shopping agents, which are very popular in the Czech Republic. Almost two-thirds of online shoppers use CPAs when they engage in internet shopping. The final part of the paper addresses references and customers’ reviews as an important factor for the selection of online retailer.

QUALITY THROUGH INTEGRATION OF PRODUCTION AND SHOP FLOOR MANAGEMENT BY DISCRETE EVENT SIMULATION

Directory of Open Access Journals (Sweden)

Zoran Mirović

2007-06-01

Full Text Available With the intention to integrate strategic and tactical decision making and develop the capability of plans and schedules reconfiguration and synchronization in a very short cycle time many firms have proceeded to the adoption of ERP and Advanced Planning and Scheduling (APS technologies. The final goal is a purposeful scheduling system that guide in the right direction the current, high priority needs of the shop floor while remaining consistent with long-term production plans. The difference, and the power, of Discrete-Event Simulation (DES is its ability to mimic dynamic manufacturing systems, consisting of complex structures, and many heterogeneous interacting components. This paper describes such an integrated system (ERP/APS/DES and draw attention to the essential role of simulation based scheduling within it.

Shopping Centres and Selected Aspects of Shopping Behaviour (Brno, the Czech Republic)

Czech Academy of Sciences Publication Activity Database

Kunc, J.; Tonev, P.; Szczyrba, Z.; Frantál, Bohumil

2012-01-01

Roč. 7, č. 2 (2012), s. 39-51 ISSN 2065-4421 Institutional support: RVO:68145535 Keywords : shopping centres * shopping habits * commuting to retail shops Subject RIV: AO - Sociology, Demography http://technicalgeography.org/pdf/2_2012/05_josef_kunc_petr_tonev_zdenek_szczyrba_bohumil_frantal_shopping_centres_and_selected_aspects_of_shopping_behaviour.pdf

Flexible Work Schedules. ERIC Digest.

Science.gov (United States)

Kerka, Sandra

Flexible work schedules are one response to changes in the composition of the work force, new life-styles, and changes in work attitudes. Types of alternative work schedules are part-time and temporary employment, job sharing, and flextime. Part-time workers are a diverse group--women, the very young, and older near-retirees. Although part-time…

Disallowing Same-program Co-schedules to Improve Efficiency in Quad-core Servers

OpenAIRE

de Blanche, Andreas; Lundqvist, Thomas

2017-01-01

Programs running on different cores in a multicore server are often forced to share resources like off-chip memory, caches, I/O devices, etc. This resource sharing often leads to degraded performance, a slowdown, for the programs that share the resources. A job scheduler can improve performance by co-scheduling programs that use different resources on the same server. The most common approach to solve this co-scheduling problem has been to make job-schedulers resource aware, finding ways to c...

28 CFR 345.83 - Job safety training.

Science.gov (United States)

2010-07-01

... 28 Judicial Administration 2 2010-07-01 2010-07-01 false Job safety training. 345.83 Section 345... INDUSTRIES (FPI) INMATE WORK PROGRAMS FPI Inmate Training and Scholarship Programs § 345.83 Job safety training. FPI provides inmates with regular job safety training which is developed and scheduled in...

Some extensions of the discrete lotsizing and scheduling problem

NARCIS (Netherlands)

M. Salomon (Marc); L.G. Kroon (Leo); R. Kuik (Roelof); L.N. van Wassenhove (Luk)

1991-01-01

textabstractIn this paper the Discrete Lotsizing and Scheduling Problem (DLSP) is considered. DLSP relates to capacitated lotsizing as well as to job scheduling problems and is concerned with determining a feasible production schedule with minimal total costs in a single-stage manufacturing process.

PROPOSTA PARA IMPLANTAÇÃO DE BUSINESS INTELLIGENCE EM SHOPPING CENTER

Directory of Open Access Journals (Sweden)

Oswaldo Moreira Pereira

2016-06-01

Full Text Available The aim of the present job was to study the concepts involved in the business intelligence process to propose a solution that supports strategic decision with focus on shopping centers use. The BI technology proposed make use of SQL Server database and its tools that allows the multidimensional modeling, the transformation of data into strategic knowledge and the presentation of the results by the analytical processing information.

Scheduling Maintenance Jobs in Networks

OpenAIRE

Abed, Fidaa; Chen, Lin; Disser, Yann; Groß, Martin; Megow, Nicole; Meißner, Julie; Richter, Alexander T.; Rischke, Roman

2017-01-01

We investigate the problem of scheduling the maintenance of edges in a network, motivated by the goal of minimizing outages in transportation or telecommunication networks. We focus on maintaining connectivity between two nodes over time; for the special case of path networks, this is related to the problem of minimizing the busy time of machines. We show that the problem can be solved in polynomial time in arbitrary networks if preemption is allowed. If preemption is restricted to integral t...

Limited access: gender, occupational composition, and flexible work scheduling.

Science.gov (United States)

Glauber, Rebecca

2011-01-01

The current study draws on national data to explore differences in access to flexible work scheduling by the gender composition of women's and men's occupations. Results show that those who work in integrated occupations are more likely to have access to flexible scheduling. Women and men do not take jobs with lower pay in return for greater access to flexibility. Instead, jobs with higher pay offer greater flexibility. Integrated occupations tend to offer the greatest access to flexible scheduling because of their structural locations. Part-time work is negatively associated with men's access to flexible scheduling but positively associated with women's access. Women have greater flexibility when they work for large establishments, whereas men have greater flexibility when they work for small establishments.

Constraint-Directed Search: A Case Study of Job-Shop Scheduling.

Science.gov (United States)

1983-12-13

Structures But Were Unable to Represent", Proceedings of the American Association for Aritificial Intelligence , pp. 212-214, Stanford University...under these constraints raises a number of issues of interest to the artificial intelligence community such as: - knowledge representation semantics for...Management Science 15 2.3. Artificial Intelligence 17 2.4. Relationship to Previous Research 21 3. ISIS Modeling System 23 3.1. Introduction 24 3.2. Layer

ShopComm: Community-Supported Online Shopping for Older Adults.

Science.gov (United States)

Gorkovenko, Katerina; Tigwell, Garreth W; Norrie, Christopher S; Waite, Miriam; Herron, Daniel

2017-01-01

The United Kingdom has an ageing population whose members experience significant life transitions as they grow older, for example, losing mobility due to deteriorating health. For these adults, digital technology has the potential to sustain their independence and improve their quality of life. However older adults can be reluctant to use digital solutions. In this paper, we review a local charity providing a grocery shopping service for older adults who are unable to go themselves. We explore how older adults perceive the benefits and drawbacks of both physical and digital shopping. Using these insights, we designed ShopComm to enable and support older adults with mobility impairments to shop online.

Optimal Algorithms and a PTAS for Cost-Aware Scheduling

NARCIS (Netherlands)

L. Chen; N. Megow; R. Rischke; L. Stougie (Leen); J. Verschae

2015-01-01

htmlabstractWe consider a natural generalization of classical scheduling problems in which using a time unit for processing a job causes some time-dependent cost which must be paid in addition to the standard scheduling cost. We study the scheduling objectives of minimizing the makespan and the

A Pareto-Based Adaptive Variable Neighborhood Search for Biobjective Hybrid Flow Shop Scheduling Problem with Sequence-Dependent Setup Time

Directory of Open Access Journals (Sweden)

Huixin Tian

2016-01-01

Full Text Available Different from most researches focused on the single objective hybrid flowshop scheduling (HFS problem, this paper investigates a biobjective HFS problem with sequence dependent setup time. The two objectives are the minimization of total weighted tardiness and the total setup time. To efficiently solve this problem, a Pareto-based adaptive biobjective variable neighborhood search (PABOVNS is developed. In the proposed PABOVNS, a solution is denoted as a sequence of all jobs and a decoding procedure is presented to obtain the corresponding complete schedule. In addition, the proposed PABOVNS has three major features that can guarantee a good balance of exploration and exploitation. First, an adaptive selection strategy of neighborhoods is proposed to automatically select the most promising neighborhood instead of the sequential selection strategy of canonical VNS. Second, a two phase multiobjective local search based on neighborhood search and path relinking is designed for each selected neighborhood. Third, an external archive with diversity maintenance is adopted to store the nondominated solutions and at the same time provide initial solutions for the local search. Computational results based on randomly generated instances show that the PABOVNS is efficient and even superior to some other powerful multiobjective algorithms in the literature.

Omni channel fashion shopping

NARCIS (Netherlands)

Kemperman, A.D.A.M.; van Delft, L.; Borgers, A.W.J.; Pantano, E.

2015-01-01

This chapter gives insight into consumers' online and offline fashion shopping behavior, consumers' omni-channel usage during the shopping process, and consumer fashion shopper segments. Based on a literature review, omni-channel shopping behavior during the shopping process was operationalized.

Time-constrained project scheduling with adjacent resources

NARCIS (Netherlands)

Hurink, Johann L.; Kok, A.L.; Paulus, J.J.; Schutten, Johannes M.J.

We develop a decomposition method for the Time-Constrained Project Scheduling Problem (TCPSP) with adjacent resources. For adjacent resources the resource units are ordered and the units assigned to a job have to be adjacent. On top of that, adjacent resources are not required by single jobs, but by

Time-constrained project scheduling with adjacent resources

NARCIS (Netherlands)

Hurink, Johann L.; Kok, A.L.; Paulus, J.J.; Schutten, Johannes M.J.

2008-01-01

We develop a decomposition method for the Time-Constrained Project Scheduling Problem (TCPSP) with Adjacent Resources. For adjacent resources the resource units are ordered and the units assigned to a job have to be adjacent. On top of that, adjacent resources are not required by single jobs, but by

Perancangan Sistem Penjadwalan Mesin Hybrid Flow Shop dengan Algoritma Levyflight Discrete Firefly

Directory of Open Access Journals (Sweden)

Andrew Verrayo Limas

2014-12-01

Full Text Available The main issues that have been encountered in PT Surya Toto Indonesia is companies do not know how to measure the performance of the production process so as the utilization of resources that will be used isn’t yet to be known with efficiently. The purpose of this case studies is creating a better production processes by proposing a better and systematic scheduling information system. An Object Oriented Analysis and Design method is used to determine system’s requirements and design of the system architecture. Metaheuristic methods such as Discrete algorithms Levy-flight Firefly is used to improve the performance of the Hybrid Flow Shop machine scheduling become more better. Indicators that are used to determine the performance of the scheduling is makespan and lateness. Results from this algorithm is makespan value of 305.27 hours with lateness value of 10.92 which determine that there is no delays in scheduling. Scheduling information system was designed three primary capabilities, which are integrated data management, inventory management and a systematic and accurate scheduling system.

Environment-Aware Production Schedulingfor Paint Shops in Automobile Manufacturing: A Multi-Objective Optimization Approach.

Science.gov (United States)

Zhang, Rui

2017-12-25

The traditional way of scheduling production processes often focuses on profit-driven goals (such as cycle time or material cost) while tending to overlook the negative impacts of manufacturing activities on the environment in the form of carbon emissions and other undesirable by-products. To bridge the gap, this paper investigates an environment-aware production scheduling problem that arises from a typical paint shop in the automobile manufacturing industry. In the studied problem, an objective function is defined to minimize the emission of chemical pollutants caused by the cleaning of painting devices which must be performed each time before a color change occurs. Meanwhile, minimization of due date violations in the downstream assembly shop is also considered because the two shops are interrelated and connected by a limited-capacity buffer. First, we have developed a mixed-integer programming formulation to describe this bi-objective optimization problem. Then, to solve problems of practical size, we have proposed a novel multi-objective particle swarm optimization (MOPSO) algorithm characterized by problem-specific improvement strategies. A branch-and-bound algorithm is designed for accurately assessing the most promising solutions. Finally, extensive computational experiments have shown that the proposed MOPSO is able to match the solution quality of an exact solver on small instances and outperform two state-of-the-art multi-objective optimizers in literature on large instances with up to 200 cars.

Multiagent scheduling models and algorithms

CERN Document Server

Agnetis, Alessandro; Gawiejnowicz, Stanisław; Pacciarelli, Dario; Soukhal, Ameur

2014-01-01

This book presents multi-agent scheduling models in which subsets of jobs sharing the same resources are evaluated by different criteria. It discusses complexity results, approximation schemes, heuristics and exact algorithms.

ATTITUDES TOWARD ONLINE SHOPPING FROM THE ASPECTS OF PERSONAL CHARACTERISTICS AND SHOPPING MOTIVE THROUGH A DEVELOPING CONCEPT: PRIVATE SHOPPING

OpenAIRE

BAYBARS, Miray; USTUNDAGLI, Elif

2011-01-01

Private shopping is one of the concepts that serve as a members-only online shopping platform with deep discounts and well-known brands. The aim of this paper is to determine whether consumers’ need for uniqueness and innovativeness as a personal trait and price discount orientation affect consumer attitudes toward private shopping and their purchase decision or not. Research results revealed that need for uniqueness and innovativeness affect positive attitudes towards private shopping positi...

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

Supporting the Supermarket Shopping Experience through a Context-Aware Shopping Trolley

DEFF Research Database (Denmark)

Black, Darren; Clemmensen, Nils Jakob; Skov, Mikael B.

2009-01-01

Shopping in the real world is becoming an increasingly interactive experience as stores integrate various technologies to support shoppers. Based on an empirical study of supermarket shoppers, we designed a mobile context-aware system called the Context- Aware Shopping Trolley (CAST). The aim...... of the system is to support shopping in supermarkets through context-awareness and acquiring user attention. Thus, the interactive trolley guides and directs shoppers in the handling and finding of groceries. An empirical evaluation showed that shoppers using CAST adapted in different shopping behavior than...... traditional trolley shoppers by exhibiting a more uniform behavior in terms of product sequence collection and ease of finding products and thus, CAST supported the shopping experience....

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

Research Article Special Issue

African Journals Online (AJOL)

pc

2018-03-07

Mar 7, 2018 ... to find an optimization in the work process. ... and waiting time will affect the productivity too as more product could be produced ... genetic algorithm that based on the opposition-based learning in flexible job shop scheduling.

Shopping online and/or in-store? A structural equation model of the relationships between e-shopping and in-store shopping

OpenAIRE

Farag, Sendy; Schwanen, Tim; Dijst, Martin

2005-01-01

Searching product information or buying goods online is becoming increasingly popular and could affect shopping trips. However, the relationship between e-shopping and in-store shopping is currently unclear. The aim of this study is to investigate empirically how the frequencies of online searching, online buying, and non-daily shopping trips relate to each other, after controlling for sociodemographic, land use, behavioral, and attitudinal characteristics. Data were collected from 826 respon...

Mistral Supercomputer Job History Analysis

OpenAIRE

Zasadziński, Michał; Muntés-Mulero, Victor; Solé, Marc; Ludwig, Thomas

2018-01-01

In this technical report, we show insights and results of operational data analysis from petascale supercomputer Mistral, which is ranked as 42nd most powerful in the world as of January 2018. Data sources include hardware monitoring data, job scheduler history, topology, and hardware information. We explore job state sequences, spatial distribution, and electric power patterns.

Scheduling in Heterogeneous Grid Environments: The Effects of DataMigration

Energy Technology Data Exchange (ETDEWEB)

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

2004-01-01

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 goal can be fully realized. One problem critical to the effective utilization of computational grids is efficient job scheduling. Our prior work addressed this challenge by defining a grid scheduling architecture and several job migration strategies. The focus of this study is to explore the impact of data migration under a variety of demanding grid conditions. We evaluate our grid scheduling algorithms by simulating compute servers, various groupings of servers into sites, and inter-server networks, using real workloads obtained from leading supercomputing centers. Several key performance metrics are used to compare the behavior of our algorithms against reference local and centralized scheduling schemes. Results show the tremendous benefits of grid scheduling, even in the presence of input/output data migration - while highlighting the importance of utilizing communication-aware scheduling schemes.

A Market-Based Approach to Multi-factory Scheduling

Science.gov (United States)

Vytelingum, Perukrishnen; Rogers, Alex; MacBeth, Douglas K.; Dutta, Partha; Stranjak, Armin; Jennings, Nicholas R.

In this paper, we report on the design of a novel market-based approach for decentralised scheduling across multiple factories. Specifically, because of the limitations of scheduling in a centralised manner - which requires a center to have complete and perfect information for optimality and the truthful revelation of potentially commercially private preferences to that center - we advocate an informationally decentralised approach that is both agile and dynamic. In particular, this work adopts a market-based approach for decentralised scheduling by considering the different stakeholders representing different factories as self-interested, profit-motivated economic agents that trade resources for the scheduling of jobs. The overall schedule of these jobs is then an emergent behaviour of the strategic interaction of these trading agents bidding for resources in a market based on limited information and their own preferences. Using a simple (zero-intelligence) bidding strategy, we empirically demonstrate that our market-based approach achieves a lower bound efficiency of 84%. This represents a trade-off between a reasonable level of efficiency (compared to a centralised approach) and the desirable benefits of a decentralised solution.

Active Job Monitoring in Pilots

Science.gov (United States)

Kuehn, Eileen; Fischer, Max; Giffels, Manuel; Jung, Christopher; Petzold, Andreas

2015-12-01

Recent developments in high energy physics (HEP) including multi-core jobs and multi-core pilots require data centres to gain a deep understanding of the system to monitor, design, and upgrade computing clusters. Networking is a critical component. Especially the increased usage of data federations, for example in diskless computing centres or as a fallback solution, relies on WAN connectivity and availability. The specific demands of different experiments and communities, but also the need for identification of misbehaving batch jobs, requires an active monitoring. Existing monitoring tools are not capable of measuring fine-grained information at batch job level. This complicates network-aware scheduling and optimisations. In addition, pilots add another layer of abstraction. They behave like batch systems themselves by managing and executing payloads of jobs internally. The number of real jobs being executed is unknown, as the original batch system has no access to internal information about the scheduling process inside the pilots. Therefore, the comparability of jobs and pilots for predicting run-time behaviour or network performance cannot be ensured. Hence, identifying the actual payload is important. At the GridKa Tier 1 centre a specific tool is in use that allows the monitoring of network traffic information at batch job level. This contribution presents the current monitoring approach and discusses recent efforts and importance to identify pilots and their substructures inside the batch system. It will also show how to determine monitoring data of specific jobs from identified pilots. Finally, the approach is evaluated.

An iPad™-based picture and video activity schedule increases community shopping skills of a young adult with autism spectrum disorder and intellectual disability.

Science.gov (United States)

Burckley, Elizabeth; Tincani, Matt; Guld Fisher, Amanda

2015-04-01

To evaluate the iPad 2™ with Book Creator™ software to provide visual cues and video prompting to teach shopping skills in the community to a young adult with an autism spectrum disorder and intellectual disability. A multiple probe across settings design was used to assess effects of the intervention on the participant's independence with following a shopping list in a grocery store across three community locations. Visual cues and video prompting substantially increased the participant's shopping skills within two of the three community locations, skill increases maintained after the intervention was withdrawn, and shopping skills generalized to two untaught shopping items. Social validity surveys suggested that the participant's parent and staff favorably viewed the goals, procedures, and outcomes of intervention. The iPad 2™ with Book Creator™ software may be an effective way to teach independent shopping skills in the community; additional replications are needed.

Internet Shopping

Institute of Scientific and Technical Information of China (English)

刘洪毓

2004-01-01

Nowadays you no longer need to walk round hundreds of shops looking for the items you need. You can shop for just about anything from your armchair. All you need is a computer and access(进入) to the Internet.

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 multi-group and preemptable scheduling of cloud resource based on HTCondor

Science.gov (United States)

Jiang, Xiaowei; Zou, Jiaheng; Cheng, Yaodong; Shi, Jingyan

2017-10-01

Due to the features of virtual machine-flexibility, easy controlling and various system environments, more and more fields utilize the virtualization technology to construct the distributed system with the virtual resources, also including high energy physics. This paper introduce a method used in high energy physics that supports multiple resource group and preemptable cloud resource scheduling, combining virtual machine with HTCondor (a batch system). It makes resource controlling more flexible and more efficient and makes resource scheduling independent of job scheduling. Firstly, the resources belong to different experiment-groups, and the type of user-groups mapping to resource-groups(same as experiment-group) is one-to-one or many-to-one. In order to make the confused group simply to be managed, we designed the permission controlling component to ensure that the different resource-groups can get the suitable jobs. Secondly, for the purpose of elastically allocating resources for suitable resource-group, it is necessary to schedule resources like scheduling jobs. So this paper designs the cloud resource scheduling to maintain a resource queue and allocate an appropriate amount of virtual resources to the request resource-group. Thirdly, in some kind of situations, because of the resource occupied for a long time, resources need to be preempted. This paper adds the preemption function for the resource scheduling that implement resource preemption based on the group priority. Additionally, the way to preempting is soft that when virtual resources are preempted, jobs will not be killed but also be held and rematched later. It is implemented with the help of HTCondor, storing the held job information in scheduler, releasing the job to idle status and doing second matcher. In IHEP (institute of high energy physics), we have built a batch system based on HTCondor with a virtual resources pool based on Openstack. And this paper will show some cases of experiment JUNO

Parallel patterns determination in solving cyclic flow shop problem with setups

Directory of Open Access Journals (Sweden)

Bożejko Wojciech

2017-06-01

Full Text Available The subject of this work is the new idea of blocks for the cyclic flow shop problem with setup times, using multiple patterns with different sizes determined for each machine constituting optimal schedule of cities for the traveling salesman problem (TSP. We propose to take advantage of the Intel Xeon Phi parallel computing environment during so-called ’blocks’ determination basing on patterns, in effect significantly improving the quality of obtained results.

A new mathematical model for single machine batch scheduling problem for minimizing maximum lateness with deteriorating jobs

Directory of Open Access Journals (Sweden)

Ahmad Zeraatkar Moghaddam

2012-01-01

Full Text Available This paper presents a mathematical model for the problem of minimizing the maximum lateness on a single machine when the deteriorated jobs are delivered to each customer in various size batches. In reality, this issue may happen within a supply chain in which delivering goods to customers entails cost. Under such situation, keeping completed jobs to deliver in batches may result in reducing delivery costs. In literature review of batch scheduling, minimizing the maximum lateness is known as NP-Hard problem; therefore the present issue aiming at minimizing the costs of delivering, in addition to the aforementioned objective function, remains an NP-Hard problem. In order to solve the proposed model, a Simulation annealing meta-heuristic is used, where the parameters are calibrated by Taguchi approach and the results are compared to the global optimal values generated by Lingo 10 software. Furthermore, in order to check the efficiency of proposed method to solve larger scales of problem, a lower bound is generated. The results are also analyzed based on the effective factors of the problem. Computational study validates the efficiency and the accuracy of the presented model.

Job Sharing: An Employment Alternative for the Career Services Professional.

Science.gov (United States)

Johnson, Louise; Meerdink, Lois A.

1985-01-01

Describes and assesses job sharing as an employment alternative for career services professionals. Discusses the job-sharing format with regard to fringe benefits, scheduling, advantages, client reactions, potential problems, and specific factors that contribute to successful job sharing. (BH)

THE INFLUENCE OF HEDONIC SHOPPING MOTIVATION TO THE IMPULSE BUYING OF ONLINE-SHOPPING CONSUMER ON INSTAGRAM

Directory of Open Access Journals (Sweden)

Asnawati

2018-02-01

Full Text Available This research aims to know the influence of Adventure Shopping, Relaxation Shopping, Value Shopping, Social Shopping and Idea Shopping variables to the variable of Impulse Buying of Online-Shopping Consumer on Instagram. The type of the research is explanatory research. The result of F-test showed that Fcount (12.829 > Ftable (2.669 which meant that research variables had influences to the Impulse Buying. With partial correlation value of 0.548, Idea Shopping variable became the dominant factor influencing Impulse Buying on the online-shopping purchase on Instagram.

Scheduling permutation flowshops with initial availability constraint: Analysis of solutions and constructive heuristics

OpenAIRE

Pérez González, Paz; Framiñán Torres, José Manuel

2009-01-01

In this paper, we address the problem of scheduling a set of jobs in a flowshop with makespan objective. In contrast to the usual assumption of machine availability presented in most research, we consider that machines may not be available at the beginning of the planning period, due to processing of previously scheduled jobs. We first formulate the problem, analyse the structure of solutions depending on a number of factors (such as machines, jobs, structure of the processing times, availabi...

Evolutionary heuristic for makespan minimization in no-idle flow shop production systems - doi: 10.4025/actascitechnol.v35i2.12534

Directory of Open Access Journals (Sweden)

Marcelo Seido Nagano

2013-04-01

Full Text Available This paper deals with no-idle flow shop scheduling problem with the objective of minimizing makespan. A new hybrid metaheuristic is proposed for the scheduling problem solution. The proposed method is compared with the best method reported in the literature. Experimental results show that the new method provides better solutions regarding the solution quality to set of problems evaluated.  

Scheduling with Learning Effects and/or Time-Dependent Processing Times to Minimize the Weighted Number of Tardy Jobs on a Single Machine

Directory of Open Access Journals (Sweden)

Jianbo Qian

2013-01-01

Full Text Available We consider single machine scheduling problems with learning/deterioration effects and time-dependent processing times, with due date assignment consideration, and our objective is to minimize the weighted number of tardy jobs. By reducing all versions of the problem to an assignment problem, we solve them in O(n4 time. For some important special cases, the time complexity can be improved to be O(n2 using dynamic programming techniques.

Providing Better University Personnel through Job Sharing.

Science.gov (United States)

Hutton, Clifford E.; McFarlin, Joy Simon

1982-01-01

Universities could benefit by offering more flexible part-time job opportunities such as job-sharing, following an apparent national trend in accommodating social and economic needs. Institutions have many options in scheduling and allocating tasks. Possible benefits include improved employee attitude and productivity. (MSE)

THE INFLUENCE OF HEDONIC SHOPPING MOTIVATION TO THE IMPULSE BUYING OF ONLINE-SHOPPING CONSUMER ON INSTAGRAM

OpenAIRE

Asnawati; Wahyuni S.

2018-01-01

This research aims to know the influence of Adventure Shopping, Relaxation Shopping, Value Shopping, Social Shopping and Idea Shopping variables to the variable of Impulse Buying of Online-Shopping Consumer on Instagram. The type of the research is explanatory research. The result of F-test showed that Fcount (12.829) > Ftable (2.669) which meant that research variables had influences to the Impulse Buying. With partial correlation value of 0.548, Idea Shopping variable became the dominant fa...

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.

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

Shopping Malls - ShoppingCenters

Data.gov (United States)

NSGIC Local Govt | GIS Inventory — Collected from a variety of sources both commercial and internal, this layer represents shopping center locations within Volusia County and is maintained by the...

Shop Floor Scheduling for Program Depot Maintenance Considering Stochastic Repair Needs

National Research Council Canada - National Science Library

Gemmill, Douglas

2000-01-01

.... The research resulted in the development of a new method to identify the critical path within resource-constrained project scheduling problems, heuristic search methods that improved overall project...

Female Consumers Recreational Shopping Experiences

Directory of Open Access Journals (Sweden)

Sarbjot Singh

2013-04-01

Full Text Available The study examines the core meaning of intrinsic shopping to understand their experimental aspects of recreational and leisure shopping. The study focus only on female shoppers of age group ranging from 25-30, and understand their mall experiences because this segment is newly transform into self dependent segment which have less social and familial liabilities and have enough enthusiasm to explore the world or their boundaries. The Grounded theory use for identification of recreational shopping themes which are (a seeking experiences and (b experimental shopping and each have respective sub themes. The themes are connected to the key idea that shoppers are motivated by their expectations and desires. The study uses social constructivism to find and understand the shopper meanings in real terms rather than imposing and judgment on them. The findings described the way people do recreational shopping and how shopping malls use as leisure space and become facilitators of recreational shopping activities. Females use malls to fulfill their recreational and leisure shopping experiences as this is the great way of enjoying shopping for females of small towns. In malls females not only enjoy product experiences but services experiences also which makes their shopping interesting. The way the female of this age category use malls help the marketers and retailers to understand this segment shopping patterns.

OL-DEC-MDP Model for Multiagent Online Scheduling with a Time-Dependent Probability of Success

Directory of Open Access Journals (Sweden)

Cheng Zhu