Search

Parallel machines scheduling problems (PMSPs) exist in the industry since most manufacturing operations aim to produce lots of similar products in a defined time period. Some incoming jobs have different sizes and due dates; plus, the production capacity, setup time, job processing time and energy requirement of each machine can be different, possibly due to distinct models and brands. In addition, jobs can be split into sublots and processed independently on any machine; and the setup times of machines also depend on job sequences. As such, the production management involving those machines becomes exceedingly complex, particularly when the problem has multiple objectives. To obtain optimum solutions, it would require complicated mathematical model along with a solver software; however, metaheuristic algorithms might be needed if a problem becomes too large. This study applied two metaheuristic algorithms, namely differential evolution (DE) and particle swarm optimization (PSO) to the tri-objective PMSP with job splitting and sequence dependent setup times (PMSP-JSSDST) in order to obtain solutions with simultaneously minimized makespan, tardiness and total energy consumption. Both algorithms were used to solve the PMSP-JSSDST instances with some small instances being run on a commercial solver for control purpose. Then, the performances of DE and PSO were compared using hypervolume indicator. The results showed that the performances of both algorithms almost matched to those of the commercial solver for the small instances. And for the large instances, DE algorithm offers superior performances compared to those of PSO algorithm, having significantly higher values of the hypervolume indicator. [ABSTRACT FROM AUTHOR]

Parallel machines scheduling problems (PMSPs) exist in the industry since most manufacturing operations aim to produce lots of similar products in a defined time period. Some incoming jobs have different sizes and due dates; plus, the production capacity, setup time, job processing time and energy requirement of each machine can be different, possibly due to distinct models and brands. In addition, jobs can be split into sublots and processed independently on any machine; and the setup times of machines also depend on job sequences. As such, the production management involving those machines becomes exceedingly complex, particularly when the problem has multiple objectives. To obtain optimum solutions, it would require complicated mathematical model along with a solver software; however, metaheuristic algorithms might be needed if a problem becomes too large. This study applied two metaheuristic algorithms, namely differential evolution (DE) and particle swarm optimization (PSO) to the tri-objective PMSP with job splitting and sequence dependent setup times (PMSP-JSSDST) in order to obtain solutions with simultaneously minimized makespan, tardiness and total energy consumption. Both algorithms were used to solve the PMSP-JSSDST instances with some small instances being run on a commercial solver for control purpose. Then, the performances of DE and PSO were compared using hypervolume indicator. The results showed that the performances of both algorithms almost matched to those of the commercial solver for the small instances. And for the large instances, DE algorithm offers superior performances compared to those of PSO algorithm, having significantly higher values of the hypervolume indicator.

Multiple production lines can work together to efficiently manufacture certain products. Thus, when capacity is insufficient, it is necessary to decide whether to develop new production lines to ensure the timely completion of all orders. For example, running a new production line for a small number of orders is not cost-effective. Therefore, decision-making involves choosing between paying tardiness costs for a few orders, abandoning some orders, or developing new production lines to maximize efficiency. Additionally, the timely transportation of completed orders is crucial and depends on vehicle usage efficiency. From a transportation perspective, fully loading vehicles is the most efficient, but this may impact the timeliness of orders, leading to potential tardiness costs. By comprehensively considering these aspects, a multi-machine production model is constructed that incorporates transportation batch sequences and uses heuristic algorithms to solve the problem. Finally, designed case examples validate the effectiveness of the model and algorithm. [ABSTRACT FROM AUTHOR]

The problem studied in this paper is elective surgery scheduling, with resource constraints in each of the three following stages: preoperative, perioperative, and postoperative stages. With the integrated availability of hospital beds in wards and operating rooms, the aim is to determine operation start times of surgeries and allocate the hospital beds to patients while getting patients treated as soon as possible. This task is crucial in providing timely treatments for the patients while ensuring the hospital’s resource utilization balance. For the problem, we first formulate it as mixed-integer programming, which is NP-complete. Then, we propose several heuristics to overcome the long computation time. To make the solution better, we also propose improved algorithms. Finally, we conduct a series of numerical studies to illustrate the efficiency of our proposed algorithms and examine the impact of the number of jobs, beds, and surgery blocks on the performance measure. Computational experiments showed the superior performance of our heuristics in makespan. [ABSTRACT FROM AUTHOR]

We consider parallel-machine scheduling with identical machine resource capacity limits and DeJong's learning effect. Each job has a resource consumption requirement and a normal processing time. The actual processing time of a job is a function of its normal processing time, subject to DeJong's learning effect, while the resource consumption of a job is a function of its actual processing time. Each machine has the same resource capacity limit. The objective is to maximise the minimum machine load. Considering three resource consumption functions, namely, linear, concave, and convex, we show that all three scheduling models are NP-hard and propose two approximation algorithms for the models and analyse their worst-case ratios. [ABSTRACT FROM AUTHOR]

