Log in

Relevant bibliographies by topics / Makespan Optimization

Contents

Journal articles
Dissertations / Theses
Book chapters
Conference papers

Academic literature on the topic 'Makespan Optimization'

Author: Grafiati

Published: 7 June 2025

Last updated: 9 July 2025

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Makespan Optimization.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Makespan Optimization"

1

Dika Prasisti and Yohanes Anton Nugroho. "Optimasi Penjadwalan Produksi untuk Meminimalkan Makespan dengan Pendekatan Particle Swarm Optimization dan Genetic Algorithm." Jurnal Teknologi dan Manajemen Industri Terapan 2, no. 2 (2023): 111–18. http://dx.doi.org/10.55826/tmit.v2i2.134.

Full text

Abstract:

PT Adi Satria Abadi merupakan perusahaan manufaktur yang bergerak dalam produksi sarung tangan golf. Permasalahan yang terjadi adalah tanggal 21 Maret terdapat produk work in process di bagian sewing sejumlah 1.205 unit sarung tangan golf, dari total keseluruhan order sebanyak 11.880 unit sarung tangan golf. Produk harus dikirimkan pada tanggal 22 Maret dan jumlah produk work in process melebihi target produksi harian. Tujuan dari penelitian ini adalah mendapatkan hasil penjadwalan produksi dengan particle swarm optimization algorithm dan algoritma genetika untuk mendapatkan nilai makespan minimum. Perhitungan penjadwalan produksi dengan kedua metode tersebut dilakukan sesuai dengan prosedur masing-masing metode menggunakan software Matlab R2020a. Hasil penjadwalan particle swarm optimization mempunyai urutan job, yaitu J1, J3, J2, J4, J5, J6 dengan makespan sebesar 273 menit. Sedangkan hasil penjadwalan produksi dengan metode algoritma genetika diperlukan waktu proses total (makespan) untuk memproduksi job dengan urutan J1, J4, J6, J5, J2, J3 sebesar 281 menit. Berdasarkan hasil makespan masing-masing metode menunjukkan bahwa hasil penjadwalan produksi dengan metode particle swarm optimization memiliki waktu lebih cepat 8 menit dibandingkan dengan metode genetic algorithm. Hal ini menyimpulkan bahwa metode particle swarm optimization merupakan metode yang paling optimal untuk penjadwalan produksi karena memiliki nilai makespan yang paling minimum.

APA, Harvard, Vancouver, ISO, and other styles

2

Saini, Nisha, and Jitender Kumar. "Mean makespan task scheduling approach for the edge computing environment." International Journal of Electrical and Computer Engineering (IJECE) 14, no. 4 (2024): 4714. http://dx.doi.org/10.11591/ijece.v14i4.pp4714-4720.

Full text

Abstract:

Task scheduling in the edge computing environment poses significant challenges due to its inherent NP-hard nature. Several researchers concentrated on minimizing simple makespan, disregarding the reduction of the mean time to complete all tasks, resulting in uneven distributions of mean completion times. To address this issue, this study proposes a novel mean makespan task scheduling strategy (MMTSS) to minimize simple and mean makespan. MMTSS optimizes the utilization of virtual machine capacity and uses the mean makespan optimization to minimize the processing time of tasks. In addition, it reduces imbalance by evenly distributing tasks among virtual machines, which makes it easier to schedule batches subsequently. Using genetic algorithm optimization, MMTSS effectively lowers processing time and mean makespan, offering a viable approach for effective task scheduling in the edge computing environment. The simulation results, obtained using cloudlets ranging from 500 to 2000, explicitly demonstrate the improved performance of our approach in terms of both simple and mean makespan metrics.

APA, Harvard, Vancouver, ISO, and other styles

3

Saini, Nisha, and Jitender Kumar. "Mean makespan task scheduling approach for the edge computing environment." Mean makespan task scheduling approach for the edge computing environment 14, no. 4 (2024): 4714–20. https://doi.org/10.11591/ijece.v14i4.pp4714-4720.

Full text

Abstract:

Task scheduling in the edge computing environment poses significant challenges due to its inherent NP-hard nature. Several researchers concentrated on minimizing simple makespan, disregarding the reduction of the mean time to complete all tasks, resulting in uneven distributions of mean completion times. To address this issue, this study proposes a novel mean makespan task scheduling strategy (MMTSS) to minimize simple and mean makespan. MMTSS optimizes the utilization of virtual machine capacity and uses the mean makespan optimization to minimize the processing time of tasks. In addition, it reduces imbalance by evenly distributing tasks among virtual machines, which makes it easier to schedule batches subsequently. Using genetic algorithm optimization, MMTSS effectively lowers processing time and mean makespan, offering a viable approach for effective task scheduling in the edge computing environment. The simulation results, obtained using cloudlets ranging from 500 to 2000, explicitly demonstrate the improved performance of our approach in terms of both simple and mean makespan metrics.

APA, Harvard, Vancouver, ISO, and other styles

4

Yunus, Muhammad Ahladi, Marwan Marwan, and Muhammad Rijal Alfian. "Optimization of production process scheduling at Mataram Convection using the Campbell-Dudek and Smith method and the Ho and Chang method." Majalah Ilmiah Matematika dan Statistika 23, no. 1 (2023): 80. http://dx.doi.org/10.19184/mims.v23i1.36403.

Full text

Abstract:

