Scheduling Multiple Orders per Job with Various Constraints

doi:10.3969/j.issn.1005-3026.2015.10.030

Abstract

Abstract: Taking a comprehensive consideration of the characteristics of multiple product types， the past-sequence-dependent (p-s-d) setup time and the deterioration effects constraints in processes of wafer fabrication， with an objective function of minimizing total weighted earliness-tardiness penalties cost， a mathematical programming model of scheduling multiple orders per job (MOJ) in a single machine was built. On this basis， the decision-making variables were separated， and a modified genetic algorithm-ant colony optimization (MGA-ACO) algorithm adopting two-level encoding mechanism was put forward. Genetic algorithm was converged to the process of dynamic and adaptive ant colony iterations. To improve the algorithm convergence performance， a modified rule of apparent tardiness cost with setups (ATCS) was applied. Finally， the simulation results indicated that the developed algorithm is valid and feasible.

Key words: multiple product types, p-s-d setup time, deterioration effects, scheduling, MGA-ACO algorithm

CLC Number:

TP391

ZHOU Bing-hai， WANG Teng， FANG Teng. Scheduling Multiple Orders per Job with Various Constraints[J]. Journal of Northeastern University:Natural Science, 2015, 36(10): 1506-1511.

References

[1]Qu P，Mason S J.Using tabu search on the single machine multi-orders per job scheduling problem ［C］//IIE Annual Conference and Exhibition. Houston:Institute of Industrial Engineers，2004:1831-1835.
[2]Sobeyko O，Monch L.Genetic algorithms to solve a single machine multiple orders per job scheduling problem ［C］//2010 Winter Simulation Conference. Piscataway:IEEE，2010:2493 – 2503.
[3]Jampani J，Mason S J.Column generation heuristics for multiple machine，multiple orders per job scheduling problems［J］.Annals of Operations Research，2008，159(1):261-273.
[4]Mason S J，Chen J S.Scheduling multiple orders per job in a single machine to minimize total completion time［J］. European Journal of Operational Research，2010，207(1):70-77.
[5]Erramilli V，Mason S J.Multiple orders per job compatible batch scheduling［J］.IEEE Transactions on Electronics Packaging Manufacturing，2006，29 (4):285-296.
[6]Erramilli V，Mason S J.Multiple orders per job batch scheduling with incompatible jobs［J］.Annals of Operations Research，2008，159(1):245-260.
[7]Chen J S.Optimization models for the flow-shop scheduling problem with multiple orders per job［C］//The 40th International Conference on Computers and Industrial Engineering.Piscataway:IEEE，2010:1-6.
[8]Zhou B H，Zhai Z Q.Lifetime distribution model of port facilities with pitting corrosion of stochastic processes［J］.Applied Mechanics and Materials，2011，44:46-50.
[9]Shen L X，Wu Y B.Single machine past-sequence-dependent delivery times scheduling with general position-dependent and time-dependent learning effects［J］. Applied Mathematical Modelling，2013，37(7):5444-5451.
[10]Qu P，Mason S J.Metaheuristic scheduling of 300 mm jobs containing multiple orders［J］. IEEE Transactions on Semiconductor Manufacturing，2005，18(4):633-643.
[11]Pfund M，Fowler J W，Gadkari A，et al.Scheduling jobs on parallel machines with setup times and ready times［J］. Computers & Industrial Engineering，2008，54(4):764-782.

[1]	GENG Rong， ZHANG Zhao， NIU Tian-shui， WANG Yu-fei. Research and Simulation of Space-based Resource Scheduling Based on Improved Ant Colony Algorithm [J]. Journal of Northeastern University(Natural Science), 2023, 44(2): 168-176.
[2]	FANG Xiao-qing， LIU Shu-han， SUN Wen-qiang. Hydraulic Modelling and Scheduling Scheme of Blast Furnace Gas Pipeline Network [J]. Journal of Northeastern University(Natural Science), 2023, 44(1): 69-75.
[3]	DING Shan， ZANG Shi-yi， CAO Dian-ming， SHE Li-huang. Security Scheduling Algorithm of CAN Bus Based on Dynamic ID Hopping [J]. Journal of Northeastern University(Natural Science), 2022, 43(3): 350-358.
[4]	SUN Lei， CHEN Yan-feng， CHANG Shuang-shuang， DENG Qing-xu. Research on Elastic Charging Strategy of Electric Vehicles [J]. Journal of Northeastern University(Natural Science), 2022, 43(10): 1383-1390.
[5]	DU Zi-chao， LU Fu-qiang， WANG Su-xin， WANG Lei-zhen. Vehicle Scheduling Model and Optimization of Crowdsourcing Logistics Distribution [J]. Journal of Northeastern University(Natural Science), 2021, 42(8): 1210-1216.
[6]	JIANG Xu-yan， YAN Jin-li， QUAN Wei， SUN Zhi-gang. SSA:CQF-oriented Scheduling Algorithm in Time-Sensitive Networking [J]. Journal of Northeastern University Natural Science, 2020, 41(6): 784-791.
[7]	LI Ji， XU An-jun. Simulation-based Solution for Multi-crane Dynamic Scheduling in Steelmaking Shop [J]. Journal of Northeastern University Natural Science, 2020, 41(12): 1699-1707.
[8]	ZHOU Bing-hai， GU Jia-ying. An Energy-Saving Scheduling Algorithm for Non-identical Parallel Machines with Multi-resource Contraints [J]. Journal of Northeastern University Natural Science, 2019, 40(3): 403-408.
[9]	HAN Mei-ling， DENG Qing-xu， ZHANG Tian-yu， LIN Yu-han. Response Time Analysis of Multiprocessor Systems for DAG Parallel Tasks Based on G-EDF [J]. Journal of Northeastern University Natural Science, 2019, 40(3): 315-320.
[10]	ZHOU Bing-hai， TAN Fen. Scheduling Method of Material Delivery for Automotive Assembly Lines Based on Milk-Run Delivery [J]. Journal of Northeastern University Natural Science, 2018, 39(3): 389-393.
[11]	ZENG Cheng-kuan， LIU Shi-xin. Job Shop Scheduling Problem with Limited Output Buffer [J]. Journal of Northeastern University Natural Science, 2018, 39(12): 1679-1684.
[12]	WANG Xu， LIU Shi-xin， WANG Jia. Memetic Algorithm for Crane Scheduling Problem in Slab Yard with Spatial and Temporal Constraints [J]. Journal of Northeastern University Natural Science, 2017, 38(7): 913-917.
[13]	LIU Xiao-ming， XU Zhi-qiang， CHEN Xin， ZHONG De-yun. Production Scheduling in Underground Mining Using Mixed Integer Programming [J]. Journal of Northeastern University:Natural Science, 2017, 38(6): 880-885.
[14]	CHEN Di， SUN Fu-quan， LIU Shi-xin. Multi-skilled Workforce Scheduling Model for MRO Service Center [J]. Journal of Northeastern University Natural Science, 2016, 37(7): 927-930.
[15]	SUN Xiao-yu， DENG Peng-hong， ZHAO Ming. Integrated Optimization Model of Multi-period Open-Pit Mine Production Scheduling [J]. Journal of Northeastern University Natural Science, 2016, 37(10): 1460-1464.