Search

The rapid population growth has resulted in ever-growing demand for healthcare services, which forces managers to use costly resources such as operating rooms effectively. The surgery-scheduling problem is a general title that is attributed to such problems as patient selection and sequencing of surgeries at the operational level, setting their start times, and assigning resources. Hospital managers usually encounter elective surgeries that can be delayed slightly and emergency surgeries whose arrivals are unexpected, and most of them need quick access to operating rooms. Reserving operating room capacity for handling incoming emergency surgeries is expensive. Moreover, emergency surgeries cannot afford long waiting times. This paper deals with the problem of surgery scheduling in the presence of emergency surgeries with a focus on balancing the efficient use of operating room capacity and responsiveness to emergency surgeries. We proposed a new algorithm for surgery scheduling with a specific operating room capacity planning and analyzed it using simulation method based on real data. This algorithm respects working hours and availability of staff and other resources in a surgical suite. [ABSTRACT FROM AUTHOR]

This paper deals with open shop scheduling to minimise total tardiness. Contrary to other scheduling problems (i.e., flow and job shops), the formulation of the open shop is given far less attention in the literature. Therefore, we intend to fulfil this gap by the presentation of four different mixed integer linear programming models. We compare the models on the basis of their complexity sizes. Furthermore, we propose two metaheuristics based on genetic algorithm and variable neighbourhood search. We exhaustively explore the effect of different operators and parameters on the performance of genetic algorithm by means of Taguchi method. Two computational experiments are conducted to evaluate the models and algorithms for performance. The first one includes small-sized instances by which the models and general performance of the algorithms are examined. The second one consists of three well-known benchmarks by which we further evaluate the algorithms. The results show the effectiveness of the proposed models and algorithms. [ABSTRACT FROM AUTHOR]

This paper addresses the general assembly line balancing problem where the simple version is enriched by considering sequence-dependent setup times between tasks. Recently, Andres et al. (Andres, C., Miralles, C., and Pastor, R., 2008. Balancing and scheduling tasks in assembly lines with sequence-dependent setup times. European Journal of Operational Research, 187, (3), 1212-1223.) proposed the type I general assembly line balancing problem with setups (GALBPS-I) and developed a mathematical model and several algorithms for solving the problem. In a similar vein, we scrutinised the GALBPS type II problem where the challenge is to find the minimum cycle time for a predefined number of work stations. To solve the problem, we develop a mathematical model and a novel simulated annealing (SA) algorithm to solve such an NP-hard problem. We then employed the Taguchi method as an optimisation technique to extensively tune different parameters of our algorithm and make the classical SA algorithm more efficient in terms of running time and solution quality. Computational results reflected the high efficiency of the SA algorithm in both aspects. [ABSTRACT FROM AUTHOR]

This paper presents a simulation-based experimental study of scheduling rules for scheduling a dynamic flexible flow line problem considering sequence-dependent setup times. A discrete-event simulation model is presented as well as eight adapted heuristic algorithms, including seven dispatching rules and one constructive heuristic, from the literature. In addition, six new proposed heuristics are implemented in the simulation model. Simulation experiments are conducted under various conditions such as setup time ratio and shop utilisation percentage. One of the proposed rules performs better for the mean flow time measure and another one performs better for the mean tardiness measure. Finally, multiple linear regression based meta-models are developed for the best performing scheduling rules. [ABSTRACT FROM AUTHOR]

This paper presents an efficient hybrid metaheuristics for scheduling jobs in a hybrid flowshop with sequence-dependent setup times. The problem is to determine a schedule that minimises the sum of earliness and tardiness of jobs. Since this problem class is NP-hard in the strong sense, there seems to be no escape from appealing to metaheuristic procedures to achieve near-optimal solutions for real life problems. This paper proposes the hybrid metaheuristic algorithm which comprises three components: an initial population generation method based on an ant colony optimisation, a simulated annealing algorithm as an evolutionary algorithm that employs certain probability to avoid becoming trapped in a local optimum, and a variable neighbourhood search which involves three local search procedures to improve the population. A design of experiments approach is employed to calibrate the parameters of the algorithm. Results of computational tests in solving 252 problems up to 100 jobs have shown that the proposed algorithm is computationally more effective in yielding solutions of better quality than the adapted random key genetic algorithm and immune algorithm presented previously. [ABSTRACT FROM AUTHOR]