Konveksi Mataram (Djagoan Kaos dan Seragam) is one of the industries engaged in the manufacture of various types of clothing models with fabric as the basic material. So far, the scheduling method used by the company is the First Come First Serve method, in which the completion of production is based on order-to-order data. In this case, with high order intensity, companies often experience difficulties in completing orders according to a predetermined pick-up time. The problems experienced by the company were caused by the production process scheduling that was not optimal. Based on the problems encountered, the purpose of this research is to obtain the optimal scheduling sequence by determining the smallest makespan (minimum total completion time) of the application of the method to the production process. The methods used in this study are the Campbell-Dudek and Smith method and the Ho and Chang method and from these two methods, it is known that the smallest production process is optimal. Based on the results of calculations using the Campbell-Dudek and Smith method, the optimal scheduling sequence with the smallest makespan is 39163 minutes or the production process will be completed in 73 working days. While the results of calculations using the Ho and Chang method obtained the optimal scheduling sequence with the smallest makespan of 38660.50 minutes or the production process will be completed in 72 working days. From the makespans of the two methods, the Ho and Chang method is superior to the Campbell-Dudek and Smith method with a difference of 502.50 minutes or about 1 working day, whereas when compared to the company's initial method, namely First Serve First Come with a makespan of 43025.50 minutes, the HC method can make completion time efficient with a difference of 4365 minutes or about 8 working days. Keywords: Campbell-Dudek and Smith methods, first come first serve, Ho and Chang, makespan, production schedulingMSC2020: 90B30

APA, Harvard, Vancouver, ISO, and other styles

5

Putra, Andika Prima, Zeny Fatimah Hunusalela, and Hermanto Ruslan. "Usulan Penjadwalan Produksi Menggunakan Metode Algoritma Tabu Search dan Ant Colony Optimization Untuk Meminimasi Makespan di PT. Raja Ampat Indotim." Jurnal KaLIBRASI - Karya Lintas Ilmu Bidang Rekayasa Arsitektur, Sipil, Industri. 5, no. 2 (2022): 139–47. http://dx.doi.org/10.37721/kalibrasi.v5i2.1022.

Full text

Abstract:

Pentingnya penjadwalan produksi untuk mendapatkan waktu penyelesaian pekerjaan yang optimal, yaitu waktu yang dibutuhkan secara wajar oleh pekerja normal untuk menyelesaikan suatu pekerjaan yang dijalankan dalam sistem kerja terbaik. Terdapat suatu permasalahan yang sering terjadi pada PT. Raja Ampat Indotim seperti nilai makespan perusahaan terlalu tinggi pada pembuatan mesin parutan kelapa, pelet lokal dan pemipil jagung dengan nilai makespan sebesar 757,97 menit. Sehingga menyebabkan terlambatnya target pemesanan produk. Tujuan dari penelitian ini adalah untuk mencari alternatif penjadwalan terbaik untuk menggurangi makespan selama proses produksi, sehingga dalam sehari didapatkan waktu proses yang lebih optimal. Metode yang digunakan Algoritma Tabu Search (TS) dan Algoritma Ant Colony Optimization (ACO). Hasil penelitian yang didapatkan dari metode yang digunakan yaitu metode Algoritma Tabu Search pada job 3-1-2 dengan nilai makespan sebesar 621,11 menit. Kemudian metode Algoritma Ant Colony Optimization didapatkan hasil pada job 3-1-2 dengan total makespan terendah yaitu 683,27 menit. Dengan demikian perusahaan dapat menggunakan penjadwalan produksi menggunakan metode Algoritma Tabu Search guna untuk mengatasi target keterlambatan produk pada penjadwalan produksinya.

APA, Harvard, Vancouver, ISO, and other styles

6

Mangngenre, Saiful, A. Besse Indah, Diniary Syamsul, Azran Arief, and Olyvia Novawanda. "Performance analysis of production scheduling in Toyota simulation." Acta logistica 12, no. 1 (2025): 91–102. https://doi.org/10.22306/al.v12i1.592.

Full text

Abstract:

This research analyzes production scheduling performance in the context of sustainable manufacturing using Toyota Production System (TPS) simulation. The primary focus of this study is to study scheduling performance based on the makespan value and job order for each method. To reduce makespan, two metaheuristic techniques are employed: the tabu search (TS) method and the simulated annealing (SA) method. This research fills the literature gap by exploring makespan optimization methods, combining computer simulation with metaheuristics, and considering TPS scheduling constraints. Data obtained from a miniature car simulation based on the Toyota Production System concept. The research method includes SA and TS implementation using Python and Visual Basic 6.0. The results show that SA and TS produce makespan 2.2-3.2% lower than the Initial Method. SA shows flexibility with different job sequences for each level of demand, while TS produces consistent sequences. The increase in makespan as demand increases is consistent across all methods (14.1-16.4%). In conclusion, SA and TS are effective optimization methods for production scheduling, with the selection depending on the preference for flexibility or consistency.

APA, Harvard, Vancouver, ISO, and other styles

7

Mashuri, Chamdan, Ahmad Heru Mujianto, and Hadi Sucipto. "Comparative analysis of the Campbell Dudek Smith (CDS) and GUPTA Methods for Optimization of Production Scheduling." Generation Journal 5, no. 1 (2021): 1–10. http://dx.doi.org/10.29407/gj.v5i1.13954.

Full text

Abstract:

