309 results on '"Batch scheduling"'
Search Results
2. A hybrid discrete differential evolution – genetic algorithm approach with a new batch formation mechanism for parallel batch scheduling considering batch delivery.
- Author
-
Kucukkoc, Ibrahim, Aydin Keskin, Gulsen, Karaoglan, Aslan Deniz, and Karadag, Sevgi
- Subjects
DIFFERENTIAL evolution ,GENETIC algorithms ,LINEAR programming ,FROZEN foods ,JOB shops ,PRODUCTION planning - Abstract
Scheduling is an important decision-making problem in production planning and the resulting decisions have a direct impact on reducing waste, including energy and idle capacity. Batch scheduling problems occur in various industries from automotive to food and energy. This paper introduces the parallel p-batch scheduling problem with batch delivery, content-dependent loading/unloading times and energy-aware objective function. The problem has been motivated by a real system used for freezing products in a food processing company. A mixed-integer linear programming model (MILP) has been developed and explained through a numerical example. As it is not practical to solve large-size instances via a mathematical model, the discrete differential evolution algorithm has been improved (iDDE) and hybridised with the genetic algorithm (GA). A release-oriented vector generation procedure and a heuristic batch formation mechanism have been developed to efficiently solve the problem. The performance of the proposed approach (iDDEGA) has been compared with CPLEX, iDDE and GA through a comprehensive computational study. A case study was conducted based on real data collected from the freezing process of the company, which also verified the practical use and advantages of the proposed methodology. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
3. Population-based iterated local search for batch scheduling on parallel machines with incompatible job families, release dates, and tardiness penalties: Population-based iterated local search...: J. M. Medeiros et al.
- Author
-
Medeiros, José Maurício Fernandes, Subramanian, Anand, and Queiroga, Eduardo
- Abstract
This work addresses a parallel batch machine scheduling problem subject to tardiness penalties, release dates, and incompatible job families. In this environment, jobs of the same family are partitioned into batches and each batch is assigned to a machine. The objective is to determine the sequence in which the batches will be processed on each machine with a view of minimizing the total weighted tardiness. To solve the problem, we propose a population-based iterated local search algorithm that makes use of multiple neighborhood structures and an efficient perturbation mechanism. The algorithm also incorporates the time window decomposition (TWD) heuristic to generate the initial population and employs population control strategies aiming to promote individuals with higher fitness by combining the total weighted tardiness with the contribution to the diversity of the population. Extensive computational experiments were conducted on 4860 benchmark instances and the results obtained compare very favorably with those found by the best existing algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2025
- Full Text
- View/download PDF
4. Serial batching to minimize the weighted number of tardy jobs.
- Author
-
Hermelin, Danny, Mnich, Matthias, and Omlor, Simon
- Subjects
SETUP time ,MULTIVARIATE analysis ,BACKPACKS ,INTEGERS ,SCHEDULING ,ECONOMIC lot size - Abstract
The 1 | s-batch (∞) , r j | ∑ w j U j scheduling problem takes as input a batch setup time Δ and a set of n jobs, each having a processing time, a release date, a weight, and a due date; the task is to find a sequence of batches that minimizes the weighted number of tardy jobs. This problem was introduced by Hochbaum and Landy (Oper Res Lett 16(2):79–86, 1994); as a wide generalization of Knapsack, it is NP -hard. In this work, we provide a multivariate complexity analysis of the 1 | s-batch (∞) , r j | ∑ w j U j problem with respect to several natural parameters. That is, we establish a classification into fixed-parameter tractable and W [ 1 ] -hard problems, for parameter combinations of (i) # p = number of distinct processing times, (ii) # w = number of distinct weights, (iii) # d = number of distinct due dates, (iv) # r = number of distinct release dates. Thereby, we significantly extend the work of Hermelin et al. (Ann Oper Res 298:271–287, 2018) who analyzed the parameterized complexity of the non-batch variant of this problem without release dates. As one of our key results, we prove that 1 | s-batch (∞) , r j | ∑ w j U j is W [ 1 ] -hard parameterized by the number of distinct processing times and distinct due dates. To the best of our knowledge, these are the first parameterized intractability results for scheduling problems with few distinct processing times. Further, we show that 1 | s-batch (∞) , r j | ∑ w j U j is fixed-parameter tractable parameterized by # d + # p + # r , and parameterized by # d + # w if there is just a single release date. Both results hold even if the number of jobs per batch is limited by some integer b. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
5. 面向部分工序无序加工的柔性作业车间 批量调度方法.
- Author
-
柳宁, 华天标, 王高, and 陈法明
- Abstract
Copyright of Journal of South China University of Technology (Natural Science Edition) is the property of South China University of Technology 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.)
- Published
- 2024
- Full Text
- View/download PDF
6. 带有动态到达工件的分布式柔性作业 车间调度问题研究.
- Author
-
张洪亮, 童 超, and 丁倩兰
- Abstract
Copyright of Journal of Anhui University of Technology (Natural Science) is the property of Anhui University of Technology 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.)
- Published
- 2024
- Full Text
- View/download PDF
7. Machine learning application in batch scheduling for multi-product pipelines: A review.
- Author
-
Renfu Tu, Hao Zhang, Bin Xu, Xiaoyin Huang, Yiyuan Che, Jian Du, Chang Wang, Rui Qiu, and Yongtu Liang
- Subjects
PIPELINES ,MACHINE learning ,COMPUTER scheduling ,ALGORITHMS ,PETROLEUM production - Abstract
Batch scheduling is a crucial part of pipeline enterprise operation management, especially in the context of market-oriented operation. It involves 3 main tasks: quickly preparing batch plans, accurately tracking interface movement, and operation condition in real time. Normally, the completion of multi-product pipeline batch scheduling depends on simulation models or optimization models and corresponding conventional solving algorithm. However, this approach becomes inefficient when applied to large-scale systems. The rapid development of machine learning has brought new ideas to batch scheduling research. This paper first reviews the current state of batch scheduling technology, and suggests that applying machine learning to it is a promising development direction. Then, we summarize the progress of machine learning applications in batch planning, interface movement tracking, and operational condition monitoring, and point out their limitations. Finally, considering the separation of refined oil production, transportation, and sales processes, 5 recommendations are put forward: oil supply and demand prediction and pipeline capacity prediction, batch planning, batch interface movement tracking, mixed oil development monitoring, and pipeline operation condition identification. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
8. Two-agent scheduling on mixed batch machines to minimise the total weighted makespan.
- Author
-
Fan, Guo-Qiang, Wang, Jun-Qiang, and Liu, Zhixin
- Subjects
BATCH processing ,PRODUCTION scheduling ,APPROXIMATION algorithms ,SCHEDULING ,MACHINERY - Abstract
This paper studies a two-agent scheduling problem on mixed batch machines in parallel. A mixed batch machine can process several jobs simultaneously as a batch, as long as the number of jobs in the batch does not exceed the machine capacity. The processing time of a mixed batch is the weighted sum of the maximum processing time and the total processing time of jobs in the batch. The objective is to minimise the weighted sum of two agents' makespans. We present four approximation algorithms based on two strategies: the machine-centric strategy and the agent-centric strategy. For each strategy, a full batch longest processing time (FBLPT) rule and a longest processing time greedy (LPTG) rule are used. We conduct theoretical analyses based on the worst-case performance ratio to provide the provable guarantees on the performances of the algorithms, and simulation analyses based on randomly generated instances to evaluate the average performances of the algorithms. Furthermore, we verify the consistency between the theoretical and simulation results. The algorithms using agent-centric strategy perform better than ones using machine-centric strategy. Finally, we provide managerial insights for the problem by analysing the technological parameters of batches, importance of agents, and demand seasonality. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
9. ULD Build-Up Scheduling with Logic-Based Benders Decomposition
- Author
-
Euler, Ricardo, Borndörfer, Ralf, Puchert, Christian, Takkula, Tuomo, Goos, Gerhard, Series Editor, Hartmanis, Juris, Founding Editor, van Leeuwen, Jan, Series Editor, Hutchison, David, Editorial Board Member, Kanade, Takeo, Editorial Board Member, Kittler, Josef, Editorial Board Member, Kleinberg, Jon M., Editorial Board Member, Kobsa, Alfred, Series Editor, Mattern, Friedemann, Editorial Board Member, Mitchell, John C., Editorial Board Member, Naor, Moni, Editorial Board Member, Nierstrasz, Oscar, Series Editor, Pandu Rangan, C., Editorial Board Member, Sudan, Madhu, Series Editor, Terzopoulos, Demetri, Editorial Board Member, Tygar, Doug, Editorial Board Member, Weikum, Gerhard, Series Editor, Vardi, Moshe Y, Series Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, and Dilkina, Bistra, editor
- Published
- 2024
- Full Text
- View/download PDF
10. A Two-Machine Flow Shop Batch Scheduling Model to Minimize Total Actual Flow Time.
- Author
-
Yusriski, Rinto, Nasution, Andri Rachmat Kumalasian, Lukas, Wijayanti, Linda, and Octaviani, Sandra
- Subjects
- *
FLOW shop scheduling , *FLOW shops , *MANUFACTURING processes , *RAW materials - Abstract
This study introduces a scheduling model for a two-machine flow shop batch system to minimize the actual flow time. In this system, two machines are responsible for processing raw materials and producing finished products, with a single bottleneck machine. The entity overseeing the manufacturing process organizes demand units into batches, ensures the accurate and timely arrival of raw materials, and delivers all finished products punctually to meet an expected due date. The study addresses crucial challenges, including determining the optimal number of batches, sizes, and sequences to achieve the specified objective. The analysis adopted an algorithm grounded in the Lagrange relaxation method to tackle these challenges. Moreover, the algorithm is operated by identifying the bottleneck machine as a scheduling reference and determining the appropriate number of batches and sizes. The analysis showed the efficacy of the developed algorithm by using Johnson's rule for making batch sequence decisions through numerical experiments conducted across 1000 cases. The results showed a 1.44% to 4.43% improvement in efficiency compared to previous research, accompanied by a 2 to 8 times reduction in computational time. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
11. 2DPChain: Orchestrating Transactions in Order-Execute Blockchain to Exploit Intra-batch and Inter-batch Parallelism
- Author
-
Shi, Jianfeng, Wu, Heng, Liu, Wang, Gao, Heran, Zhang, Wenbo, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Monti, Flavia, editor, Rinderle-Ma, Stefanie, editor, Ruiz Cortés, Antonio, editor, Zheng, Zibin, editor, and Mecella, Massimo, editor
- Published
- 2023
- Full Text
- View/download PDF
12. Improved Analysis of Two Algorithms for Min-Weighted Sum Bin Packing
- Author
-
Sagnol, Guillaume, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Hsieh, Sun-Yuan, editor, Hung, Ling-Ju, editor, and Lee, Chia-Wei, editor
- Published
- 2023
- Full Text
- View/download PDF
13. Encoding for Reinforcement Learning Driven Scheduling
- Author
-
Li, Boyang, Fan, Yuping, Papka, Michael E., Lan, Zhiling, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Klusáček, Dalibor, editor, Julita, Corbalán, editor, and Rodrigo, Gonzalo P., editor
- Published
- 2023
- Full Text
- View/download PDF
14. Exact Algorithm for Batch Scheduling on Unrelated Machine.
- Author
-
Allaoua, Hemmak
- Published
- 2023
- Full Text
- View/download PDF
15. A Batch Scheduling Model for a Three-Stage Flowshop with Batch Processor and Heterogeneous Job Processor to Minimize Total Actual Flowtime
- Author
-
Suryadhini, Pratya Poeri, Sukoyo, Suprayogi, Halim, Abdul Hakim, Kuo, Yong-Hong, editor, Fu, Yelin, editor, Chen, Peng-Chu, editor, Or, Calvin Ka-lun, editor, Huang, George G., editor, and Wang, Junwei, editor
- Published
- 2022
- Full Text
- View/download PDF
16. Two-stage hybrid flow shop batching and lot streaming with variable sublots and sequence-dependent setups.
- Author
-
Wang, Shasha, Kurz, Mary, Mason, Scott Jennings, and Rashidi, Eghbal
- Subjects
FLOW shops ,SETUP time ,PAINT manufacturing ,EMULSION paint ,FACTORY orders ,MACHINE shops ,BATCH processing - Abstract
A paint manufacturing firm's customers typically place orders for two or more products simultaneously. Each product belongs to a family that denotes batching compatibility during manufacturing. Further, products can be split into several sublots to allow overlapping production in a two-stage hybrid flow shop wherein various identical, capacitated machines operate in parallel at each stage. We present a mixed-integer linear program (MILP) for this integrated batching and lot streaming problem with variable sublots, incompatible job families, and sequence-dependent setup times. The model determines the number and size of sublots for each product and the production sequencing for each sublot such that the total weighted completion time is minimised. To promote practical implementation, we develop and evaluate heuristics to efficiently solve this problem. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
17. Single Item Batch-scheduling Model for a Flow Shop with m Batch-processing Machines to Minimize Total Actual Flow Time
- Author
-
Abdul Hakim Halim, Nita Puspita Anugrawati Hidayat, and Wisnu Aribowo
- Subjects
batch processor ,batch scheduling ,flow shop ,total actual flow time ,Technology ,Technology (General) ,T1-995 - Abstract
We propose a batch-scheduling model to minimize the total actual flow time (TAF) of parts to be processed in a flow shop consisting of m batch-processing machines. A batch-processing machine (BPM) is a machine that can process several parts at once, and the TAF of parts is the total interval time from the arrival times to the corresponding due date. In the real world, shop floors often have production lines with BPMs and multistage processes. We were motivated by a real problem in the aircraft industry and aimed to simultaneously satisfy the due dates and minimize the total time that parts spend in the shop. The problem was formulated as a mathematical model and solved using a proposed algorithm. The batch-scheduling problem is divided into batching and scheduling subproblems. The solution has been obtained by adopting backward scheduling. This paper develops a new model of flow shop scheduling problem for the shop with batch processing machines and the heuristic solution method. It provides numerical examples and their results to demonstrate the effectiveness of the proposed algorithm for solving the problem.
- Published
- 2022
- Full Text
- View/download PDF
18. 基于多目标差分进化算法的机加工柔性作业车间调度.
- Author
-
程 强, 高元杰, 初红艳, 张彩霞, and 刘志峰
- Subjects
PRODUCTION scheduling ,DIFFERENTIAL evolution ,LOADERS (Machines) ,ENERGY consumption ,MACHINING ,PROPORTIONAL navigation ,TRAIN schedules - Abstract
Copyright of Journal of Beijing University of Technology is the property of Journal of Beijing University of Technology, Editorial Department 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.)
- Published
- 2023
- Full Text
- View/download PDF
19. MILP performance improvement strategies for short-term batch production scheduling: a chemical industry use case
- Author
-
Sascha Kunath, Mathias Kühn, Michael Völker, Thorsten Schmidt, Phillip Rühl, and Gennadij Heidel
- Subjects
Mixed integer linear programming ,Batch scheduling ,Multi-product plant ,Multi-stage ,Parallel units ,MILP performance ,Science ,Technology - Abstract
Abstract This paper presents the development and mathematical implementation of a production scheduling model utilizing mixed-integer linear programming (MILP). A simplified model of a real-world multi-product batch plant constitutes the basis. The paper shows practical extensions to the model, resulting in a digital twin of the plant. Apart from sequential arrangement, the final model contains maintenance periods, campaign planning and storage constraints to a limited extend. To tackle weak computational performance and missing model features, a condensed mathematical formulation is introduced at first. After stating that these measures do not suffice for applicability in a restrained time period, a novel solution strategy is proposed. The overall non-iterative algorithm comprises a multi-step decomposition approach, which starts with a reduced scope and incrementally complements the schedule in multiple subproblem stages. Each of those optimizations holds less decision variables and makes use of warmstart information obtained from the predecessor model. That way, a first feasible solution accelerates the subsequent improvement process. Furthermore, the optimization focus can be shifted beneficially leveraging the Gurobi solver parameters. Findings suggest that correlation may exist between certain characteristics of the scheduling scope and ideal parameter settings, which yield potential for further investigation. Another promising area for future research addresses the concurrent multi-processing of independent MILPs on a single machine. First observations indicate that significant performance gains can be achieved in some cases, though sound dependencies were not discovered yet.
- Published
- 2022
- Full Text
- View/download PDF
20. Online Batch Scheduling of Incompatible Job Families with Variable Lookahead Interval.
- Author
-
Li, Wenhua, Wang, Libo, and Yuan, Hang
- Subjects
ONLINE algorithms ,FAMILIES ,SCHEDULING ,ECONOMIC lot size - Abstract
We consider online parallel-batch scheduling of f incompatible unit-length job families with variable lookahead interval to minimize the maximum completion time, where f is the number of job families which is known in advance. Incompatible job family means that a batch only contains the jobs from the same job family. At any time t , an online algorithm can foresee the information of the jobs arriving in the time interval (t , t + Δ (t) ] , where Δ (t) = (λ − 1) t + β is variable. When the batch capacity b = ∞ and f ≥ 1 , we provide a best possible online algorithm with competitive ratio 1 + α f for 0 ≤ β < 1 and 1 ≤ λ ≤ 1 + β , where α f is a positive root of λ f α f 2 + (λ f + β + 1 − f) α f + β − f = 0. When the batch capacity (f <) b < ∞ and f ≥ 2 , we give an online algorithm with competitive ratio 1 + max { f f α f + f , f λ f α f + β + 1 } for 0 ≤ β < 1 and λ ≥ 1 , and prove that it is the best possible for λ = 1 and 0 ≤ β ≤ f + 1 − f 2 + 1 2 . [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
21. Simheuristic algorithm for a stochastic parallel machine scheduling problem with periodic re-planning assessment.
- Author
-
Abu-Marrul, Victor, Martinelli, Rafael, Hamacher, Silvio, and Gribkovskaia, Irina
- Subjects
- *
JOB shops , *PARALLEL algorithms , *MONTE Carlo method , *SETUP time , *SCHEDULING , *VALUE at risk - Abstract
This paper addresses a parallel machine scheduling problem with non-anticipatory family setup times and batching, considering the task's stochastic processing times and release dates. The problem arises from a real-life ship scheduling problem in the oil and gas industry. We developed an Iterated Greedy simheuristic with built-in Monte Carlo Simulation to sample the stochastic parameters. We conducted experiments on a set of instances from the literature, considering two simheuristic variants and three uncertainty levels for the stochastic parameters. To highlight the advantages of using simulation to tackle the stochastic problem, the simheuristics are compared against a regular Iterated Greedy metaheuristic, yielding an improvement of up to 16.5% on the objective function's expected values, with a reduced impact on computational times. During a risk analysis, the Pareto set of solutions is generated to illustrate the trade-off between the expected objective value of the solutions and the conditional value at risk, providing decision-makers with a useful tool to select the schedules that better fit their risk profiles. We use an iterative mechanism to build confidence intervals within a certain confidence level during the method's simulation step, interrupting the procedure when it reaches the desired error. This strategy's advantage is highlighted in the computational experiments, which indicates that the number of replications of the simulation is instance and uncertainty level dependent. A periodic re-planning strategy is also used to evaluate the performance of the simheuristic, highlighting the advantages of using the proposed algorithm in a real-life usage situation. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
22. On lower and upper bounds for single machine parallel batch scheduling.
- Author
-
Gafarov, Evgeny R. and Dolgui, Alexandre
- Abstract
In this paper, we consider a single machine parallel batch scheduling problem subject to chains of jobs. We present polynomial lower and upper bounds as well as their experimental comparison and relative errors. According to the results of the numerical experiment, the relative difference between upper and lower bounds does not exceed 1.5. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
23. GLUME: A Strategy for Reducing Workflow Execution Times on Batch-Scheduled Platforms
- Author
-
Hataishi, Evan, Dutot, Pierre-François, Silva, Rafael Ferreira da, Casanova, Henri, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Klusáček, Dalibor, editor, Cirne, Walfredo, editor, and Rodrigo, Gonzalo P., editor
- Published
- 2021
- Full Text
- View/download PDF
24. Scheduling Challenges for Variable Capacity Resources
- Author
-
Zhang, Chaojie, Chien, Andrew A., Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Klusáček, Dalibor, editor, Cirne, Walfredo, editor, and Rodrigo, Gonzalo P., editor
- Published
- 2021
- Full Text
- View/download PDF
25. Integrated Transportation and Packaging Problem Modeling and Application
- Author
-
Köksal, Tuğçe, Akkuş, Ege, Demirel, Gökçe, Tosun, Esin, Gökçe, Mahmut Ali, Yurtseven, Cansu, Cavas-Martínez, Francisco, Series Editor, Chaari, Fakher, Series Editor, Gherardini, Francesco, Series Editor, Haddar, Mohamed, Series Editor, Ivanov, Vitalii, Series Editor, Kwon, Young W., Series Editor, Trojanowska, Justyna, Series Editor, Durakbasa, Numan M., editor, and Gençyılmaz, M. Güneş, editor
- Published
- 2021
- Full Text
- View/download PDF
26. Minimizing Tardiness in Stochastic Flexible Job Shop Problem
- Author
-
Nekouei-Shahraki, Mahsa, Abraham, Ajith, Lotfi, Mohammd Mehdi, Kacprzyk, Janusz, Series Editor, Pal, Nikhil R., Advisory Editor, Bello Perez, Rafael, Advisory Editor, Corchado, Emilio S., Advisory Editor, Hagras, Hani, Advisory Editor, Kóczy, László T., Advisory Editor, Kreinovich, Vladik, Advisory Editor, Lin, Chin-Teng, Advisory Editor, Lu, Jie, Advisory Editor, Melin, Patricia, Advisory Editor, Nedjah, Nadia, Advisory Editor, Nguyen, Ngoc Thanh, Advisory Editor, Wang, Jun, Advisory Editor, Abraham, Ajith, editor, Sasaki, Hideyasu, editor, Rios, Ricardo, editor, Gandhi, Niketa, editor, Singh, Umang, editor, and Ma, Kun, editor
- Published
- 2021
- Full Text
- View/download PDF
27. An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems.
- Author
-
Shahvari, Omid, Logendran, Rasaratnam, and Tavana, Madjid
- Subjects
PRODUCTION scheduling ,ECONOMIC lot size ,RANDOM forest algorithms ,SETUP time ,LINEAR programming ,SCHEDULING ,MATHEMATICAL optimization - Abstract
This paper presents the problem of batching and scheduling jobs belonging to incompatible job families on unrelated-parallel machines. More specifically, we investigate cost-efficient approaches for solving batching and scheduling problems concerning the desired lower bounds on batch sizes ( LB b ), which indirectly has a considerable impact on the production cost. Batch scheduling is a more realistic extension of the traditional group scheduling approach, in which the jobs belonging to a job family can be processed as multiple batches. The objective is to minimize the total weighted job completion time and tardiness subject to a machine- and sequence-dependent setup time, dynamic machine availability and job release times, customer segments and job priority, and different machine capability and eligibility criteria for processing. Solving this type of batch scheduling problem is a big challenge due to the high computational complexity incurred by both the sequencing assignment and batching composition. A machine learning random forest classification algorithm is used for the LB b determination. Then, an efficient mixed-integer linear programming model (MILP) is developed based on the flow conservation constraints of jobs on machines to reduce the computational complexity. By mapping the MILP model onto a network formulation, an equivalent integer set partitioning type formulation is developed for a branch-and-price optimization algorithm. Computational experiments carried out over different sets of instances, indicate the efficiency and effectiveness of the optimization algorithm, compared to the linear relaxation and relaxed MILP models. Regarding the only available benchmark in the literature, the optimization algorithm yields optimal solutions with affordable computational time. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
28. Multi-Processor Combined Production Batch Scheduling Problem Based on Brain Storm Optimization Algorithm.
- Author
-
WANG Quanwu, XU Zhenhao, and GU Xingsheng
- Subjects
PRODUCTION scheduling ,MATHEMATICAL optimization ,BRAINSTORMING ,MANUFACTURING processes ,JOB shops - Abstract
In the field of production scheduling, due to the influence of many factors such as production technology, each production process usually requires multiple machines to simultaneously participate in processing. Meanwhile, the number of workpieces to be processed is large, and each type of workpiece needs to be processed in batches for shortening the production cycle. Aiming at the above problems, in a job shop environment, this paper adopts a variable batching scheme according to the load of the machines involved in each processing process, and proposes a non-mixed multi-processor combined production batch scheduling model and integrate the brainstorming algorithm to search the shortest processing time. Moreover, an improved brainstorming algorithm is proposed by introducing greedy thinking and dynamic discussion mechanism. The number of discussions is changed adaptively with the iteration and the global search and local search are utilized to strengthen the search ability of the proposed algorithm. Finally, it is shown via the test results that the improved brainstorming algorithm is more efficient and convergent than the basic brainstorming algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
29. Integrated production scheduling and batch delivery with fixed departure times and inventory holding costs.
- Author
-
Agnetis, Alessandro, Aloulou, Mohamed Ali, and Kovalyov, Mikhail Y.
- Subjects
PRODUCTION scheduling ,SUPPLY chain management ,INVENTORY control ,PRODUCTION management (Manufacturing) ,MANUFACTURING processes ,MANUFACTURED products - Abstract
In this paper, we address a model for supply chain coordination. There are m manufacturers modelled as single machines, each of which processes a specific set of jobs (products). After processing is completed, jobs are batched, and batches are shipped to a customer by means of vehicles. The problem consists in concurrently finding a production schedule of the jobs, a partition of jobs into delivery batches and an assignment of delivery batches to vehicles, so that jobs are delivered within their deadlines and total costs are minimised. We focus on a scenario characterised by fixed departure times and inventory holding costs. For each departure time there is a given number of vehicles, possibly having limited capacity. Each job incurs a cost proportional to the time from job completion to delivery departure. In this paper, we show that the problem is NP-hard even for a very restricted case, and report various polynomiality results for two scenarios, namely: (i) when the production sequence of each manufacturer is fixed in advance, and (ii) when there is a single manufacturer and processing times are all equal to 1. We also point out several open problems. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
30. A branch and bound algorithm for scheduling unit size jobs on parallel batching machines to minimize makespan.
- Author
-
Ozturk, Onur, Begen, Mehmet A., and Zaric, Gregory S.
- Subjects
PRODUCTION scheduling ,BATCH processing ,BRANCH & bound algorithms ,MIXED integer linear programming ,MATHEMATICAL programming ,MATHEMATICAL optimization - Abstract
In this paper, we present a branch and bound algorithm for the parallel batch scheduling of jobs having different processing times, release dates and unit sizes. There are identical machines with a fixed capacity and the number of jobs in a batch cannot exceed the machine capacity. All batched jobs are processed together and the processing time of a batch is given by the greatest processing time of jobs in that batch. We compare our method to a mixed integer program as well as a method from the literature that is capable of optimally solving instances with a single machine. Computational experiments show that our method is much more efficient than the other two methods in terms of solution time for finding the optimal solution. [ABSTRACT FROM PUBLISHER]
- Published
- 2017
- Full Text
- View/download PDF
31. Optimizing distributed reentrant heterogeneous hybrid flowshop batch scheduling problem: Iterative construction-local search-reconstruction algorithm.
- Author
-
He, Peng, Zhang, Biao, Lu, Chao, Meng, Lei-lei, and Zou, Wen-qiang
- Subjects
EVIDENCE gaps ,NP-hard problems ,LINEAR programming ,COMPARATIVE studies ,SCHEDULING - Abstract
• A MILP model for the DRHHFBSP is developed. • A construction heuristic capable of generating excellent solutions is developed. • An iterative construction-local search-reconstruction algorithm is designed. In recent years, the distributed hybrid flowshop scheduling problem (DHFSP) has garnered widespread attention due to the continuous emergence of practical challenges. The production model, characterized by multiple varieties and small batches, is widely observed in the industrial sector. Additionally, in various real-world scenarios, batches often undergo repeated processes across multiple stages. This paper addresses the research gap by introducing the reentrant nature of batches and the heterogeneity of factories into the DHFSP, resulting in a novel problem referred to as the distributed reentrant heterogeneous hybrid flowshop batch scheduling problem (DRHHFBSP). To tackle this problem, we propose a mixed-integer linear programming (MILP) model. Given that this problem falls into the NP-hard category, an iterative construction-local search-reconstruction algorithm (ICLSRA) is designed. Specifically designed by incorporating construction, local search, and reconstruction processes that have different roles, this algorithm strikes a balance between local and global search. Comparative analysis with the MILP model and state-of-the-art algorithms demonstrates the superiority of ICLSRA in achieving efficient solutions for the DRHHFBSP. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
32. A Batch Scheduling Problem of Automatic Drug Dispensing System in Outpatient Pharmacy
- Author
-
Liu, Lili, Fu, Chunyu, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Zhang, Zhao, editor, Li, Wei, editor, and Du, Ding-Zhu, editor
- Published
- 2020
- Full Text
- View/download PDF
33. 基于改进粒子群算法的多机器多任务3D打印智能调度方法.
- Author
-
周明霞, 张梦娜, 李虓宇, 吴川, and 张潇
- Abstract
Copyright of Computer Measurement & Control is the property of Magazine Agency of Computer Measurement & Control 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.)
- Published
- 2022
- Full Text
- View/download PDF
34. Single Item Batch-scheduling Model for a Flow Shop with m Batch-processing Machines to Minimize Total Actual Flow Time.
- Author
-
Halim, Abdul Hakim, Hidayat, Nita Puspita Anugrawati, and Aribowo, Wisnu
- Subjects
FLOW shops ,FLOW shop scheduling ,BATCH processing ,AIRCRAFT industry ,MACHINERY - Abstract
We propose a batch-scheduling model to minimize the total actual flow time (TAF) of parts to be processed in a flow shop consisting of m batch-processing machines. A batch-processing machine (BPM) is a machine that can process several parts at once, and the TAF of parts is the total interval time from the arrival times to the corresponding due date. In the real world, shop floors often have production lines with BPMs and multistage processes. We were motivated by a real problem in the aircraft industry and aimed to simultaneously satisfy the due dates and minimize the total time that parts spend in the shop. The problem was formulated as a mathematical model and solved using a proposed algorithm. The batch-scheduling problem is divided into batching and scheduling subproblems. The solution has been obtained by adopting backward scheduling. This paper develops a new model of flow shop scheduling problem for the shop with batch processing machines and the heuristic solution method. It provides numerical examples and their results to demonstrate the effectiveness of the proposed algorithm for solving the problem. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
35. A new method for a class of parallel batch machine scheduling problem.
- Author
-
Jiang, Wei, Shen, Yilan, Liu, Lingxuan, Zhao, Xiancong, and Shi, Leyuan
- Subjects
MIXED integer linear programming ,ONLINE algorithms ,CONSTRAINT programming ,BATCH processing - Abstract
This paper studies the scheduling problem of jobs with release times, non-identical sizes, and incompatible job families on unrelated parallel batch machines. The capacities of batch machines and the processing times of each job on the batch machines are different. The processing time of one batch is equal to the longest processing time of jobs in this batch. Different types of jobs are not allowed to be assigned into the same batch, which is known as incompatible job families. Mixed integer linear programming and constraint programming (CP) models are proposed. A new batch-based local search method is designed and an iterated greedy (IG) algorithm is developed to avoid unreasonable exchanging of jobs during the local search. Numerical results show that the CP method can obtain high quality solutions in the small-scale instances. For the large-scale instances, the IG algorithm with the new local search method has a competitive performance. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
36. Data-Driven Locality-Aware Batch Scheduling
- Author
-
Gonthier, Maxime, Larsson, Elisabeth, Marchal, Loris, Nettelblad, Carl, Thibault, Samuel, Gonthier, Maxime, Larsson, Elisabeth, Marchal, Loris, Nettelblad, Carl, and Thibault, Samuel
- Abstract
Clusters employ workload schedulers such as the Sturm Workload Manager to allocate computing jobs onto nodes. These schedulers usually aim at a good trade-off between increasing resource utilization and user satisfaction (decreasing job waiting time). However, these schedulers are typically unaware of jobs sharing large input files, which may happen in data intensive scenarios. The same input files may end up being loaded several times, leading to a waste of resources. We study how to design a data-aware job scheduler that is able to keep large input files on the computing nodes, without impacting other memory needs, and can benefit from previously-loaded tiles to decrease data transfers in order to reduce the waiting times ofjobs. We present three schedulers capable of distributing the load between the computing nodes as well as re-using input files already loaded in the memory of some node as much as possible. We perform simulations with single node jobs using traces of real HPC-cluster usage, to compare them to classical job schedulers. The results show that keeping data in local memory between successive jobs and using data -locality information to schedule jobs improves performance compared to a widely -used scheduler (FCFS, with and without backfilling): a reduction in job waiting time (a 7.5% improvement in stretch), and a decrease in the amount of data transfers (7%).
- Published
- 2024
- Full Text
- View/download PDF
37. Research of Flexible Assembly Job-Shop Batch–Scheduling Problem Based on Improved Artificial Bee Colony
- Author
-
Xiulin Li, Jiansha Lu, Chenxi Yang, and Jiale Wang
- Subjects
flexible assembly job shop ,batch splitting ,batch scheduling ,lot streaming ,consistent size ,unequal size ,Biotechnology ,TP248.13-248.65 - Abstract
This study examined the flexible assembly job-shop scheduling problem with lot streaming (FAJSP-LS), common in multivariety and small-batch production, such as household electrical appliances. In FAJSP-LS, an assembly stage is appended to the flexible job shop, and jobs in the first stage are processed in a large batch to reduce switching costs, while leading to more waiting time, especially during the assembly stage. This article considered splitting the batch into a few sub-batches of unequal and consistent sizes to allow jobs to efficiently pass the two-stage system. With this objective, the problem was modeled as a mixed-integer linear program comprising the following two subproblems: batch splitting and batch scheduling. As the integrated problem is NP-hard, the improved bioinspired algorithm based on an artificial bee colony was proposed, including a four-layer chromosome–encoding structure to describe the solution, as well as an optimization strategy utilizing different bee colonies to synchronously solve this two-stage problem. To examine the algorithm’s efficiency, a benchmark case was used to show that better solutions can be acquired with the improved algorithm regardless of whether the batch was split into equal or unequal sizes. To promote practical implementation, the algorithm was applied to a real case refrigerator workshop and showed better performance on time efficiency when jobs were split into unequal sizes compared to jobs without splitting or splitting into equal sizes.
- Published
- 2022
- Full Text
- View/download PDF
38. A Model of Multiple Items Batch Scheduling for m Batch Processors Flow shop to Minimize Total Actual Flowtime.
- Author
-
Hidayat, Nita P. A., Aribowo, Wisnu, and Halim, Abdul Hakim
- Subjects
BATCH processing ,AIRCRAFT industry ,FLOW shops ,NUMERICAL analysis ,COMPUTER software development - Abstract
This research was motivated by a real problem in an aircraft company which has m batch processors (BP) flow shop in this machine order; BP
1 - BP2 -...-BPm . The number of parts in a batch can be processed on a BP simultaneously. Under multiple items condition, the demanded part requires a different processing time which it depends on the type of item. Completed parts will be delivered simultaneously at a common due date. We developed a batch scheduling model for this problem by adopting the total actual flowtime part (Fa ) as an objective function. Numerical examples are done by using the Lingo software, and the results showed that the model can guarantee Fa is minimum, the due date and the flow shop rules are fulfilled under flow shop condition. [ABSTRACT FROM AUTHOR]- Published
- 2021
39. Adaptive Batch Scheduling for Open-Domain Question Answering
- Author
-
Donghyun Choi, Myeongcheol Shin, Eunggyun Kim, and Dong Ryeol Shin
- Subjects
Open-domain question answering ,dense passage retrieval ,batch scheduling ,Electrical engineering. Electronics. Nuclear engineering ,TK1-9971 - Abstract
Open-domain question answering aims to get answers for given questions from a set of documents. Recently, dual encoder architecture is widely adopted to dense passage retrieval for question answering. In-batch negative sampling is typically used to gather extra negative samples during training. In this paper, we propose adaptive batch scheduling to enhance the performance of in-batch negative sampling. The proposed algorithm schedules training batches to increase the difficulty of the sampled negatives by in-batch negative sampling during training. We evaluated the proposed approach on the two well-known document retrieval benchmark datasets MSMARCO and Natural Questions. The evaluation result shows that the proposed adaptive batch scheduling could significantly improve the document retrieval performances of dual encoder architecture document retrieval systems.
- Published
- 2021
- Full Text
- View/download PDF
40. MaLeFICE: Machine learning support for continuous performance improvement in computational engineering.
- Author
-
Sonmezer, Hasan Berk, Muhtaroglu, Nitel, Ari, Ismail, and Gokcin, Deniz
- Subjects
MACHINE learning ,FINITE element method ,TIME perception ,ENGINEERING ,COMPUTER engineering - Abstract
Summary: Computer aided engineering (CAE) practices improved drastically within the last decade due to ease of access to computing resources and open‐source software. However, increasing complexity of hardware and software settings and the scarcity of multiskilled personnel rendered the practice inefficient and infeasible again. In this article, we present a method for continuous performance improvement in computational engineering that combines online performance profiling with machine learning (ML). To test the viability of this method, we provide a detailed analysis for solution time estimation of finite element analysis (FEA) jobs based on multidimensional models. These models combine numerous matrix features (matrix size, density, bandwidth, etc.), solver features (direct‐iterative, preconditioning, tolerance), and hardware features (core count, virtual–physical). We repeat our analysis over different machines as well as docker containers to demonstrate applicability over different platforms. Next, we train supervised and unsupervised ML algorithms over commonly used, realistic FEA benchmarks and compare accuracy of different models. Finally, we design two new ML‐based online batch schedulers called shortest predicted time first (SPTF) and shortest cluster time first (SCTF), which are comparable in performance to the optimal, but offline shortest job first (SJF) scheduler. We find that ML‐based profiling and scheduling can reduce the average turnaround times by 2×–5× over other alternatives. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
41. 单机上带有可变前瞻区间的分批在线排序问题.
- Author
-
王利博, 李文华, and 余丹
- Subjects
ONLINE algorithms ,PRODUCTION scheduling ,SCHEDULING ,TIME - Abstract
Copyright of Operations Research Transactions / Yunchouxue Xuebao is the property of Editorial office of Operations Research Transactions 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.)
- Published
- 2022
- Full Text
- View/download PDF
42. A Batch Scheduling Model for a Three-stage Hybrid Flowshop Producing Products with Hierarchical Assembly Structures
- Author
-
Rahmi Maulidya, Suprayogi, Rachmawati Wangsaputra, and Abdul Hakim Halim
- Subjects
batch scheduling ,hierarchical assembly structures ,three-stage hybrid flowshop ,total actual flow time ,unique and common component ,Technology ,Technology (General) ,T1-995 - Abstract
This paper addresses a batch scheduling problem for a three-stage hybrid flowshop consisting of a machining stage processing common and unique components on unrelated parallel machines, an assembly stage combining the components into assembled products with complex assembly structures, and a differentiation stage processing the assembled products on dedicated machines to produce different product types. The common components are the same for all products and are processed in batches, while the unique components are dedicated to respective given product types and are processed individually (one-by-one component). The goal is to schedule all the products with different assembly structures to minimize total actual flow time (TAFT) defined as total time interval of components to be processed from their arrival times to their common due date. A non-linear programming model is proposed, where small size problems can be solved optimally using the LINGO software, and large size problems is to be solved using a heuristic algorithm. The proposed algorithm consists of two sub-algorithms. The first one is constructed using a shortest processing time (SPT) based heuristic to get a job sequence as an initial solution and the second one is to improve the initial solution using the variable neighbourhood descent (VND) method with neighbourhood insert and swap move operators. In solving the problem with the algorithm, two scenarios arise, e.g., the same and the different sequences for all stages. A set of hypothetical data is generated for different hierarchical assembly structures to test the model and the algorithm, and the results show that the different sequences for all stages obtain solutions with better performances than the same ones.
- Published
- 2020
- Full Text
- View/download PDF
43. Minimising makespan on a batch processing machine using heuristics improved by an enumeration scheme.
- Author
-
Li, XiaoLin, Li, YuPeng, and Wang, Yu
- Subjects
BATCH processing ,BATCH process control ,MANUFACTURING processes ,HEURISTIC ,PRODUCTION planning ,JOB analysis - Abstract
Batch processing machines can process several job simultaneously and are encountered in many manufacturing environments. Jobs in a batch are processed together and have the same start and end processing time. Since jobs are non-identical in job sizes and job processing times, they should be reasonably scheduled to improve the machine utilisation and processing efficiency. Two well-known heuristics, first fit longest processing time and best fit longest processing time (BFLPT), are improved in this study by considering identical job sizes and then BFLPT is further improved by an enumeration scheme proposed. Computational experiments are conducted to evaluate the performance of the improvement and the results are compared with the existing heuristics. [ABSTRACT FROM PUBLISHER]
- Published
- 2017
- Full Text
- View/download PDF
44. Complexity and Approximation Results for Setup-Minimal Batch Scheduling with Deadlines on a Single Processor
- Author
-
Kress, Dominik, Barketau, Maksim, Pesch, Erwin, Müller, David, Fortz, Bernard, editor, and Labbé, Martine, editor
- Published
- 2019
- Full Text
- View/download PDF
45. A batch scheduling model for m heterogeneous batch processor.
- Author
-
Hidayat, Nita P.A., Cakravastia, Andi, Samadhi, T.M.A. Ari, and Halim, Abdul Hakim
- Subjects
PRODUCTION scheduling ,BATCH processing ,PRODUCTION control ,MANUFACTURING processes ,ALGORITHMS ,SCHEDULING - Abstract
This research addresses a batch scheduling problem for single item parts with multi due date on m heterogeneous batch processors. The objective is to minimise total actual flowtime of parts through the shop. The total actual flowtime of parts in a batch is the multiplication of the interval between batch arrival time and the due date by the number of parts in the batch. Using the actual flowtime as the objective means it is oriented to satisfy the due date as a commitment to customers, and simultaneously to minimise the length of time of the parts spending in the shop. An algorithm to solve this problem is proposed. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
46. 打印参数可变模式下 3D 打印批调度问题研究.
- Author
-
王 彬, 唐 昊, 戴 飞, and 谭 琦
- Subjects
MACHINE learning ,DECISION making ,WORKBENCHES ,PRODUCTION scheduling ,SCHEDULING ,THREE-dimensional printing ,TASKS ,ALGORITHMS - Abstract
Copyright of Control Theory & Applications / Kongzhi Lilun Yu Yinyong is the property of Editorial Department of Control Theory & Applications 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.)
- Published
- 2021
- Full Text
- View/download PDF
47. Mixed-batch scheduling to minimize total tardiness using deep reinforcement learning.
- Author
-
Huang, JinDian
- Subjects
DEEP reinforcement learning ,TARDINESS ,SCHEDULING ,FEATURE extraction ,BATCH processing ,REINFORCEMENT learning - Abstract
This study addresses the issue of scheduling batch machine to minimize total tardiness. Vacuum heat treatment allows multiple jobs to be processed as a batch, as long as they do not exceed the machine's weight and size limits; the weight and size of the jobs both impact the batch processing time. By considering the differences in the release time and due date for each job, a mixed-integer linear programming model is developed and validated using small-scale instances. To tackle large-scale scheduling problems, an intelligent algorithm based on deep reinforcement learning is proposed. Double deep Q-learning networks are designed, and the environmental state feature matrix is extracted as input parameters for the networks. Four job-sorting rules and three scheduling time windows are defined, resulting in twelve action rules within the action space. The most suitable action rule is dynamically selected based on the current batch's environmental status during the scheduling process. Through extensive comparison using large-scale random data, the proposed algorithm demonstrates significantly improved scheduling performance compared to the benchmark algorithms. • A new mixed-batch scheduling problem involves batch times influenced by job weight/size, constrained by machine weight/size. • An intelligent algorithm based on DRL (Deep Reinforcement Learning) was proposed to address batch scheduling problems. • Double deep Q-learning networks were designed, with environmental state feature matrix extracted as input for the networks. • Four job sorting rules and three scheduling time windows were defined, yielding twelve action rules in the action space. • Dynamic selection of the most suitable action rule based on the current batch's environmental status during the scheduling. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
48. A Study on Heuristic Task Scheduling Optimizing Task Deadline Violations in Heterogeneous Computational Environments
- Author
-
Bo Wang, Ying Song, Changhai Wang, Wanwei Huang, and Xiaoyun Qin
- Subjects
Batch scheduling ,heuristic scheduling ,task scheduling ,deadline violation ,Electrical engineering. Electronics. Nuclear engineering ,TK1-9971 - Abstract
In this paper, we focus on the problem of optimizing deadline violations for executing tasks in various heterogeneous computational environments. To address the problem, we formulated it as a binary nonlinear programming (BNP) model, which maximize the number of completed tasks and optimize the resource utilization of servers. To solve the BNP model in a polynomial complexity, we propose a heuristic task scheduling method, which iteratively schedules a task to the first core such that the accumulated slack time of all scheduled tasks is minimum, until the core cannot finish any task, and executes tasks with the earliest deadline first in each core to execute as many task as possible in a core. Experiment results based on a real world trace show that our method has upto 100% less task violations, and has the best performance in resource efficiency optimization in overall, compared with eight classical and state-of-the-art heuristic methods.
- Published
- 2020
- Full Text
- View/download PDF
49. Min-Max-Flow Based Algorithm for Evacuation Network Planning in Restricted Spaces
- Author
-
Hong, Yi, Liu, Jiandong, Luo, Chuanwen, Li, Deying, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Kim, Donghyun, editor, Uma, R. N., editor, and Zelikovsky, Alexander, editor
- Published
- 2018
- Full Text
- View/download PDF
50. A Batch Scheduling Model for a Three-stage Flow Shop with Job and Batch Processors Considering a Sampling Inspection to Minimize Expected Total Actual Flow Time.
- Author
-
Suryadhini, Pratya Poeri, Sukoyo, Sukoyo, Suprayogi, Suprayogi, and Halim, Abdul Hakim
- Subjects
- *
FLOW shops , *JOB shops , *SAMPLING (Process) , *FLOW shop scheduling , *PROBLEM solving - Abstract
Purpose: This research develops a batch scheduling model for a three-stage flow shop with job processors in the first and second stages and a batch processor in the third stage. The model integrates production process activities and a product inspection activity to minimize the expected total actual flow time. Design/methodology/approach: The problem of batch scheduling for a three-stage flow shop is formulated as a mathematical model, and a heuristic algorithm is proposed to solve the problem. This model applies backward scheduling to accommodate the objective of minimizing the expected total actual flow time. Findings: This research has proposed a batch scheduling model for a three-stage flow shop with job and batch processors to produce multiple items and an algorithm to solve the model. The objective is to minimize total actual time. The resulting production batches can be sequenced between all types of products to minimize idle time, and the batch processor capacity affects the sample size and indirectly affects the production batch size. Originality/value: This research develops a batch scheduling model for a three-stage flow shop constituting job and batch processors and carrying out integrated production and inspection activities to minimize the expected total actual flow time [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.