Much of the research on operations scheduling problems has either ignored setup times or assumed that setup times on each machine are independent of the job sequence. Furthermore, most scheduling problems that have been discussed in the literature are under the assumption that machines are continuously available. Nevertheless, in most real-life industries a machine can be unavailable for many reasons, such as unanticipated breakdowns (stochastic unavailability), or due to scheduled preventive maintenance where the periods of unavailability are known in advance (deterministic unavailability). This paper deals with hybrid flow shop scheduling problems in which there are sequence-dependent setup times (SDSTs), and machines suffer stochastic breakdowns, to optimise objectives based on the expected makespan. With the increase in manufacturing complexity, conventional scheduling techniques for generating a reasonable manufacturing schedule have become ineffective. An immune algorithm (IA) can be used to tackle complex problems and produce a reasonable manufacturing schedule within an acceptable time. In this research, a computational method based on a clonal selection principle and an affinity maturation mechanism of the immune response is used. This paper describes how we can incorporate simulation into an immune algorithm for the scheduling of a SDST hybrid flow shop with machines that suffer stochastic breakdowns. The results obtained are analysed using a Taguchi experimental design. [ABSTRACT FROM AUTHOR]

Identical parallel machine scheduling problem with controllable processing times is investigated in this research. In such an area, our focus is mostly motivated by the adoption of just-in-time (JIT) philosophy with the objective of minimizing total weighted tardiness and earliness as well as job compressions/expansion cost simultaneously. Also the optimal set amounts of job compressions/expansion plus the job sequence are determined on each machine. It is assumed that the jobs processing times can vary within a given interval, i.e., it is permitted to compress or expand in return for compression/expansion cost. A mixed integer linear programming (MILP) model for the considered problem is firstly proposed and thereafter the optimal jobs set amounts of compression and expansion processing times in a known sequence are determined via parallel net benefit compression-net benefit expansion called PNBC- NBE heuristic. An intelligent water drop (IWD) algorithm, as a new swarm-based nature-inspired optimization one, is also adopted to solve this multi-criteria problem. A heuristic method besides three meta-heuristic algorithms is then employed to solve small- and medium- to large-size sample-generated instances. Computational results reveal that the proposed IWDNN outperforms the other techniques and is a trustable one which can solve such complicated problems with satisfactory consequences. [ABSTRACT FROM AUTHOR]

This study proposed a novel hybrid metaheuristic that hybridized the particle swarm optimization, simulated annealing and variable neighborhood search to solve the hybrid flowshop scheduling with sequence-dependent setup times (SDST). To address the realistic assumptions of the proposed problem, three additional traits were added to the scheduling problem. These include SDST, position-dependent learning effects (LEs), and the consideration of tardiness together with earliness penalties as objective function. According to the best of our knowledge, this problem has never been investigated in the hybrid flowshop. Considering position-dependent LEs, it is assumed that the learning process reflects a decrease in the process and setup times as a function of the number of repetitions of the production of a same operation in a same stage because in many realistic situations, the more time you practice, the better LE you obtain. To evaluate the performance of the suggested method, the hybrid simulated annealing metaheuristic (HSA) presented recently is investigated for comparison purposes and computational experiments are performed on standard test problems. Results show that the suggested method performs better than the HSA for various test problems. [ABSTRACT FROM AUTHOR]

This paper addresses an economic lot scheduling problem (ELSP) for manufacturing environments regarding slack costs and deteriorating items using the extended basic period approach under Power-of-Two (PoT) policy. The purpose of this research is to determine an optimal batch size for a product and minimizing total related costs to such a problem. The cost function consists of three components, namely, setup cost, holding cost includes deteriorating factor, and slack cost. The ELSP is concerned with the scheduling decision of n items and lot sizing. Avoiding schedule interference is the main problem in ELSP. The used PoT policy ensures that the replenishment cycle of each item to be integer and this task reduces potential schedule interferences. Since the ELSP is shown as an NP-hard problem, an imperialist competitive algorithm is employed to provide good solutions within reasonable computational times. Computational results show that the proposed approach can efficiently solve such complicated problems. [ABSTRACT FROM AUTHOR]