Abstrak – Penelitian optimalisasi waktu produksi menggunakan algoritma campbell dudek smith (CDS) pada penjadwalan proses produksi bertujuan untuk optimasi makespan untuk pengoperasian mesin untuk memproduksi produk wajan ukuran 12, wajan ukuran 14, wajan ukuran 16, wajan ukuran 18 dan wajan ukuran 20 sehingga didapat nilai makespan yang optimal. Metode yang diterapkan algoritma Campbell Dudek and Smith (CDS), CDS merupakan metode yang digunakan dalam penjadwalan bersifat flowshop dikembangkan dari aturan Johnson yang mampu meminimalkan makespan 2 mesin yang disusun seri. Metode CDS sangat cocok pada karakter produksi yang menerapkan urutan mesin untuk proses produksi. CDS menghasilkan beberapa iterasi yang memiliki nilai makespan, dari beberapa iterasi tersebut didapat nilai makespan yang paling minimal untuk menentukan urutan produk yang akan diproduksi. Penelitian ini menghasilakan aplikasi yang dapat menjadwalkan produk yang akan diproduksi oleh mesin secara otomatis. Dari hasil pengujian dengan jumlah produksi 12 buah pada setiap produk dengan perulangan sebanyak 6 kali, maka didapatkan nilai makespan paling minimal yaitu 210,12 menit dengan urutan pengerjaan produk wajan 20, wajan 18, wajan 16, wajan 14, dan wajan 12. Akurasi hasil pengujian aplikasi menunjukkan 99,99% untuk waktu pertama dan 99,96% untuk waktu kedua jika dibandingkan dengan perhitungan manual.

APA, Harvard, Vancouver, ISO, and other styles

8

Sahputra, Iwan Halim, Tanti Octavia, and Agus Susanto Chandra. "TABU SEARCH SEBAGAI LOCAL SEARCH PADA ALGORITMA ANT COLONY UNTUK PENJADWALAN FLOWSHOP." Jurnal Teknik Industri 11, no. 2 (2009): 188–94. http://dx.doi.org/10.9744/jti.11.2.188-194.

Full text

Abstract:

Ant colony optimization (ACO) is one of the meta-heuristic methods developed for finding solutions to optimization problems such as scheduling. Local search method is one part of the ACO which determines the quality of the resulting solution. In this paper, Tabu Search was proposed as a method of local search in ACO to solve the problem of flowshop scheduling. The purpose of this scheduling was to minimize the makespan. Makespan and computation time of the proposed method were compared to the ACO that implemented Job-Index as local search method. Using proposed algorithm, makespan values obtained were not significantly different than solutions of ACO using Job-Index method, and had computation time shorter.   Abstract in Bahasa Indonesia:  Ant colony optimization (ACO) adalah salah satu metode meta-heuristic yang dikembangkan untuk mencari solusi bagi permasalahan optimasi seperti penjadwalan. Metode local search merupakan salah satu bagian dari ACO yang menentukan kualitas solusi yang dihasilkan. Dalam makalah ini Tabu Search diusulkan sebagai metode local search dalam algoritma ACO untuk menyelesaikan masalah penjadwalan flowshop. Tujuan dari penjadwalan ini adalah untuk meminimalkan makespan. Hasil makespan dan computation time dari metode usulan ini akan dibandingkan dengan algoritma ACO yang menggunakan Job-Index sebagai metode local search. Dengan menggunakan algoritma Tabu Search sebagai local search didapat nilai makespan yang tidak berbeda secara signifikan dibandingkan yang menggunakan metode Job-Index, dengan kelebihan computation time yang lebih singkat.  Kata kunci: Tabu Search, Ant Colony Algorithm, Local Search, Penjadwalan Flowshop.

APA, Harvard, Vancouver, ISO, and other styles

9

Mashuri, Chamdan, Ahmad Heru Mujianto, Hadi Sucipto, Rinaldo Yudianto Arsam, and Ginanjar Setyo Permadi. "Production Time Optimization using Campbell Dudek Smith (CDS) Algorithm for Production Scheduling." E3S Web of Conferences 125 (2019): 23009. http://dx.doi.org/10.1051/e3sconf/201912523009.

Full text

Abstract:

The production time optimization study used the Campbell Dudek smith (CDS) algorithm in the production process scheduling aimed at makespan optimization for engine operation to produce 12-size pan products, 14-size griddle, 16-size griddle, 18-size griddle, and 20-size griddle. The method applied by the Campbell Dudek and Smith (CDS) algorithm, CDS is a method used in flowshop-type scheduling developed from Johnson's rule that is able to minimize makespan 2 machines arranged in series. The CDS method is very suitable for production characters who apply the machine sequence to the production process. CDS produces several iterations that have makespan values, from the few iterations the most minimum makespan value is obtained to determine the order of products to be produced. This research produces an application that can schedule products to be produced by the machine automatically. From the results of testing with a total production of 12 pieces on each product with repetitions of 6 times, the minimum makespan value is 210.12 minutes with a work order of 20, grid 18, griddle 16, griddle 14, and griddle 12. Accuracy of results Application testing showed 99.99% for the first time and 99.96% for the second time when compared to manual calculations.

APA, Harvard, Vancouver, ISO, and other styles

10

Lahza, Husam, Sreenivasa B R, Hassan Fareed M. Lahza, and Shreyas J. "Adaptive Multi-Objective Resource Allocation for Edge-Cloud Workflow Optimization Using Deep Reinforcement Learning." Modelling 5, no. 3 (2024): 1298–313. http://dx.doi.org/10.3390/modelling5030067.

Full text

Abstract:

This study investigates the transformative impact of smart intelligence, leveraging the Internet of Things and edge-cloud platforms in smart urban development. Smart urban development, by integrating diverse digital technologies, generates substantial data crucial for informed decision-making in disaster management and effective urban well-being. The edge-cloud platform, with its dynamic resource allocation, plays a crucial role in prioritizing tasks, reducing service delivery latency, and ensuring critical operations receive timely computational power, thereby improving urban services. However, the current method has struggled to meet the strict quality of service (QoS) requirements of complex workflow applications. In this study, these shortcomings in edge-cloud are addressed by introducing a multi-objective resource optimization (MORO) scheduler for diverse urban setups. This scheduler, with its emphasis on granular task prioritization and consideration of diverse makespans, costs, and energy constraints, underscores the complexity of the task and the need for a sophisticated solution. The multi-objective makespan–energy optimization is achieved by employing a deep reinforcement learning (DRL) model. The simulation results indicate consistent improvements with average makespan enhancements of 31.6% and 70.09%, average cost reductions of 62.64% and 73.24%, and average energy consumption reductions of 25.02% and 17.77%, respectively, by MORO over-reliability enhancement strategies for workflow scheduling (RESWS) and multi-objective priority workflow scheduling (MOPWS) for SIPHT workflow. Similarly, consistent improvements with average makespan enhancements of 37.98% and 74.44%, average cost reductions of 65.53% and 74.89%, and average energy consumption reductions of 29.52% and 24.73%, respectively, by MORO over RESWS and MOPWS for CyberShake workflow, highlighting the proposed model’s efficiency gains. These findings substantiate the model’s potential to enhance computational efficiency, reduce costs, and improve energy conservation in real-world smart urban scenarios.

APA, Harvard, Vancouver, ISO, and other styles

More sources

Dissertations / Theses on the topic "Makespan Optimization"

1

Weyerman, Whitney Samuel. "Approximations with Improving Error Bounds for Makespan Minimization in Batch Manufacturing." Diss., CLICK HERE for online access, 2008. http://contentdm.lib.byu.edu/ETD/image/etd2300.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Ibrahem, Al-mehdi Mohamed M. "Scheduling optimization of cellular flowshop with sequence dependent setup times." Proceedings of the 47th CIRP Conference on Manufacturing Systems, 2014. http://hdl.handle.net/1993/30730.

Full text

Abstract:

In cellular manufacturing systems, minimization of the completion time has a great impact on the production time, material flow, and productivity. An effective scheduling is crucial to attaining the advantages of cellular manufacturing systems. This dissertation attempts to solve the Flowshop Manufacturing Cell (cellular flowshop) Scheduling Problem with Sequence Dependent Setup Times (FMCSP with SDSTs) considering two performance measures: the total flow time as a mono objective, and the makespan and total flow time combined as a bi-criteria scheduling problem. The proposed problem is known to be the NP-hard problem because of its complexity. Several metaheuristic algorithms based on Genetic Algorithm (GA), Simulated Annealing (SA), and Particle Swarm Optimization (PSO) are developed for scheduling part families as well as jobs within each part family for FMCSP with SDSTs to minimize the total flow time. A local search method based on SA combined with PSO (named as PSO-SA) is proposed to enhance the intensification and improve the quality of the solution obtained by pure PSO. The effectiveness and efficiency of the proposed metaheuristics are evaluated based on the Relative Percentage Deviation (RPD) from its lower bound, and the robustness. Results indicate PSO-SA is performed similar to best available algorithms for small and medium size test problems. Yet, there is a very small deviation from best results for large problems. A Multi-objective Particle Swarm Optimization (MPSO) and a Multi-objective Simulated Annealing (MOSA) Algorithm are further proposed to solve the bi-criteria optimization problem to minimize the total flow time and makespan simultaneously. An improved PSO is combined with Threshold Acceptance (TA) algorithm to improve effectiveness of the proposed MPSO (named as IMPSO-TA) for the convergence of the obtained Pareto Front. The proposed algorithms are evaluated using several Quality Indicators (QI) measures for multiobjective optimization problems. The proposed algorithms can generate approximated Pareto Fronts in a reasonable CPU time. The proposed IMPSO-SA outperforms MOSA algorithm in terms of CPU time and minimizing the objective functions.<br>October 2015

APA, Harvard, Vancouver, ISO, and other styles

3

Abdallah, Fadel. "Optimization and Scheduling on Heterogeneous CPU/FPGA Architecture with Communication Delays." Thesis, Université de Lorraine, 2017. http://www.theses.fr/2017LORR0301.

Full text

Abstract:

Le domaine de l'embarqué connaît depuis quelques années un essor important avec le développement d'applications de plus en plus exigeantes en calcul auxquels les architectures traditionnelles à base de processeurs (mono/multi cœur) ne peuvent pas toujours répondre en termes de performances. Si les architectures multiprocesseurs ou multi cœurs sont aujourd'hui généralisées, il est souvent nécessaire de leur adjoindre des circuits de traitement dédiés, reposant notamment sur des circuits reconfigurables, permettant de répondre à des besoins spécifiques et à des contraintes fortes particulièrement lorsqu'un traitement temps-réel est requis. Ce travail présente l'étude des problèmes d'ordonnancement dans les architectures hétérogènes reconfigurables basées sur des processeurs généraux (CPUs) et des circuits programmables (FPGAs). L'objectif principal est d'exécuter une application présentée sous la forme d'un graphe de précédence sur une architecture hétérogène CPU/FPGA, afin de minimiser le critère de temps d'exécution total ou makespan (Cmax). Dans cette thèse, nous avons considéré deux cas d'étude : un cas d'ordonnancement qui tient compte des délais d'intercommunication entre les unités de calcul CPU et FPGA, pouvant exécuter une seule tâche à la fois, et un autre cas prenant en compte le parallélisme dans le FPGA, qui peut exécuter plusieurs tâches en parallèle tout en respectant la contrainte surfacique. Dans un premier temps, pour le premier cas d'étude, nous proposons deux nouvelles approches d'optimisation, GAA (Genetic Algorithm Approach) et MGAA (Modified Genetic Algorithm Approach), basées sur des algorithmes génétiques. Nous proposons également de tester un algorithme par séparation et évaluation (méthode Branch & Bound). Les approches GAA et MGAA proposées offrent un très bon compromis entre la qualité des solutions obtenues (critère d'optimisation de makespan) et le temps de calcul nécessaire à leur obtention pour résoudre des problèmes à grande échelle, en comparant à la méthode par séparation et évaluation (Branch & Bound) proposée et l'autre méthode exacte proposée dans la littérature. Dans un second temps, pour le second cas d'étude, nous avons proposé et implémenté une méthode basée sur les algorithmes génétiques pour résoudre le problème du partitionnement temporel dans un circuit FPGA en utilisant la reconfiguration dynamique. Cette méthode fournit de bonnes solutions avec des temps de calcul raisonnables. Nous avons ensuite amélioré notre précédente approche MGAA afin d'obtenir une nouvelle approche intitulée MGA (Multithreaded Genetic Algorithm), permettent d'apporter des solutions au problème de partitionnement. De plus, nous avons également proposé un algorithme basé sur le recuit simulé, appelé MSA (Multithreaded Simulated Annealing). Ces deux approches proposées, basées sur les méthodes métaheuristiques, permettent de fournir des solutions approchées dans un intervalle de temps très raisonnable aux problèmes d'ordonnancement et de partitionnement sur système de calcul hétérogène<br>The domain of the embedded systems becomes more and more attractive in recent years with the development of increasing computationally demanding applications to which the traditional processor-based architectures (either single or multi-core) cannot always respond in terms of performance. While multiprocessor or multicore architectures have now become generalized, it is often necessary to add to them dedicated processing circuits, based in particular on reconfigurable circuits, to meet specific needs and strong constraints, especially when real-time processing is required. This work presents the study of scheduling problems into the reconfigurable heterogeneous architectures based on general processors (CPUs) and programmable circuits (FPGAs). The main objective is to run an application presented in the form of a Data Flow Graph (DFG) on a heterogeneous CPU/FPGA architecture in order to minimize the total running time or makespan criterion (Cmax). In this thesis, we have considered two case studies: a scheduling case taking into account the intercommunication delays and where the FPGA device can perform a single task at a time, and another case taking into account parallelism in the FPGA, which can perform several tasks in parallel while respecting the constraint surface. First, in the first case, we propose two new optimization approaches GAA (Genetic Algorithm Approach) and MGAA (Modified Genetic Algorithm Approach) based on genetic algorithms. We also propose to compare these algorithms to a Branch & Bound method. The proposed approaches (GAA and MGAA) offer a very good compromise between the quality of the solutions obtained (optimization makespan criterion) and the computational time required to perform large-scale problems, unlike to the proposed Branch & Bound and the other exact methods found in the literature. Second, we first implemented an updated method based on genetic algorithms to solve the temporal partitioning problem in an FPGA circuit using dynamic reconfiguration. This method provides good solutions in a reasonable running time. Then, we improved our previous MGAA approach to obtain a new approach called MGA (Multithreaded Genetic Algorithm), which allows us to provide solutions to the partitioning problem. In addition, we have also proposed an algorithm based on simulated annealing, called MSA (Multithreaded Simulated Annealing). These two proposed approaches which are based on metaheuristic methods provide approximate solutions within a reasonable time period to the scheduling and partitioning problems on a heterogeneous computing system

APA, Harvard, Vancouver, ISO, and other styles

4

Abdallah, Fadel. "Optimization and Scheduling on Heterogeneous CPU/FPGA Architecture with Communication Delays." Electronic Thesis or Diss., Université de Lorraine, 2017. http://www.theses.fr/2017LORR0301.

Full text

Abstract:

Le domaine de l'embarqué connaît depuis quelques années un essor important avec le développement d'applications de plus en plus exigeantes en calcul auxquels les architectures traditionnelles à base de processeurs (mono/multi cœur) ne peuvent pas toujours répondre en termes de performances. Si les architectures multiprocesseurs ou multi cœurs sont aujourd'hui généralisées, il est souvent nécessaire de leur adjoindre des circuits de traitement dédiés, reposant notamment sur des circuits reconfigurables, permettant de répondre à des besoins spécifiques et à des contraintes fortes particulièrement lorsqu'un traitement temps-réel est requis. Ce travail présente l'étude des problèmes d'ordonnancement dans les architectures hétérogènes reconfigurables basées sur des processeurs généraux (CPUs) et des circuits programmables (FPGAs). L'objectif principal est d'exécuter une application présentée sous la forme d'un graphe de précédence sur une architecture hétérogène CPU/FPGA, afin de minimiser le critère de temps d'exécution total ou makespan (Cmax). Dans cette thèse, nous avons considéré deux cas d'étude : un cas d'ordonnancement qui tient compte des délais d'intercommunication entre les unités de calcul CPU et FPGA, pouvant exécuter une seule tâche à la fois, et un autre cas prenant en compte le parallélisme dans le FPGA, qui peut exécuter plusieurs tâches en parallèle tout en respectant la contrainte surfacique. Dans un premier temps, pour le premier cas d'étude, nous proposons deux nouvelles approches d'optimisation, GAA (Genetic Algorithm Approach) et MGAA (Modified Genetic Algorithm Approach), basées sur des algorithmes génétiques. Nous proposons également de tester un algorithme par séparation et évaluation (méthode Branch & Bound). Les approches GAA et MGAA proposées offrent un très bon compromis entre la qualité des solutions obtenues (critère d'optimisation de makespan) et le temps de calcul nécessaire à leur obtention pour résoudre des problèmes à grande échelle, en comparant à la méthode par séparation et évaluation (Branch & Bound) proposée et l'autre méthode exacte proposée dans la littérature. Dans un second temps, pour le second cas d'étude, nous avons proposé et implémenté une méthode basée sur les algorithmes génétiques pour résoudre le problème du partitionnement temporel dans un circuit FPGA en utilisant la reconfiguration dynamique. Cette méthode fournit de bonnes solutions avec des temps de calcul raisonnables. Nous avons ensuite amélioré notre précédente approche MGAA afin d'obtenir une nouvelle approche intitulée MGA (Multithreaded Genetic Algorithm), permettent d'apporter des solutions au problème de partitionnement. De plus, nous avons également proposé un algorithme basé sur le recuit simulé, appelé MSA (Multithreaded Simulated Annealing). Ces deux approches proposées, basées sur les méthodes métaheuristiques, permettent de fournir des solutions approchées dans un intervalle de temps très raisonnable aux problèmes d'ordonnancement et de partitionnement sur système de calcul hétérogène<br>The domain of the embedded systems becomes more and more attractive in recent years with the development of increasing computationally demanding applications to which the traditional processor-based architectures (either single or multi-core) cannot always respond in terms of performance. While multiprocessor or multicore architectures have now become generalized, it is often necessary to add to them dedicated processing circuits, based in particular on reconfigurable circuits, to meet specific needs and strong constraints, especially when real-time processing is required. This work presents the study of scheduling problems into the reconfigurable heterogeneous architectures based on general processors (CPUs) and programmable circuits (FPGAs). The main objective is to run an application presented in the form of a Data Flow Graph (DFG) on a heterogeneous CPU/FPGA architecture in order to minimize the total running time or makespan criterion (Cmax). In this thesis, we have considered two case studies: a scheduling case taking into account the intercommunication delays and where the FPGA device can perform a single task at a time, and another case taking into account parallelism in the FPGA, which can perform several tasks in parallel while respecting the constraint surface. First, in the first case, we propose two new optimization approaches GAA (Genetic Algorithm Approach) and MGAA (Modified Genetic Algorithm Approach) based on genetic algorithms. We also propose to compare these algorithms to a Branch & Bound method. The proposed approaches (GAA and MGAA) offer a very good compromise between the quality of the solutions obtained (optimization makespan criterion) and the computational time required to perform large-scale problems, unlike to the proposed Branch & Bound and the other exact methods found in the literature. Second, we first implemented an updated method based on genetic algorithms to solve the temporal partitioning problem in an FPGA circuit using dynamic reconfiguration. This method provides good solutions in a reasonable running time. Then, we improved our previous MGAA approach to obtain a new approach called MGA (Multithreaded Genetic Algorithm), which allows us to provide solutions to the partitioning problem. In addition, we have also proposed an algorithm based on simulated annealing, called MSA (Multithreaded Simulated Annealing). These two proposed approaches which are based on metaheuristic methods provide approximate solutions within a reasonable time period to the scheduling and partitioning problems on a heterogeneous computing system

APA, Harvard, Vancouver, ISO, and other styles

5

Larabi, Mohand. "Le problème de job-shop avec transport : modélisation et optimisation." Phd thesis, Université Blaise Pascal - Clermont-Ferrand II, 2010. http://tel.archives-ouvertes.fr/tel-00625528.

Full text

Abstract:

Dans cette thèse nous nous sommes intéressés à l'extension du problème job-shop en ajoutant la contrainte du transport des jobs entre les différentes machines. Dans cette étude nous avons retenu l'existence de deux types de robots, les robots de capacité de chargement unitaire (capacité=1 veut dire qu'un robot ne peut transporter qu'un seul job à la fois) et les robots de capacité de chargement non unitaire (capacité>1 veut dire qu'un robot peut transporter plusieurs job à la fois). Nous avons traité cette extension en deux étapes. Ainsi, la première étape est consacrée au problème du job-shop avec plusieurs robots de capacité de chargement unitaire et en seconde étape en ajoutant la capacité de chargement non unitaire aux robots. Pour les deux problèmes étudiés nous avons proposé :* Une modélisation linéaire ;* Une modélisation sous forme de graphe disjonctif ;* Plusieurs heuristiques de construction de solutions ;* Plusieurs recherches locales qui améliorent les solutions obtenues ;* Utilisation des algorithmes génétiques / mémétiques comme schéma global d'optimisation ;* De nouveaux benchmarks, des résultats de test de nos approches sur nos benchmarks et ceux de la littérature et ces résultats sont commentés et comparés à ceux de la littérature. Les résultats obtenus montrent la pertinence de notre modélisation ainsi que sa qualité.

APA, Harvard, Vancouver, ISO, and other styles

6

Al-Olimat, Hussein S. "Optimizing Cloudlet Scheduling and Wireless Sensor Localization using Computational Intelligence Techniques." University of Toledo / OhioLINK, 2014. http://rave.ohiolink.edu/etdc/view?acc_num=toledo1403922600.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Pokorný, Pavel. "Využití optimalizace v řízení výroby." Master's thesis, Vysoké učení technické v Brně. Fakulta podnikatelská, 2008. http://www.nusl.cz/ntk/nusl-221771.

Full text

Abstract:

The Master’s thesis deals with production scheduling in an industrial company. It uses the means of artificial intelligence to develop an appropriate production schedule in a generalized Flow-shop Programming problem. This problem can be solved by application which is a result of this thesis and was prepaired with use of the software Matlab 7.1 and its Genetic Algorithm and Direct Search toolbox. There is a part devoted to the use of advanced production systems (APS) and the concept of the operative production planning in praxis as well. The thesis pays attention to various optimization models in production scheduling and supply chain management too.

APA, Harvard, Vancouver, ISO, and other styles

8

Han, Chang, and 張翰. "Minimizing Makespan for Scheduling Problem on Unrelated Parallel Machines by Using Particle Swarm Optimization." Thesis, 2016. http://ndltd.ncl.edu.tw/handle/r948e7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Page, Daniel. "Tractability and approximability for subclasses of the makespan problem on unrelated parallel machines." 2014. http://hdl.handle.net/1993/23825.

Full text

Abstract:

Let there be m parallel machines and n jobs to be scheduled non-preemptively. A job j scheduled on machine i takes p_{i,j} time units to complete, where 1 ≤ i ≤ m and 1 ≤ j ≤ n. For a given schedule, the makespan is the completion time of a machine that finishes last. The goal is to produce a schedule of all n jobs with minimum makespan. This is known as the makespan problem on unrelated parallel machines (UPMs), denoted as R||C_{max}. In this thesis, we focus on subclasses of R||C_{max}. Our research consists of two components. First, a survey of theoretic results for R||C_{max} with a focus on approximation algorithms is presented. Second, we present exact polynomial-time algorithms and approximation algorithms for some subclasses of R||C_{max}. For instance, we present k-approximation algorithms on par with or better than the best known for certain subclasses of R||C_{max}.

APA, Harvard, Vancouver, ISO, and other styles

10

Ravi, Peruvemba Sundaram. "Techniques for Proving Approximation Ratios in Scheduling." Thesis, 2010. http://hdl.handle.net/10012/5552.

Full text

Abstract:

The problem of finding a schedule with the lowest makespan in the class of all flowtime-optimal schedules for parallel identical machines is an NP-hard problem. Several approximation algorithms have been suggested for this problem. We focus on algorithms that are fast and easy to implement, rather than on more involved algorithms that might provide tighter approximation bounds. A set of approaches for proving conjectured bounds on performance ratios for such algorithms is outlined. These approaches are used to examine Coffman and Sethi's conjecture for a worst-case bound on the ratio of the makespan of the schedule generated by the LD algorithm to the makespan of the optimal schedule. A significant reduction is achieved in the size of a hypothesised minimal counterexample to this conjecture.

APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Makespan Optimization"

1

Neumann, Frank, and Carsten Witt. "Makespan Scheduling." In Bioinspired Computation in Combinatorial Optimization. Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-16544-3_7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Fu, Bin, Yumei Huo, and Hairong Zhao. "Makespan Minimization with Machine Availability Constraints." In Combinatorial Optimization and Applications. Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-02026-1_41.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Zhang, Yuzhong, Jianfeng Ren, and Chengfei Wang. "Scheduling with Rejection to Minimize the Makespan." In Combinatorial Optimization and Applications. Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-02026-1_39.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Kesarawani, Prakash, Neeraj Kumar, and Abhishek Mishra. "Makespan Optimization in Open Shop Scheduling." In Lecture Notes in Mechanical Engineering. Springer Singapore, 2019. http://dx.doi.org/10.1007/978-981-32-9931-3_24.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Kononov, Alexander, and Yulia Kovalenko. "Makespan Minimization for Parallel Jobs with Energy Constraint." In Mathematical Optimization Theory and Operations Research. Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-49988-4_20.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Gupta, Anupam, Amit Kumar, Viswanath Nagarajan, and Xiangkun Shen. "Stochastic Makespan Minimization in Structured Set Systems (Extended Abstract)." In Integer Programming and Combinatorial Optimization. Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-45771-6_13.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Malhotra, Khushboo, Deepak Gupta, Sonia Goel, and A. K. Tripathi. "Optimization in makespan working with like parallel machines." In Sustainability in Digital Transformation Era: Driving Innovative & Growth. CRC Press, 2024. http://dx.doi.org/10.1201/9781003534136-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Milidiú, Ruy Luiz, Artur Alves Pessoa, and Eduardo Sany Laber. "Complexity of Makespan Minimization for Pipeline Transportation of Petroleum Products." In Approximation Algorithms for Combinatorial Optimization. Springer Berlin Heidelberg, 2002. http://dx.doi.org/10.1007/3-540-45753-4_21.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Chekuri, Chandra, and Michael Bender. "An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines." In Integer Programming and Combinatorial Optimization. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/3-540-69346-7_29.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Verdugo, Victor, and José Verschae. "Breaking Symmetries to Rescue Sum of Squares: The Case of Makespan Scheduling." In Integer Programming and Combinatorial Optimization. Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-17953-3_32.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Makespan Optimization"

1

Sathya Sofia, A., C. P. Thamil Selvi, P. Francis Antony Selvi, and P. Emmanuel Nicholas. "HBPSO based Resource Scheduling for Optimization of Cost and Makespan in Cloud Data Centers." In 2025 International Conference on Emerging Smart Computing and Informatics (ESCI). IEEE, 2025. https://doi.org/10.1109/esci63694.2025.10987949.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Wu, Can, and Dan Liu. "Solving the Balance Optimization Problem of Makespan and Total Computation Time for Cloud Computing Scheduling Based on NSGA-II." In 2025 International Conference on Digital Analysis and Processing, Intelligent Computation (DAPIC). IEEE, 2025. https://doi.org/10.1109/dapic66097.2025.00149.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Liu, Qiong, Qin Ye, and Xu Mei. "Inter-Cell Scheduling Optimization With Limited Transportation Capacities for Optimization of Vehicle Numbers." In ASME 2020 15th International Manufacturing Science and Engineering Conference. American Society of Mechanical Engineers, 2020. http://dx.doi.org/10.1115/msec2020-8290.

Full text

Abstract:

Abstract Inter-cell manufacturing could quickly respond to market changes and save investments on equipment. The number of vehicles in an inter-cell manufacturing system is one of important factors affecting results of inter-cell scheduling and related costs. Previous literatures on inter-cell scheduling with limited transportation capacities assumed that numbers of vehicles in a manufacturing system are fixed and simply set as numbers of manufacturing cells. However, numbers of vehicles generally are determined by decision makers and might be different in different manufacturing systems. Reducing the number of vehicles could save investments and latter operation costs. To help decision makers make decisions on the number of vehicles, it is needed to explore relationships among the number of vehicles, makespan, and total costs. An inter-cell scheduling model is proposed for an inter-cell manufacturing system with flexible routes and limited transportation capacities to optimize the number of vehicles, makespan and total costs. A Shuffled Frog Leaping Algorithm (SFLA) is designed to solve the proposed model. A four-segment coding method is proposed to encode operation sequence of parts, manufacturing cells, and machines for processing operations, and vehicle allocation. A case is used to analyze relationships among the number of vehicles, makespan, and total costs. Conclusions are yielded, which would help decision makers to make decisions on the number of vehicles.

APA, Harvard, Vancouver, ISO, and other styles

4

Xu, Ke, and Souran Manoochehri. "Job Shop Scheduling Optimization Using Genetic Algorithm With Global Criterion Technique." In ASME 2019 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2019. http://dx.doi.org/10.1115/detc2019-98076.

Full text

Abstract:

Abstract The Job Shop Scheduling Problem (JSSP) is a method which assigns multiple jobs to various machines. The large dimension of JSSP and the dynamic manufacturing environment have always been a difficult problem to optimize due to its size and complexity. In this study, three objective functions are selected namely, minimizing makespan, minimizing total cost and maximizing machine utilization. Genetic Algorithm (GA) is used to solve this scheduling problem. Lot size optimization technique is investigated for the potential of optimizing the makespan, total cost, and machine utilization objectives. Global Criterion (GC) Technique is implemented which can optimize multiple objectives all at once and obtain the best schedule. Finally, a case study is presented.

APA, Harvard, Vancouver, ISO, and other styles

5

Nailwal, Kewal Krishan, Deepak Gupta, and Sameer Sharma. "Minimizing makespan in flow shop under no-wait restriction on jobs." In 2016 International Conference on Electrical, Electronics, and Optimization Techniques (ICEEOT). IEEE, 2016. http://dx.doi.org/10.1109/iceeot.2016.7754945.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Mobini, Mohammad Hadi, Reza Entezari-Maleki, and Ali Movaghar. "Biogeography-based optimization of makespan and reliability in grid computing systems." In 2012 IV International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT 2012). IEEE, 2012. http://dx.doi.org/10.1109/icumt.2012.6459689.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Ren, Caile, Chaoyong Zhang, Yanbin Zhao, and Leilei Meng. "Migrating birds optimization for hybrid flow shop scheduling problem with makespan." In 2017 6th International Conference on Measurement, Instrumentation and Automation (ICMIA 2017). Atlantis Press, 2017. http://dx.doi.org/10.2991/icmia-17.2017.123.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Canon, Louis-Claude, and Emmanuel Jeannot. "Scheduling strategies for the bicriteria optimization of the robustness and makespan." In Distributed Processing Symposium (IPDPS). IEEE, 2008. http://dx.doi.org/10.1109/ipdps.2008.4536366.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Aswini, J., K. Johny Elma, P. John Augustine, N. Kopperundevi, S. M. Chithra, and T. Parasuraman. "Mantaray Foraging Optimization based Makespan Enhancement in Cloud based Scheduling Environment." In 2022 International Conference on Automation, Computing and Renewable Systems (ICACRS). IEEE, 2022. http://dx.doi.org/10.1109/icacrs55517.2022.10029112.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Davendra, Donald, Ivan Zelinka, Roman Senkerik, et al. "DISCRETE SELF-ORGANISING MIGRATING ALGORITHM FOR FLOW SHOP SCHEDULING WITH NO WAIT MAKESPAN." In PROCEEDINGS OF THE FOURTH GLOBAL CONFERENCE ON POWER CONTROL AND OPTIMIZATION. AIP, 2011. http://dx.doi.org/10.1063/1.3592479.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!