Permutation flow shop scheduling with order acceptance and weighted tardiness. (English) Zbl 1237.90101

Summary: We study the permutation flow shop scheduling problem with order acceptance and weighted tardiness (PFSS-OAWT) faced by firms that have a number of candidate orders to be selected and scheduled on a flow shop production line. The objective is to maximize the total net profit with weighted tardiness penalties. We formulate the PFSS-OAWT problem as an integer programming (IP) model. A heuristic algorithm named simulated annealing based on partial optimization (SABPO) is developed for solving the IP model and obtaining near-optimal solutions. Computational studies are carried out on solving 160 problem instances with different scales (small, medium, large, and very large). The experimental results show that the SABPO algorithm exhibits good optimality for small-sized problems and robustness for medium/large-sized problems compared with benchmarks.


90B35 Deterministic scheduling theory in operations research
Full Text: DOI


[1] Pourbabai, B., A short term production planning and scheduling model, Engineering Costs and Production Economics, 18, 159-167 (1989)
[2] De, P.; Ghosh, J. B.; Wells, C. E., Job selection and sequencing on a single machine in a random environment, European Journal of Operational Research, 70, 425-431 (1993) · Zbl 0782.90049
[3] Slotnick, S. A.; Morton, T. E., Selecting jobs for a heavily loaded shop with lateness penalties, Computers & Operations Research, 23, 131-140 (1996) · Zbl 0871.90050
[4] Slotnick, S. A.; Morton, T. E., Order acceptance with weighted tardiness, Computers & Operations Research, 34, 3029-3042 (2007) · Zbl 1185.90093
[5] Ghosh, J. B., Job selection in a heavily loaded shop, Computers & Operations Research, 24, 141-145 (1997) · Zbl 0893.90089
[6] Lewis, H. F.; Slotnick, S. A., Multi-period job selection: planning work loads to maximize profit, Computers & Operations Research, 29, 1081-1098 (2002) · Zbl 0995.90050
[7] Rom, W. O.; Slotnick, S. A., Order acceptance using genetic algorithms, Computers & Operations Research, 36, 1758-1767 (2009) · Zbl 1179.90151
[8] Johnson, S. M., Optimal two-and three-stage production schedules with set up times included, Naval Research Logistics Quarterly, 1, 61-68 (1954) · Zbl 1349.90359
[9] Ribas, I.; Leisten, R.; Framiñan, J. M., Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective, Computers & Operations Research, 37, 1439-1454 (2010) · Zbl 1183.90189
[10] Potts, C. N.; Shmoys, D. B.; Williamson, D. P., Permutation vs. non-permutation flow shop schedules, Operations Research Letters, 10, 281-284 (1991) · Zbl 0742.90045
[11] Conway, R.; Maxwell, W.; Miller, L., Theory of Scheduling (1967), Addison-Wesley Publishing Co.: Addison-Wesley Publishing Co. MA · Zbl 1058.90500
[12] Sviridenko, M. I., A note on permutation flow shop problem, Annals of Operations Research, 129, 247-252 (2004) · Zbl 1056.90123
[13] Ladhari, T.; Haouari, M., A computational study of the permutation flow shop problem based on a tight lower bound, Computers & Operations Research, 32, 1831-1847 (2005) · Zbl 1074.90018
[14] Lageweg, B. J.; Lenstra, J. K.; Rinnooy Kan, A. H.G., A general bounding scheme for the permutation flow-shop problem, Operations Research, 26, 53-67 (1978) · Zbl 0371.90059
[15] Cheng, J.; Steiner, G.; Stephenson, P., A computational study with a new algorithm for the three-machine permutation flow-shop problem with release times, European Journal of Operational Research, 130, 559-575 (2001) · Zbl 0983.90019
[16] Chanas, S.; Kasperski, A., Minimizing maximum lateness in a single machine scheduling problem with fuzzy processing times and fuzzy due dates, Engineering Applications of Artificial Intelligence, 143, 377-386 (2001)
[17] Niu, Q.; Jiao, B.; Gu, X., Particle swarm optimization combined with genetic operators for job shop scheduling problem with fuzzy processing time, Applied Mathematics and Computation, 205, 148-158 (2008) · Zbl 1175.90187
[18] Cheng, T. C.E.; Ding, Q.; Lin, B. M.T., A concise survey of scheduling with time-dependent processing times, European Journal of Operational Research, 152, 1-13 (2004) · Zbl 1030.90023
[19] Wang, J.-B.; Daniel Ng, C. T.; Cheng, T. C.E.; Liu, L.-L., Minimizing total completion time in a two-machine flow shop with deteriorating jobs, Applied Mathematics and Computation, 180, 185-193 (2006) · Zbl 1104.90023
[20] Yang, S.-H.; Wang, J.-B., Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration, Applied Mathematics and Computation, 217, 4819-4826 (2011) · Zbl 1230.90104
[21] Wang, J.-B.; Guo, Q., A due-date assignment problem with learning effect and deteriorating jobs, Applied Mathematical Modelling, 34, 309-313 (2010) · Zbl 1185.90099
[22] Pourbabai, B., Optimal selection of orders in a just-in-time manufacturing environment: a loading model for a computer integrated manufacturing system, International Journal of Computer Integrated Manufacturing, 5, 38-44 (1992)
[23] Gupta, S. K.; Kyparisis, J.; Ip, C. M., Note—Project selection and sequencing to maximize net present value of the total return, Management Science, 38, 751-752 (1992) · Zbl 0825.90547
[24] Stadje, W., Selecting jobs for scheduling on a machine subject to failure, Discrete Applied Mathematics, 63, 257-265 (1995) · Zbl 0854.68008
[25] Oğuz, C.; Salman, F. S.; Yalçın, Z. B., Order acceptance and scheduling decisions in make-to-order systems, International Journal of Production Economics, 125, 200-211 (2010)
[26] Ivănescu, V. C.; Fransoo, J. C.; Bertrand, J. W.M., Makespan estimation and order acceptance in batch process industries when processing times are uncertain, OR Spectrum, 24, 467-495 (2002) · Zbl 1028.90518
[27] Ivănescu, V. C.; Fransoo, J. C.; Bertrand, J. W.M., A hybrid policy for order acceptance in batch process industries, OR Spectrum, 28, 199-222 (2006) · Zbl 1101.90031
[28] Raaymakers, W. H.M.; Hoogeveen, J. A., Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing, European Journal of Operational Research, 126, 131-151 (2000) · Zbl 0970.90034
[29] Raaymakers, W. H.M.; Bertrand, J. W.M.; Fransoo, J. C., Using aggregate estimation models for order acceptance in a decentralized production control structure for batch chemical manufacturing, IIE Transactions, 32, 989-998 (2000)
[30] Ebben, M. J.R.; Hans, E. W.; Olde Weghuis, F. M., Workload based order acceptance in job shop environments, OR Spectrum, 27, 107-122 (2005) · Zbl 1176.90207
[31] Yang, B.; Geunes, J., A single resource scheduling problem with job-selection flexibility, tardiness costs and controllable processing times, Computers & Industrial Engineering, 53, 420-432 (2007)
[32] Martínez, E.; Arredondo, F., Order acceptance for revenue management and capacity allocation in make-to-order batch plants, Computer Aided Chemical Engineering, 28, 1189-1194 (2010)
[33] Engels, D. W.; Karger, D. R.; Kolliopoulos, S. G.; Sengupta, S.; Uma, R. N.; Wein, J., Techniques for scheduling with rejection, Journal of Algorithms, 49, 175-191 (2003) · Zbl 1067.68024
[34] Hoogeveen, H.; Skutella, M.; Woeginger, G. J., Preemptive scheduling with rejection, Lecture Notes in Computer Science, 2000, 268-277 (1879) · Zbl 0974.68503
[35] Seiden, S. S., Preemptive multiprocessor scheduling with rejection, Theoretical Computer Science, 262, 437-458 (2001) · Zbl 0992.68072
[36] Epstein, L.; Noga, J.; Woeginger, G. J., On-line scheduling of unit time jobs with rejection: minimizing the total completion time, Operations Research Letters, 30, 415-420 (2002) · Zbl 1013.90063
[37] Miao, C.; Zhang, Y., Online scheduling with rejection on identical parallel machines, Journal of System Science & Complexity, 19, 431-435 (2006) · Zbl 1115.68040
[38] Nagy-György, J.; Imreh, Cs., Online scheduling with machine cost and rejection, Discrete Applied Mathematics, 155, 2546-2554 (2007) · Zbl 1152.90457
[39] Zhang, L.; Lu, L.; Yuan, J., Single-machine scheduling under the job rejection constraint, Theoretical Computer Science, 411, 1877-1882 (2010) · Zbl 1192.68111
[40] Roundy, R.; Chen, D.; Chen, P.; Cakanyildirim, M.; Freimer, M. B.; Melkonian, V., Capacity-driven acceptance of customer orders for a multi-stage batch manufacturing system: models and algorithms, IIE Transactions, 37, 1093-1105 (2005)
[41] Du, J.; Leung, J. Y.-T., Minimizing total tardiness on one machine is NP-hard, Mathematics of Operations Research, 15, 483-495 (1990) · Zbl 0714.90052
[42] Cesaret, B.; Oğuz, C.; Salman, F. S., A tabu search algorithm for order acceptance and scheduling, Computers & Operations Research, 39, 1197-1205 (2012)
[43] Janiak, A.; Kozan, E.; Lichtenstein, M.; Oğuz, C., Metaheuristic approaches to the hybrid flow shop scheduling problem with a cost-related criterion, International Journal of Production Economics, 105, 407-424 (2007)
[44] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162
[45] Metropolis, N.; Rosenbluth, A.; Teller, A.; Teller, E., Equation of state calculations by fast computing machines, The Journal of Chemical Physics, 21, 1087-1092 (1953) · Zbl 1431.65006
[46] Smith, W. E., Various optimizers for single-stage production, Naval Research Logistics Quarterly, 3, 59-66 (1956)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.