This paper deals with a scheduling problem of inbound and outbound trucks shipping incoming and outgoing product items into/out of a cross-docking system. We consider an instance of cross-docking systems in which more than one objective are taken into account: minimization of the total operation time (makespan) and minimization of the total lateness of outbound trucks. In order to deal with this problem, three multi-objective algorithms are developed as follows (based on the sub-population concept of evolutionary algorithms): sub-population genetic algorithm-II (SPGA-II), sub-population particle swarm optimization-II (SPPSO-II), and sub-population differential evolution algorithm-II (SPDE-II). In addition, to evaluate the performance of these algorithms, four measures are presented and compared with each other whose results will demonstrate that the SPPSO-II has better characteristics in comparison with other two algorithms. [ABSTRACT FROM AUTHOR]

Abstract: The importance and applicability of cross-docking systems have grown rapidly in recent years. As these systems play a key role, particularly, in distribution networks, the launch of multi-objective approaches can contribute to solve the real-world cases and problems of such systems, in which many different and even conflicting objectives are considered. Hence, this paper addresses three famous multi-objective algorithms including non-dominated sorting genetic algorithm-II (NSGA-II), strength Pareto evolutionary algorithm-II (SPEA-II), and sub-population genetic algorithm-II (SPGA-II) to solve the cross-docking scheduling problem, in which product items are unloaded from inbound trailers in the receiving dock and then are categorized and loaded onto outbound trailers in the shipping dock. Since the time aspect of such activities is so determining and crucial, objective functions are considered as the total operational time (makespan) and the total lateness of all outbound trailers. Furthermore, In order to appraise the performance of these algorithms, four criteria are proposed and compared with each other to demonstrate the strengths of each applied algorithm. [Copyright &y& Elsevier]

This paper considers the problem of scheduling n independent jobs in hybrid flow shop environment with sequence-dependent setup times to minimize the makespan and total tardiness. For the optimization problem, an algorithm namely; bi-objective heuristic (BOH) is proposed for searching Pareto-optimal frontier. The aim of the proposed algorithm is to generate a good approximation of the set of efficient solutions. The BOH procedure initiates by generating a seed sequence. Since the output results are strongly dependent on the initial solution and in order to increase the quality of output results algorithm, we have considered how the generation of seed sequence with random way and particular sequencing rules. Two methods named Euclidean distance and percent error have been proposed to compare non-dominated solution sets obtain of each seed sequence. It is perceived from these methods that the generation of seed sequence using earliest due date rule is more effective. Then, the performance of the proposed BOH is compared with a simulated annealing proposed in the literature and a VNS heuristic on a set of test problems. The data envelopment analysis is used to evaluate the performance of approximation methods. From the results obtained, it can be seen that the proposed algorithm is efficient and effective. [ABSTRACT FROM AUTHOR]

Abstract: One of the most thoroughly studied scheduling assumptions is considering that machines may not be periodically available during the production scheduling. Although many researchers have made great attempts at integrating production and preventive maintenance scheduling by different methods, some of these methods are so intricate that one cannot independently code them to achieve the same effectiveness, or some strongly utilize specific features of the original considered problem that one cannot extend to other problems. This paper intends to apply integrating methods simple, yet easily extendible to any other machine scheduling problems. The paper investigates scheduling flexible flowshops subject to periodic preventive maintenance on machines. The objective is to minimize makespan. Two metaheuristics, including genetic algorithm and artificial immune system, and some constructive heuristics are developed to tackle the problem. The performance of the algorithms is evaluated by comparing their solutions. The results of the computational experiments indicate that the artificial immune system outperforms the other methods. [ABSTRACT FROM AUTHOR]