Multiple production lines can work together to efficiently manufacture certain products. Thus, when capacity is insufficient, it is necessary to decide whether to develop new production lines to ensure the timely completion of all orders. For example, running a new production line for a small number of orders is not cost-effective. Therefore, decision-making involves choosing between paying tardiness costs for a few orders, abandoning some orders, or developing new production lines to maximize efficiency. Additionally, the timely transportation of completed orders is crucial and depends on vehicle usage efficiency. From a transportation perspective, fully loading vehicles is the most efficient, but this may impact the timeliness of orders, leading to potential tardiness costs. By comprehensively considering these aspects, a multi-machine production model is constructed that incorporates transportation batch sequences and uses heuristic algorithms to solve the problem. Finally, designed case examples validate the effectiveness of the model and algorithm.

This paper elucidates an algorithmic methodology aimed at optimizing the scheduling on parallel machines to minimize the total Makespan and bolster preventive protections. The scenario under consideration involves a predetermined set of 'c' jobs, processed on 'd' parallel machines, with the stipulation of non-preemptive task execution and a single job assignment per machine at any given time. The context predominantly revolves around production planning scenarios with fixed delivery dates. A mixed-integer programming approach is leveraged in the study to attain minimization of the Makespan, a key focus of this analysis. The problem at hand is tackled effectively through the application of both Genetic Algorithm (GA) and CPLEX algorithmic strategies. A thorough numerical analysis follows, aimed at evaluating the performance measures. The findings of this analysis promise to shed significant light on the optimization of scheduling and preventive measures in parallel machines, thereby paving the way for future research in this sphere. [ABSTRACT FROM AUTHOR]

Given the challenges of manufacturing resource sharing and competition in the modern manufacturing industry, the coordinated scheduling problem of parallel machine production and transportation is investigated. The problem takes into account the coordination of production and transportation before production as well as the disparities in machine spatial position and performance. A non-cooperative game model is established, considering the competition and self-interest behavior of jobs from different customers for machine resources. The job from different customers is mapped to the players in the game model, the corresponding optional processing machine and location are mapped to the strategy set, and the makespan of the job is mapped to the payoff. Then the solution of the scheduling model is transformed into the Nash equilibrium of the non-cooperative game model. A Nash equilibrium solution algorithm based on the genetic algorithm (NEGA) is designed, and the effective solution of approximate Nash equilibrium for the game model is realized. The fitness function, single-point crossover operator, and mutation operator are derived from the non-cooperative game model’s characteristics and the definition of Nash equilibrium. Rules are also designed to avoid the generation of invalid offspring chromosomes. The effectiveness of the proposed algorithm is demonstrated through numerical experiments of various sizes. Compared with other algorithms such as heuristic algorithms (FCFS, SPT, and LPT), the simulated annealing algorithm (SA), and the particle swarm optimization algorithm (PSO), experimental results show that the proposed NE-GA algorithm has obvious performance advantages. [ABSTRACT FROM AUTHOR]

In this paper, we design the first streaming algorithms for the problem of multitasking scheduling on parallel machines with shared processing. In one pass, our streaming approximation schemes can provide an approximate value of the optimal makespan. If the jobs can be read in two passes, the algorithm can find the schedule with the approximate value. This work not only provides an algorithmic big data solution for the studied problem, but also gives an insight into the design of streaming algorithms for other problems in the area of scheduling. [ABSTRACT FROM AUTHOR]

In this paper, an identical parallel machine scheduling problem with step-deteriorating jobs is considered to minimize the weighted sum of tardiness cost and extra energy consumption cost. In particular, the actual processing time of a job is assumed to be a step function of its starting time and its deteriorating threshold. When the starting time of a job is later than its deteriorating threshold, the job faces two choices: (1) maintaining its status in holding equipment and being processed with a base processing time and (2) consuming an extra penalty time to finish its processing. The two work patterns need different amounts of energy consumption. To implement energy-efficient scheduling, the selection of the pre-processing patterns must be carefully considered. In this paper, a mixed integer linear programming (MILP) model is proposed to minimize the total tardiness cost and the extra energy cost. Decomposition approaches based on logic-based Benders decomposition (LBBD) are developed by reformulating the studied problem into a master problem and some independent sub-problems. The master problem is relaxed by only making assignment decisions. The sub-problems are to find optimal schedules in the job-to-machine assignments given by the master problem. Moreover, MILP and heuristic based on Tabu search are used to solve the sub-problems. To evaluate the performance of our methods, three groups of test instances were generated inspired by both real-world applications and benchmarks from the literature. The computational results demonstrate that the proposed decomposition approaches can compute competitive schedules for medium- and large-size problems in terms of solution quality. In particular, the LBBD with Tabu search performs the best among the suggested four methods. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Sport Sciences / Magallat ulum Al-Riyadat is the property of Republic of Iraq Ministry of Higher Education & Scientific Research (MOHESR) and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

