Abstract
First this paper considers a Common Due Window (CDW) scheduling problem of n jobs on a single machine to minimize the sum of common weighted earliness and weighted number of tardy jobs when only one manufacturer processes these jobs. Two dynamic algorithms are designed for two cases respectively and each case is proved to be ordinary NP-hard. Successively the scenario, where two manufacturers jointly process these jobs due to the insufficient production facilities or techniques of each party, is investigated. A novel dynamic programming algorithm is proposed to obtain an existing reasonable set of processing utility distributions on the bi-partition of these jobs.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anger, F.D., Lee, C.-Y., Martin-Vega, L.A.: Single Machine Scheduling with Tight Windows. Research Report, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FloridaTransportation Science, pp. 86–16 (1986)
Kramer, F.-J., Lee, C.-Y.: Common Due Window Scheduling. Production and Operations Management 6, 262–275 (1997)
Lee, C.-Y.: Earliness-Tardiness Scheduling Problems with Constant Size of Due Date Window. Research Report, Department of Industrial and System Engineering, University of Florida, Gainesville, Florida, pp. 91–17 (1991)
Liman, S.D., Ramaswamy, S.: Earliness-Tardiness Scheduling Problems with a Common Delivery Window. Operations Research Letters 15, 195–203 (1994)
Liman, S.D., Panwlker, S.S., Thongmee, S.: Determination of Common Due Window Location in a Singer Machine Scheduling Problem. European Journal of Operational Research 93, 68–74 (1996)
Koulamas, C.: Single-Machine Scheduling with Time Window and Earliness/Tardiness Penalties. European Journal of Operational Research 91, 190–202 (1996)
Ventura, J.A., Weng, M.X.: Single Machine Scheduling with a Common Delivery Window. Journal of the Operational Research Society 47, 424–434 (1996)
Koulamas, C.: Maximizing the Weighted Number of On-Time Jobs in Single Machine Scheduling with Time Windows. Math. Comput. Modelling 25, 57–62 (1997)
Liman, S.D., Panwalkar, S.S., Thongmee, S.: Common Due Window Size and Location Determination in a Single Machine Scheduling Problem. Journal of the Operational Research Society 49, 1007–1010 (1998)
Liman, S.D., Panwalkar, S.S., Thongmee, S.: Scheduling Common Due Window Problems with Controllable Processing Times. Annals of Operations Research 70, 145–154 (1997)
Chen, Q.-L., Sun, S.-J.: An Earliness and Tardiness Problem in Single Machine Scheduling wiht a Common Due Window. Applied Mathematics- a Journal of Chinese universities SerA 15, 440–448 (2000)
Chen, Z.-L., Lee, C.-Y.: A Column Generation Algorithm for Parallel Machine Common Due Window Scheduling. European Journal of Operational Research 136, 512–527 (2002)
Yen, B., Wan, G.: Tabu Search for Total Weighted Earliness and Tardiness Minimizing on Single Machine with Distinct Due Windows. European Journal of Operational Research 142, 271–281 (2002)
Baker, K.R., Scudder, G.D.: Sequencing with Earliness and Tardiness Penalties: A Review. Oper. Res. 38, 22–36 (1990)
Lawler, E.L.: Fast Approximation Algorithms for Knapsack Problems. In: Proc. 18th Annual Symposium on Foundation of Computer Science, pp. 206–213. IEEE Computer Society, Long Beach, CA (1977)
Nash, J.: Two Person Cooperative Games. Econometrica 21, 128–140 (1953)
Muthoo, A.: Bargaining Theory with Application. Cambridge University Press, Cambridge (1999)
Zhang, D.: A logical Model of Nash Bargaining Solution. In: Proceeding of IJCAI, pp. 983–990 (2005)
Trockel, W.: Integrating the Nash Program into Mechanism Theory. Review of Economic Design 7, 27–43 (2002)
Trockel, W.: Core-equivalence for the Nash Bargaining Solution. Economic Theory 25, 255–263 (2005)
Dagan, N., Volij, O., Winter, E.: A Characterization of the Nash Bargaining Solution. Social Choice and Welfare 19, 811–823 (2002)
Touati, C., Altman, E., Galtier, J.: Generalized Nash Bargaining Solution for Bandwidth Allocation. Computer Networks (in press)
Nagahisa, R., Tanaka, M.: An axiomatization of the Kalai-Smorodinsky Solution when the Feasible Sets can be Finite. Social Choice and Welfare 19, 751–761 (2002)
Lahiri, S.: Axiomatic Characterization of the Nash and Kalai-Smorodinsky Solutions for Discrete Bargaining Problems. PU.M.A 14, 207–220 (2004)
Mariotti, M.: Nash Bargaining Theory when the Number of Alternatives can be Finite. Social Choice and Welfare 15, 413–421 (1998)
Chen, Q.-L.: A New Discrete Bargaining Model on Job Partition Between Two Manufacturers. PhD Dissertation, The Chinese University of Hongkong (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gan, X., Gu, Y., Vairaktarakis, G.L., Cai, X., Chen, Q. (2007). A Scheduling Problem with One Producer and the Bargaining Counterpart with Two Producers. In: Chen, B., Paterson, M., Zhang, G. (eds) Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. ESCAPE 2007. Lecture Notes in Computer Science, vol 4614. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74450-4_28
Download citation
DOI: https://doi.org/10.1007/978-3-540-74450-4_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74449-8
Online ISBN: 978-3-540-74450-4
eBook Packages: Computer ScienceComputer Science (R0)