Abstract: Dynamic job shop scheduling that considers random job arrivals and machine breakdowns is studied in this paper. Considering an event driven policy rescheduling, is triggered in response to dynamic events by variable neighborhood search (VNS). A trained artificial neural network (ANN) updates parameters of VNS at any rescheduling point. Also, a multi-objective performance measure is applied as objective function that consists of makespan and tardiness. The proposed method is compared with some common dispatching rules that have widely used in the literature for dynamic job shop scheduling problem. Results illustrate the high effectiveness and efficiency of the proposed method in a variety of shop floor conditions. [Copyright &y& Elsevier]

This paper considers group scheduling problem in hybrid flexible flow shop with sequence-dependent setup times to minimize makespan. Group scheduling problem consists of two levels, namely scheduling of groups and jobs within each group. In order to solve problems with this context, two new metaheuristics based on simulated annealing (SA) and genetic algorithm (GA) are developed. A design procedure is developed to specify and adjust significant parameters for SA- and GA-based metaheuristics. The proposed procedure is based on the response surface methodology and two types of objective function are considered to develop multiple-objective decision making model. For comparing metaheuristics, makespan and elapsed time to obtain it are considered as two response variables representing effectiveness and efficiency of algorithms. Based on obtained results in the aspect of makespan, GA-based metaheuristic is recommended for solving group scheduling problems in hybrid flexible flow shop in all sizes and for elapsed time SA-based metaheuristic has better results. [ABSTRACT FROM AUTHOR]

Abstract: Traditional scheduling problems assume that there are always infinitely many resources for delivering finished jobs to their destinations, and no time is needed for their transportation, so that finished products can be transported to customers without delay. So, for coordination of these two different activities in the implementation of a supply chain solution, we studied the problem of synchronizing production and air transportation scheduling using mathematical programming models. The overall problem is decomposed into two sub-problems, which consists of air transportation allocation problem and a single machine scheduling problem which they are considered together. We have taken into consideration different constraints and assumptions in our modeling such as special flights, delivery tardiness and no delivery tardiness. For these purposes, a variety of models have been proposed to minimize supply chain total cost which encompass transportation, makespan, delivery earliness tardiness and departure time earliness tardiness costs. [Copyright &y& Elsevier]

In this communication, we strive to apply a novel simulated annealing to consider scheduling hybrid flowshop problems to minimize both total completion time and total tardiness. To narrow the gap between the theory and the practice of the hybrid flowshop scheduling, we integrate two realistic and practical assumptions which are sequence-dependent setup and transportation times into our problem. We apply a metaheuristic based on simulated annealing (SA) which strikes a compromise between intensification and diversification mechanisms to augment the competitive performance of our proposed SA. A comprehensive calibration of different parameters and operators are done. We employ Taguchi method to select the optimum parameters with the least possible number of experiments. For the purpose of performance evaluation of our proposed algorithm, we generate a benchmark against which the adaptations of high performing algorithms in the literature are brought into comparison. Moreover, we investigate the impacts of increase of number of jobs on the performance of our algorithm. The efficiency and effectiveness of our hybrid simulated annealing are inferred from all the computational results obtained in various situations. [Copyright &y& Elsevier]

Much of the research on operations scheduling problems has ignored dynamic events in real-world environments where there are complex constraints and a variety of unexpected disruptions. Besides, while most scheduling problems which have been discussed in the literature assume that machines are incessantly available, in most real life industries a machine can be unavailable for many reasons, such as unanticipated breakdowns (stochastic unavailability), or due to a scheduled preventive maintenance where the periods of unavailability are determined in advance (deterministic unavailability). This paper describes how we can integrate simulation into genetic algorithm to the dynamic scheduling of a flexible job shop with machines that suffer stochastic breakdowns. The objectives are the minimization of two criteria, expected makespan and expected mean tardiness. An overview of the flexible job shops and scheduling under the stochastic unavailability of machines are presented. Subsequently, the details of integrating simulation into genetic algorithm are described and implemented. Consequently, problems of various sizes are used to test the performance of the proposed algorithm. The results obtained reveal that the relative performance of the algorithm for both abovementioned objectives can be affected by changing the levels of the breakdown parameters. [ABSTRACT FROM AUTHOR]