In this paper, the parallel machine scheduling problem with DeJong's learning effect, is addressed. The objective function to be minimized is the makespan. This problem is proofed to be NP-Hard in the strong sense. This is the challenging theoretical side of the studied problem. Furthermore, several real-life situations in manufacturing and computer science are modeled using the current problem. Several algorithms intended to solve the studied problem within a reasonable computing time are proposed in literature. Among these algorithms the exact methods, which failed to solve the studied problem to optimality even for small size instances. In this paper several new heuristics and meta-heuristics are proposed. These heuristics are classified into three types. The first type is based on Longest Processing Time (LPT) rule. The innovation is the modification of the LPT rule in a way to cope efficiently with the learning effect concept, by randomizing the selection of the next scheduled job. The second type of heuristics, is taking advantage of an exact Branch and Bound algorithm, developed originally for the classical parallel machine scheduling problem. The contribution for this kind of heuristics is lying in the modification of the processing time values, according to a prefixed selected functions. The third type of methods is based in an adaptation of the Genetic Algorithm to the learning effect concept. This adaptation consists in enlarging the area of selection of the parameters values. To assess the performance and the efficiency of the proposed heuristics, a newly developed lower bound is proposed. This lower bound is based on a relaxation of the studied problem, which allows to obtain a minimum cost flow problem. Finally, an extensive experimental study is conducted over a benchmark test problems. The obtained results provide strong evidence that the proposed procedures outperform the earlier existing ones. • Modeling the learning effect in parallel machine scheduling problem. • Development of dispatching rules based heuristics. • Development of heuristics based on the resolution of NP-Hard problems. • Development of new tight lower bounds based on the maximum allowed position. • Caring out an extensive experimental study that confirms the efficiency of the proposed procedures. [ABSTRACT FROM AUTHOR]

This study considers the problem of job scheduling on unrelated parallel machines. A multi-objective multi-point simulated annealing (MOMSA) algorithm was proposed for solving this problem by simultaneously minimising makespan, total weighted completion time and total weighted tardiness. To assess the performance of the proposed heuristic and compare it with that of several benchmark heuristics, the obtained sets of non-dominated solutions were assessed using four multi-objective performance indicators. The computational results demonstrated that the proposed heuristic markedly outperformed the benchmark heuristics in terms of the four performance indicators. The proposed MOMSA algorithm can provide a new benchmark for future research related to the unrelated parallel machine scheduling problem addressed in this study. [ABSTRACT FROM PUBLISHER]

Thin‐film transistor liquid‐crystal displays (TFT‐LCDs) have gradually replaced cathode‐ray tubes because of their compact size and efficient use of power. Since product lifecycles are shortening, consumers require instant order delivery, which affects fluctuations in supply and demand. As various product types in the LCD industry exist, manufacturing time has to be reduced to satisfy consumer demand. This study investigates the dispatching of parallel machines for TFT‐LCD manufacturing. Since customers' orders and suppliers' deliveries vary significantly and the manual adjustment of production planning is time consuming, an appropriate production planning and scheduling system is necessary. Consequently, this study develops a genetic algorithm to solve the scheduling problem of unrelated parallel machines, taking account of multiple performance measurement indicators. We also adopt LINGO to solve the problem and compare the obtained solution quality and computation time of the two approaches to justify the effectiveness of the proposed genetic algorithm. [ABSTRACT FROM AUTHOR]

The concept of parallel machine framework as a solution to the challenges of the complexity of intelligent machines was proposed in this paper.The ACP theory was incorporated into intelligent machine field,and a virtual-real interactive pattern was formed in the control and management of machine.The parallel machine concept is composed of the real machine and corresponding software-defined virtual ones,and through which the functionality including describing,predicting and prescription can be achieved.Finally,relevant technologies and potential applications of parallel machine were discussed.

This paper studies an integrated scheduling problem which consists of both production and transportation stages. Jobs are processed on a set of parallel batch-processing machines in the production stage, and then transported to a target customer in the transportation stage. The aim is to find an optimal integrated production and transportation schedule with the objective to minimize the weighted sum of total delivery time and total transportation cost with a relative preference α. A 0-1 mixed integer programming model is then constructed. To solve the proposed model, which is NP-hard, a developed GA is proposed to produce near-optimal solutions for large-size instances. Computational experiments on 720 instances with up to 150 jobs and 5 parallel batch-processing machines show the effectiveness and efficiency of the developed GA.

In this paper, parallel machine scheduling problem is considered under due date assignment, earliness, weighted number of tardy jobs, facilities costs and shipping products by limited vehicle capacity. The orders of the customer are presented with a due date. Each order is scheduled and assigned to one of the machines according to due date, delay weight and penalty of increasing of due date and shipped in the batch. The problem is known as NP-hardness, therefore a Genetic Algorithm (GA) is proposed to solve the problem. The results are also compared with the CPLEX solver in the GAMS. Finally, sensitivity analysis for the problem parameters is performed in relation to the objective function. The results showed a direct relationship between objective function with the weighted tardiness and processing time, also an inverse relationship with the number of machines and vehicle capacity. [ABSTRACT FROM AUTHOR]

Traditional scheduling problems are usually focused on minimising time-based objectives. In this paper, we have examined the problems in single and parallel machine scheduling. We have incorporated cash management into the objective function of these problems. It is assumed that processing a given job involves incurring a total cost and receiving a total revenue. Each job also has its own temporal pattern of cost incurring and revenue receiving. Nonetheless, the total cost/revenue of processing a job is assumed to be incurred/received during its processing and not beyond it. We have defined five new objectives: (i) maximising average available cash; (ii) minimising revenue-cost duration; (iii) minimising average cash deficiency; (iv) minimising maximum cash deficiency; and (v) maximising minimum available cash. Based on the results achieved in this paper, the above patterns do not affect the optimal scheduling policy in regards to the first two objectives. For single machine models, all except one of the problems are solved in polynomial time. For parallel machines, all models are proved to be NP-hard. Some of the NP-hard models are convertible to equivalent traditional ones. [ABSTRACT FROM AUTHOR]

Hybrid flow shop scheduling problems (HFSP), one of popular research topics in the field of shop scheduling, several alternative parallel machines in all or part of stages of the flow-shop were introduced, and production capacity and flexibility of the shop were improved. Hybrid flow-shop scheduling methods were reviewed according to the number of stages and machine characteristics herein. Related extension problems in background of practical engineering were systematically summarized, and the existing problems and possible solutions were pointed out. Combined with development trend of operations research, application prospect of HFSP in emerging fields was discussed. Finally, some possible research directions in future were pointed out. [ABSTRACT FROM AUTHOR]

Production systems are subject to machine deterioration and resource consumption constraints. The deterioration increases the processing time which leads to an increase in resource consumption. In this study, we investigate and model the behavior of a parallel machine scheduling problem with respect to the processing time. The machine is subject to deterioration and includes two resource consumption constraints. The first resource R1 controls the processing time so that additional amounts of R1 decrease the processing time. The second R2 is controlled by the actual processing time so that R2 consumption is a linear function of the actual processing time. The increment of R1 consumption leads to processing time and so R2 decrement. Solving this problem consists in finding the optimal schedule that will minimize both makespan and resources cost. This paper provides a mathematical programming model. In fact, due to the deterioration effect and the two resource consumptions, solving such a problem may be very difficult and requires a large computational time. In this paper, we introduce a multi objective simulated annealing (MOSA) in order to solve the combinatorial optimization problem related to finding the best combination (machine, job, position, R1). Literally the best jobs assignment and resources allocation so that makespan and resources cost are minimized. In order to improve the quality of the results we also developed a 2-steps algorithm by decomposing the original problem into two sub problems: an assignment problem and a resources allocation problem. Some simulations were performed to analyze the performances of the two algorithms. The results show that the 2-steps algorithm is very efficient and outperforms MOSA. [ABSTRACT FROM AUTHOR]

This paper investigates unrelated parallel machine scheduling problems where the objectives are to minimize total weighted sum of earliness/tardiness costs. Three different metaheuristic algorithms are compared with others to determine what kind (swarm intelligence based, evolutionary or single solution) of metaheuristics is effective to solve these problems. In this study, artificial bee colony (ABC), genetic algorithm and simulated annealing algorithm are chosen as swarm intelligence based algorithm, evolutionary algorithm and single solution algorithm. All proposed algorithms are created without modification in order to determine effectiveness of these metaheuristics. Experimental results show that ABC outperforms its opponents in view of solution quality as swarm intelligence based metaheuristic algorithm. [ABSTRACT FROM AUTHOR]