Abstract: This paper investigates integrated flexible job shop problem (FJSP) with preventive maintenance (PM) activities under the multi-objective optimization approaches. Finding compromise solutions between the production objectives and maintenance ones is under consideration. In order to carry out the maintenance activities, reliability models are employed. This paper attempts to simultaneously optimize two objectives: the minimization of the makespan for the production part and the minimization of the system unavailability for the maintenance part. For doing it so, two decisions are taken at the same time: finding the appropriate assignment of n jobs on m machines in order to minimize the makespan and deciding when to execute the PM activities in order to minimize the system unavailability. Both the maintenance activity numbers and maintenance intervals are not fixed in advance. Four multi-objective optimization methods are compared to find the Pareto-optimal front in the flexible job-shop problem case. Promising the obtained results, a benchmark with a large number of test instances (more than 4800) and meticulous care is employed. [Copyright &y& Elsevier]

Abstract: Cross-docking is an approach in inventory management which can reduce inventories, lead times and customer response time. In this strategy, products and shipments are unloaded from inbound trucks, sorted and categorized based on their characteristics, moved and loaded onto outbound trucks for delivery to demand points in a distribution network. The important fact is that, the items are stored in the inventory for a period which is primarily less than the actual time allocated to keep these items in a typical warehouse. Therefore, total cost and space requirement for inventory can be cut down. One of the most important targets in such systems is to establish coordination between the performance of inbound and outbound trucks in that these trucks can be scheduled, and the product items can be allocated to trucks effectively. This paper addresses some meta-heuristics to find the best sequence of inbound and outbound trucks, so that the objective, minimizing the total operation time called makespan, can be satisfied. Furthermore, not only the efficiency and capability of the algorithms’ parameters are assessed and analyzed by some performance measures, but also these meta-heuristics are compared with each other in order to find out the set of homogeneous algorithms among all proposed algorithms. By this analysis, it can be shown that the suitability of these meta-heuristics is quite sensible especially for the cross-docking systems with large sizes in which a high volume of inbound or outbound trucks transmit the product items. [ABSTRACT FROM AUTHOR]

Abstract: In this article, we consider non-preemptive open shops scheduling problem (OSSP) where setup times are sequence-dependent (SDST) on each machine to minimize makespan. The contributions of this article are threefold. Firstly, we incorporate a very practical assumption in our problem, SDST, which, according to Allahverdi et al. (2008) [Allahverdi, A., Ng, C. T., Cheung, T. C. E., & Kovalyov, Y. M. (2008). A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 187(3), 985–1032], no paper has ever attempted to integrate into OSSP. Secondly, we propose two new advanced metaheuristics: multi-neighborhood search simulated annealing and hybrid simulated annealing to tackle the problem at hand. Thirdly, for the first time, we adapt two well-known constructive heuristics: longest total processing time and longest total remaining processing from the literature so as to consider the case of SDSTs. We also apply genetic algorithm from the literature of OSSP to embrace the concepts of SDST. Since there is no standard SDST-OSSP benchmark, we make certain adaptations on the Taillard’s benchmark [Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64, 278–285] to include setup times. An experimental design based on foregoing benchmark is conducted to evaluate the competitiveness and robustness of our proposed algorithm against some effective algorithms in the literature. The obtained results strongly support the high performance of our proposed algorithms with respect to other well-known heuristic and metaheuristic algorithms. [Copyright &y& Elsevier]

Abstract: This paper explores scheduling a realistic variant of open shops with parallel machines per working stage. Since real production floors seldom employ a single machine for each operation, the regular open shop problem is very often in practice extended with a set of parallel machines at each stage. The purpose of duplicating machines in parallel is to either eliminate or to reduce the impact of bottleneck stages on the overall shop efficiency. The objective is to find the sequence which minimizes total completion times of jobs. We first formulate the problem as an effective mixed integer linear programming model, and then we employ memetic algorithms to solve the problem. We employ Taguchi method to evaluate the effects of different operators and parameters on the performance of memetic algorithm. To further enhance the memetic algorithm, we hybridize it with a simple form of simulated annealing as its local search engine. To assess the performance of the model and algorithms, we establish two computational experiments. The first one is small-sized instances by which the model and general performance of the algorithms are evaluated. The second one consists of large-sized instances by which we further evaluate the algorithms. [ABSTRACT FROM AUTHOR]