The block erection problem is defined as a parallel machine scheduling problem with precedence constraints and machine eligibility restrictions. A heuristic algorithm combined of the largest total amount of processing first rule (LTAP) and the enhanced smallest machine load first rule (ESML) is proposed to minimise makespan for the block erection in a shipyard. Finally, four lower bounds and the percentage of the reduced makespan compared with the current solutions are defined to evaluate the performance of the proposed algorithm. The experiments are performed on data selected from a shipbuilding company, and the results demonstrate that the presented algorithm can effectively find a good solution to minimise the makespan of the block erection problem. [ABSTRACT FROM AUTHOR]

The present research addresses the single transportation robot used to alleviate problems of robotic cell scheduling of the machines. For the purpose of minimizing the make-span, a model of mixed-integer linear programming (MILP) has been suggested. Since the inefficiency exists in NP-hard, a decomposition algorithm posed by Bender was utilized to alleviate the problem in real life situations. The proposed algorithm can be regarded as an efficient attempt to apply optimality Bender’s cuts regarding the problem of parallel machine robotic cell scheduling in order to reach precise resolutions for medium and big sized examples. The numerical analyses have demonstrated the efficiency of the proposed solving approach.

This study focuses on identical parallel machine scheduling of jobs with deteriorating processing times and rate-modifying activities. We consider non linearly increasing processing times of jobs based on their position assignment. Rate modifying activities are also considered to recover the increase in processing times of jobs due to deterioration. We also propose heuristics algorithms that rely on ant colony optimization and simulated annealing algorithms to solve the problem with multiple RMAs in a reasonable amount of time. Finally, we show that ant colony optimization algorithm generates close optimal solutions and superior results than simulated annealing algorithm.

A parallel-machine scheduling problem with preventive maintenance is studied in the paper. Because of the existence of indeterminacy phenomenon, the processing and maintenance time are assume to be uncertain variables. To address these uncertain parameters, two pessimistic value mathematical programming models are developed and the equivalence is proved. The worst-case bound of longest processing time (LPT) rule for the problem under an uncertain environment is obtained. To solve this problem effectively, an improved LPT rule is proposed according to the result of the theoretical analysis. Finally, numerical experiments show that the improved LPT outperforms the LPT in improving the quality of the optimal value and has a less relative error than that of the LPT. [ABSTRACT FROM AUTHOR]

Facility layout is vital to save operational cost and enhance production efficiency. Multirow layout is a common pattern in practical manufacturing environment. Although parallel machines are frequently implemented in practice to enhance productivity, there lacks any in-depth study on multirow layout problem with parallel machines. In this paper, its mathematical programming formulation is established to minimize material flow cost. A three-stage approach is proposed to solve it. First, a Monte Carlo heuristic is devised to optimize the sequence of machines on multiple rows. Second, a linear program is used to determine the optimal exact location of each machine. Finally, an exchange heuristic is adopted to reassign material flows among parallel machines in different machine groups. An iterative optimization strategy is suggested to execute the three stages repeatedly to improve the solution quality. This approach is applied to a number of problem instances and compared against others. The experimental results show that it is able to effectively solve this new problem and significantly decrease material flow cost. Note to Practitioners—Multirow layout is common in practical manufacturing systems in which parallel machines are often used to improve productivity, shorten production time, and guarantee some flexibility. This paper studies a multirow parallel machine layout problem that involves machine groups, each of which contains parallel machines. Solving it is to locate all machines at multiple parallel rows to minimize material flow cost. It is challenging because one needs to decompose material flows and determine exact locations of machines simultaneously. A three-stage approach is proposed to do so. It is applied to many problem instances. The results demonstrate that it works well for such layout problems with parallel machines. [ABSTRACT FROM AUTHOR]

In this paper, we assumed that machines have different energy consumptions or maintenance costs in the context of green manufacturing, and tried to solve the parallel machine scheduling problem under the condition of cost constraints. To minimize the maximum lateness, an integer programming model MIP was established and an improved algorithm for EDD(earliest due date firstly) — MEDD was designed. Then the feasibility of the MEDD algorithm was proved under the condition of cost constraints,and the worst error bound of the algorithm was also analyzed theoretically. By giving an example, we proved the feasibility of the algorithm. And its performance was verified by a large number of random data experiments. For a small scale, the solution of MEDD was compared with the exact solution of MIP. While the exact solution of MIP is too hard to obtain when it comes to a large scale, the optimal value of MLP of the linear programming relaxation model corresponding to MIP was taken as the lower bound to measure the solution of MEDD algorithm. All these results showed a great effectiveness of MEDD algorithm. [ABSTRACT FROM AUTHOR]